Changeset 15923 in project


Ignore:
Timestamp:
09/16/09 13:48:42 (10 years ago)
Author:
Ivan Raikov
Message:

added information about topological-sort to the manual

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/man/4/Unit data-structures

    r15417 r15923  
    251251Returns true if the list or vector {{SEQUENCE}} is already sorted.
    252252
    253 
     253==== topological-sort
     254
     255 [procedure] (topological-sort DAG PRED)
     256
     257Sorts the directed acyclic graph dag {{DAG}} so that for every edge from vertex
     258u to v, u will come before v in the resulting list of vertices.
     259
     260{{DAG}} is a list of sublists. The car of each sublist is a
     261vertex. The cdr is the adjacency list of that vertex, i.e. a list of
     262all vertices to which there exists an edge from the car vertex.
     263{{pred}} is procedure of two arguments that should compare vertices
     264for equality.
     265
     266Time complexity: O (|V| + |E|)
     267
     268<enscript highlight=scheme>
     269(require 'tsort)
     270(topological-sort
     271       '((shirt tie belt)
     272         (tie jacket)
     273         (belt jacket)
     274         (watch)
     275         (pants shoes belt)
     276         (undershorts pants shoes)
     277         (socks shoes))
     278       eq?)
     279
     280=>
     281
     282(socks undershorts pants shoes watch shirt belt tie jacket)
     283</enscript>
    254284
    255285=== Random numbers
Note: See TracChangeset for help on using the changeset viewer.