src/Pure/General/graph.ML
changeset 39020 ac0f24f850c9
parent 37853 26906cacbaae
child 39021 139aada5caf8
equal deleted inserted replaced
39019:bfd0c0e4dbee 39020:ac0f24f850c9
   112   in (a, Graph (Table.update (x, node') tab)) end;
   112   in (a, Graph (Table.update (x, node') tab)) end;
   113 
   113 
   114 
   114 
   115 (* nodes *)
   115 (* nodes *)
   116 
   116 
   117 fun map_nodes f (Graph tab) = Graph (Table.map (fn (i, ps) => (f i, ps)) tab);
   117 fun map_nodes f (Graph tab) = Graph (Table.map (K (apfst f)) tab);
   118 
   118 
   119 fun get_node G = #1 o get_entry G;
   119 fun get_node G = #1 o get_entry G;
   120 
   120 
   121 fun map_node x f = map_entry x (fn (i, ps) => (f i, ps));
   121 fun map_node x f = map_entry x (fn (i, ps) => (f i, ps));
   122 
   122 
   159   Graph (Table.default (x, (info, ([], []))) tab);
   159   Graph (Table.default (x, (info, ([], []))) tab);
   160 
   160 
   161 fun del_nodes xs (Graph tab) =
   161 fun del_nodes xs (Graph tab) =
   162   Graph (tab
   162   Graph (tab
   163     |> fold Table.delete xs
   163     |> fold Table.delete xs
   164     |> Table.map (fn (i, (preds, succs)) =>
   164     |> Table.map (fn _ => fn (i, (preds, succs)) =>
   165       (i, (fold remove_key xs preds, fold remove_key xs succs))));
   165       (i, (fold remove_key xs preds, fold remove_key xs succs))));
   166 
   166 
   167 fun del_node x (G as Graph tab) =
   167 fun del_node x (G as Graph tab) =
   168   let
   168   let
   169     fun del_adjacent which y = Table.map_entry y (fn (i, ps) => (i, (which (remove_key x) ps)));
   169     fun del_adjacent which y = Table.map_entry y (fn (i, ps) => (i, (which (remove_key x) ps)));
   204 fun no_edges (i, _) = (i, ([], []));
   204 fun no_edges (i, _) = (i, ([], []));
   205 
   205 
   206 fun join f (G1 as Graph tab1, G2 as Graph tab2) =
   206 fun join f (G1 as Graph tab1, G2 as Graph tab2) =
   207   let fun join_node key ((i1, edges1), (i2, _)) = (f key (i1, i2), edges1) in
   207   let fun join_node key ((i1, edges1), (i2, _)) = (f key (i1, i2), edges1) in
   208     if pointer_eq (G1, G2) then G1
   208     if pointer_eq (G1, G2) then G1
   209     else fold add_edge (edges G2) (Graph (Table.join join_node (tab1, Table.map no_edges tab2)))
   209     else fold add_edge (edges G2) (Graph (Table.join join_node (tab1, Table.map (K no_edges) tab2)))
   210   end;
   210   end;
   211 
   211 
   212 fun gen_merge add eq (G1 as Graph tab1, G2 as Graph tab2) =
   212 fun gen_merge add eq (G1 as Graph tab1, G2 as Graph tab2) =
   213   let fun eq_node ((i1, _), (i2, _)) = eq (i1, i2) in
   213   let fun eq_node ((i1, _), (i2, _)) = eq (i1, i2) in
   214     if pointer_eq (G1, G2) then G1
   214     if pointer_eq (G1, G2) then G1
   215     else fold add (edges G2) (Graph (Table.merge eq_node (tab1, Table.map no_edges tab2)))
   215     else fold add (edges G2) (Graph (Table.merge eq_node (tab1, Table.map (K no_edges) tab2)))
   216   end;
   216   end;
   217 
   217 
   218 fun merge eq GG = gen_merge add_edge eq GG;
   218 fun merge eq GG = gen_merge add_edge eq GG;
   219 
   219 
   220 
   220