Changeset 30603 in project for wiki/man/4/Unit datastructures
 Timestamp:
 03/26/14 09:29:17 (7 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

wiki/man/4/Unit datastructures
r28559 r30603 254 254 ==== topologicalsort 255 255 256 <procedure>(topologicalsort D AG PRED)</procedure>257 258 Sorts the directed acyclic graph dag {{DAG}} so that for every edge from vertex256 <procedure>(topologicalsort DG PRED)</procedure> 257 258 Sorts the directed graph dg {{DG}} so that for every edge from vertex 259 259 u to v, u will come before v in the resulting list of vertices. 260 260 261 {{D AG}} is a list of sublists. The car of each sublist is a261 {{DG}} is a list of sublists. The car of each sublist is a 262 262 vertex. The cdr is the adjacency list of that vertex, i.e. a list of 263 263 all vertices to which there exists an edge from the car vertex. 264 264 {{pred}} is procedure of two arguments that should compare vertices 265 for equality. 265 for equality. 266 266 267 267 Time complexity: O (V + E) … … 283 283 </enscript> 284 284 285 If the {{DG}} contains cycles a condition will be signaled. You can react to this event like so: 286 287 <enscript language=scheme> 288 (define cyclicdg '((north east) (east north))) 289 290 (conditioncase (topologicalsort cyclicdg eq?) 291 ((cycle) (print "Your DG contains cycles"))) 292 293 </enscript> 294 285 295 === Random numbers 286 296
Note: See TracChangeset
for help on using the changeset viewer.