;
; trans-closure berechnet den transitiven Abschluss einer Relation R
; die als Liste von Paaren (ai . bi) mit der Bedeutung ai R bi gegeben sind


(defun trans-closure (rel-pair-lis)

  (let* ((domain-elems (elements-of rel-pair-lis))

         (elem-followers (loop for x in domain-elems append (list x ()))))

    (loop

     for rel in rel-pair-lis do

     (let ((e1 (car rel))

           (e2 (cdr rel)))

       (setf (getf elem-followers e1) 

             (union (list e2) 

                    (union (getf elem-followers e1) (getf elem-followers e2))))

       (loop

        for y in domain-elems

        when (member e1 (getf elem-followers y)) do

        (setf (getf elem-followers y)

              (union (getf elem-followers y) (getf elem-followers e1)))))

     finally (return elem-followers))))


;
; elements-of einer Relationspaarliste gibt eine Liste der verwendeten Elemente zurück
;


(defun elements-of (rel-pair-lis)

  (cond ((null rel-pair-lis) ())

        (t 

         (union (adjoin (car (first rel-pair-lis)) (list (cdr (first rel-pair-lis))))
                
                (elements-of (cdr rel-pair-lis))))))