Next: , Previous: debugging time, Up: Top


8 (graph topological-sort)

8.1 Overview

 The algorithm is inspired by Cormen, Leiserson and Rivest (1990)
 ``Introduction to Algorithms'', chapter 23.

8.2 Usage

— Function: topological-sort dag

Returns a list of the objects in the directed acyclic graph, dag, topologically sorted. Objects are compared using equal?. The graph has the form:

           (list (obj1 . (dependents-of-obj1))
                 (obj2 . (dependents-of-obj2)) ...)

...specifying, for example, that obj1 must come before all the objects in (dependents-of-obj1) in the sort.

— Function: topological-sortq dag

Returns a list of the objects in the directed acyclic graph, dag, topologically sorted. Objects are compared using eq?. The graph has the form:

           (list (obj1 . (dependents-of-obj1))
                 (obj2 . (dependents-of-obj2)) ...)

...specifying, for example, that obj1 must come before all the objects in (dependents-of-obj1) in the sort.

— Function: topological-sortv dag

Returns a list of the objects in the directed acyclic graph, dag, topologically sorted. Objects are compared using eqv?. The graph has the form:

           (list (obj1 . (dependents-of-obj1))
                 (obj2 . (dependents-of-obj2)) ...)

...specifying, for example, that obj1 must come before all the objects in (dependents-of-obj1) in the sort.