Transitive Hülle

Ich bin zur Zeit dabei, wieder in LISP einzusteigen. In einem beruflichen Projekt, das ich in der Programmiersprache Python abgewickelt hatte, war es erforderlich, die Transitive Hülle eines Graphen zu berechnen. Deswegen habe ich dieses simple Beispiel mal genommen und versucht, es LISP-gemäß zu implementieren. Dabei ging es mir nur darum, ein bisschen zu üben.

Wem der Begriff “Transitive Hülle” fremd ist: Hat man einen gerichteten Graphen oder eine zweistellige Relation, so gilt für die Transitive Hülle: Falls zwei Kanten x->y und y->z enthalten sind, so ist auch die Kante x->z enthalten. Näheres findet man in der Wikipedia.

Der Graph soll als liste von Kanten, also z.B ((a b) (b c) (a x)) übergeben werden.
Die Definition der Berechnung in LISP erfolgt nach den Regeln:

1. Die Transitive Hülle der leeren Menge ist die leere Menge
2. Die Transitive Hülle einer einelementigen Menge ist eben diese einelementige Menge
3. Ansonsten wird die Transitive Hülle berechnet, indem die Transitive Hülle der Restliste (das CDR) berechnet wird und dann das CAR der Liste mit jedem Element der Transitiven Hülle der Restliste verglichen wird, und - falls noch eine Transition fehlt, diese hinzugefügt wird.

(defun transitive-closure (edges)
  (cond ((null edges) nil)
	((eq 1 (length edges)) edges)
	( t (union edges
		   (let ((e (car edges))
			 (l (transitive-closure (cdr edges)))
			 )
		     (loop for x in l
			when (eq (second x) (first e))
			collect (list (first x) (second e))
			when (eq (second e) (first x))
			collect (list (first e) (second x))))
		   :test #'equal))))

Welche Transitionen noch fehlen, mit dem LOOP-Macro festgestellt. Es gesucht, ob in der Transitiven Hülle der Restlliste das erste oder das zweite element des “CAR” als zeites oder erstes element einer Kante vorkommt und, falls dem so ist, die Transitive Kante hinzugenommen wird.

Beispiele:

[120]> (transitive-closure '((a b) (b c) (a x)))
((A B) (B C) (A X) (A C))

[121]> (transitive-closure '((a b) (b c) (a x) (x d)))
((A B) (B C) (A X) (X D) (A C))

Es würde mich als LISP-Wiedereinsteiger natürlich interessieren, ob es eine elegantere oder schnellere Berechnungsmöglichkeit gibt. Vielleicht findet ja ein LISP-Kenner mein Posting und hilft mir weiter. Danke im Voraus!