GNU Info

(slib.info)Topological Sort

---

Next: String Search Prev: Sorting Up: Sorting and Searching

---

Enter node , (file) or (file)node

Topological Sort
----------------

  `(require 'topological-sort)' or `(require 'tsort)'

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

 - Function: tsort dag pred
 - Function: topological-sort dag pred
     where
    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 one of `eq?', `eqv?', `equal?', `=', `char=?',
          `char-ci=?', `string=?', or `string-ci=?'.

     Sort the directed acyclic graph DAG so that for every edge from
     vertex U to V, U will come before V in the resulting list of
     vertices.

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

     Example (from Cormen):
          Prof. Bumstead topologically sorts his clothing when getting
          dressed.  The first argument to `tsort' describes which
          garments he needs to put on before others.  (For example,
          Prof Bumstead needs to put on his shirt before he puts on his
          tie or his belt.)  `tsort' gives the correct order of
          dressing:

          (require 'tsort)
          (tsort '((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)