From: Frank Brickle
Subject: re: topological sort
Date: Mon, 08 Apr 1996 00:00:00 +0000
Message-ID: <4kc4s2$ppp@newton.texel.com>

In article <··········@boris.eden.com> ······@eden.com (schermerhorm) writes:
>>Does anyone know how to do a topological sort of a directed 
>>graph in lisp?
>
>Cormen, Leisersen and Rivest (Introduction to Algorithms) give an
>algorithm in Chapter 23. Probably other Algorithms texts do also. Note
>that the graph has to be cycle free.

Does this help?

(defun tsort (edges)
  (let* ((leaders (delete-duplicates (mapcar #'first edges) :test #'equal))
         (followers (delete-duplicates (mapcar #'second edges) :test #'equal))
         (neighbors (mapcar #'list leaders))
         (visited '())
         (ordering '()))
    (mapc #'(lambda (e) (push (second e) (rest (assoc (first e) neighbors))))
          edges)
    (labels ((dfs (v)
               (pushnew v visited)
               (mapc #'(lambda (n) (when (not (member n visited)) (dfs n)))
                     (rest (assoc v neighbors)))
               (push v ordering)))
      (mapc #'dfs (set-difference leaders followers)))
    ordering))

#|
(time
(tsort '((i am)
         (not trying)
         (confuse the)
         (am trying)
         (trying to)
         (am not)
         (trying the)
         (to confuse)
         (the issue)))
)

(tsort '((i am) (am i)))
|#