Guile Library

(graph topological-sort)

Overview

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

Usage

topological-sort dag
[Function]

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.

topological-sortq dag
[Function]

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.

topological-sortv dag
[Function]

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.