Changeset 30603 in project


Ignore:
Timestamp:
03/26/14 09:29:17 (7 years ago)
Author:
certainty
Message:

updated documentation of topological-sort

File:
1 edited

Legend:

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

    r28559 r30603  
    254254==== topological-sort
    255255
    256 <procedure>(topological-sort DAG PRED)</procedure>
    257 
    258 Sorts the directed acyclic graph dag {{DAG}} so that for every edge from vertex
     256<procedure>(topological-sort DG PRED)</procedure>
     257
     258Sorts the directed graph dg {{DG}} so that for every edge from vertex
    259259u to v, u will come before v in the resulting list of vertices.
    260260
    261 {{DAG}} is a list of sublists. The car of each sublist is a
     261{{DG}} is a list of sublists. The car of each sublist is a
    262262vertex. The cdr is the adjacency list of that vertex, i.e. a list of
    263263all vertices to which there exists an edge from the car vertex.
    264264{{pred}} is procedure of two arguments that should compare vertices
    265 for equality.
     265for equality. 
    266266
    267267Time complexity: O (|V| + |E|)
     
    283283</enscript>
    284284
     285If the {{DG}} contains cycles a condition will be signaled. You can react to this event like so:
     286
     287<enscript language=scheme>
     288(define cyclic-dg '((north east) (east north)))
     289
     290(condition-case (topological-sort cyclic-dg eq?)
     291  ((cycle) (print "Your DG contains cycles")))
     292
     293</enscript>
     294
    285295=== Random numbers
    286296
Note: See TracChangeset for help on using the changeset viewer.