Changeset 15923 in project
 Timestamp:
 09/16/09 13:48:42 (10 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

wiki/man/4/Unit datastructures
r15417 r15923 251 251 Returns true if the list or vector {{SEQUENCE}} is already sorted. 252 252 253 253 ==== topologicalsort 254 255 [procedure] (topologicalsort DAG PRED) 256 257 Sorts the directed acyclic graph dag {{DAG}} so that for every edge from vertex 258 u 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 261 vertex. The cdr is the adjacency list of that vertex, i.e. a list of 262 all vertices to which there exists an edge from the car vertex. 263 {{pred}} is procedure of two arguments that should compare vertices 264 for equality. 265 266 Time complexity: O (V + E) 267 268 <enscript highlight=scheme> 269 (require 'tsort) 270 (topologicalsort 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> 254 284 255 285 === Random numbers
Note: See TracChangeset
for help on using the changeset viewer.