equal
deleted
inserted
replaced
435 end |
435 end |
436 | assemble nil _ = nil |
436 | assemble nil _ = nil |
437 |
437 |
438 (* Compute, for each adjacency list, the list with reversed edges, |
438 (* Compute, for each adjacency list, the list with reversed edges, |
439 and concatenate these lists. *) |
439 and concatenate these lists. *) |
440 val flipped = Library.foldr (op @) ((map flip g),nil) |
440 val flipped = foldr (op @) nil (map flip g) |
441 |
441 |
442 in assemble g flipped end |
442 in assemble g flipped end |
443 |
443 |
444 (* *********************************************************************** *) |
444 (* *********************************************************************** *) |
445 (* *) |
445 (* *) |
473 (* Returns the nodes in the DFS tree rooted at u in g *) |
473 (* Returns the nodes in the DFS tree rooted at u in g *) |
474 fun dfs_visit g u : term list = |
474 fun dfs_visit g u : term list = |
475 let |
475 let |
476 val _ = visited := u :: !visited |
476 val _ = visited := u :: !visited |
477 val descendents = |
477 val descendents = |
478 Library.foldr (fn ((v,l),ds) => if been_visited v then ds |
478 foldr (fn ((v,l),ds) => if been_visited v then ds |
479 else v :: dfs_visit g v @ ds) |
479 else v :: dfs_visit g v @ ds) |
480 ((adjacent (op aconv) g u) ,nil) |
480 nil (adjacent (op aconv) g u) |
481 in |
481 in |
482 finish := u :: !finish; |
482 finish := u :: !finish; |
483 descendents |
483 descendents |
484 end |
484 end |
485 in |
485 in |
523 |
523 |
524 fun dfs_visit g u : int list = |
524 fun dfs_visit g u : int list = |
525 let |
525 let |
526 val _ = visited := u :: !visited |
526 val _ = visited := u :: !visited |
527 val descendents = |
527 val descendents = |
528 Library.foldr (fn ((v,l),ds) => if been_visited v then ds |
528 foldr (fn ((v,l),ds) => if been_visited v then ds |
529 else v :: dfs_visit g v @ ds) |
529 else v :: dfs_visit g v @ ds) |
530 ( ((adjacent (op =) g u)) ,nil) |
530 nil (adjacent (op =) g u) |
531 in descendents end |
531 in descendents end |
532 |
532 |
533 in u :: dfs_visit g u end; |
533 in u :: dfs_visit g u end; |
534 |
534 |
535 |
535 |