chickadee » data-structures » topological-sort

Sorts the directed acyclic graph dag DAG so that for every edge from vertex u to v, u will come before v in the resulting list of vertices.

DAG is a list of sublists. The car of each sublist is a vertex. The cdr is the adjacency list of that vertex, i.e. a list of all vertices to which there exists an edge from the car vertex. pred is procedure of two arguments that should compare vertices for equality.

Time complexity: O (|V| + |E|)

(topological-sort
       '((shirt tie belt)
         (tie jacket)
         (belt jacket)
         (watch)
         (pants shoes belt)
         (undershorts pants shoes)
         (socks shoes))
       eq?)

=>

(socks undershorts pants shoes watch shirt belt tie jacket)

If a cycle is detected during the sorting process, an exception of the condition kinds (exn runtime cycle) is thrown.