src/Pure/General/graph.ML
changeset 46658 f11400424782
parent 46614 165886a4fe64
child 46665 919dfcdf6d8a
equal deleted inserted replaced
46657:61aac9bd43fa 46658:f11400424782
    51   val restrict: (key -> bool) -> 'a T -> 'a T
    51   val restrict: (key -> bool) -> 'a T -> 'a T
    52   val merge: ('a * 'a -> bool) -> 'a T * 'a T -> 'a T                 (*exception DUP*)
    52   val merge: ('a * 'a -> bool) -> 'a T * 'a T -> 'a T                 (*exception DUP*)
    53   val join: (key -> 'a * 'a -> 'a) (*exception DUP/SAME*) ->
    53   val join: (key -> 'a * 'a -> 'a) (*exception DUP/SAME*) ->
    54     'a T * 'a T -> 'a T                                               (*exception DUP*)
    54     'a T * 'a T -> 'a T                                               (*exception DUP*)
    55   val irreducible_paths: 'a T -> key * key -> key list list
    55   val irreducible_paths: 'a T -> key * key -> key list list
    56   val all_paths: 'a T -> key * key -> key list list
       
    57   exception CYCLES of key list list
    56   exception CYCLES of key list list
    58   val add_edge_acyclic: key * key -> 'a T -> 'a T                     (*exception UNDEF | CYCLES*)
    57   val add_edge_acyclic: key * key -> 'a T -> 'a T                     (*exception UNDEF | CYCLES*)
    59   val add_deps_acyclic: key * key list -> 'a T -> 'a T                (*exception UNDEF | CYCLES*)
    58   val add_deps_acyclic: key * key list -> 'a T -> 'a T                (*exception UNDEF | CYCLES*)
    60   val merge_acyclic: ('a * 'a -> bool) -> 'a T * 'a T -> 'a T         (*exception CYCLES*)
    59   val merge_acyclic: ('a * 'a -> bool) -> 'a T * 'a T -> 'a T         (*exception CYCLES*)
    61   val topological_order: 'a T -> key list
    60   val topological_order: 'a T -> key list
   268       if eq_key (x, z) then cons (z :: path)
   267       if eq_key (x, z) then cons (z :: path)
   269       else fold (paths (z :: path)) (irreducible_preds G X path z);
   268       else fold (paths (z :: path)) (irreducible_preds G X path z);
   270   in if eq_key (x, y) andalso not (is_edge G (x, x)) then [[]] else paths [] y [] end;
   269   in if eq_key (x, y) andalso not (is_edge G (x, x)) then [[]] else paths [] y [] end;
   271 
   270 
   272 
   271 
   273 (* all paths *)
       
   274 
       
   275 fun all_paths G (x, y) =
       
   276   let
       
   277     val (_, X) = reachable (imm_succs G) [x];
       
   278     fun paths path z =
       
   279       if not (null path) andalso eq_key (x, z) then [z :: path]
       
   280       else if Keys.member X z andalso not (member eq_key path z)
       
   281       then maps (paths (z :: path)) (immediate_preds G z)
       
   282       else [];
       
   283   in paths [] y end;
       
   284 
       
   285 
       
   286 (* maintain acyclic graphs *)
   272 (* maintain acyclic graphs *)
   287 
   273 
   288 exception CYCLES of key list list;
   274 exception CYCLES of key list list;
   289 
   275 
   290 fun add_edge_acyclic (x, y) G =
   276 fun add_edge_acyclic (x, y) G =