src/Pure/General/graph.ML
changeset 15531 08c8dad8e399
parent 15160 394fb9b8908b
child 15570 8d8c70b41bab
equal deleted inserted replaced
15530:6f43714517ee 15531:08c8dad8e399
    90 fun maximals (Graph tab) =
    90 fun maximals (Graph tab) =
    91   Table.foldl (fn (ms, (m, (_, (_, [])))) => m :: ms | (ms, _) => ms) ([], tab);
    91   Table.foldl (fn (ms, (m, (_, (_, [])))) => m :: ms | (ms, _) => ms) ([], tab);
    92 
    92 
    93 fun get_entry (Graph tab) x =
    93 fun get_entry (Graph tab) x =
    94   (case Table.lookup (tab, x) of
    94   (case Table.lookup (tab, x) of
    95     Some entry => entry
    95     SOME entry => entry
    96   | None => raise UNDEF x);
    96   | NONE => raise UNDEF x);
    97 
    97 
    98 fun map_entry x f (G as Graph tab) = Graph (Table.update ((x, f (get_entry G x)), tab));
    98 fun map_entry x f (G as Graph tab) = Graph (Table.update ((x, f (get_entry G x)), tab));
    99 
    99 
   100 
   100 
   101 (* nodes *)
   101 (* nodes *)
   152   Graph (Table.update_new ((x, (info, ([], []))), tab));
   152   Graph (Table.update_new ((x, (info, ([], []))), tab));
   153 
   153 
   154 fun del_nodes xs (Graph tab) =
   154 fun del_nodes xs (Graph tab) =
   155   let
   155   let
   156     fun del (x, (i, (preds, succs))) =
   156     fun del (x, (i, (preds, succs))) =
   157       if x mem_key xs then None
   157       if x mem_key xs then NONE
   158       else Some (x, (i, (foldl op del_key (preds, xs), foldl op del_key (succs, xs))));
   158       else SOME (x, (i, (foldl op del_key (preds, xs), foldl op del_key (succs, xs))));
   159   in Graph (Table.make (mapfilter del (Table.dest tab))) end;
   159   in Graph (Table.make (mapfilter del (Table.dest tab))) end;
   160 
   160 
   161 
   161 
   162 (* edges *)
   162 (* edges *)
   163 
   163 
   175       |> map_entry x (fn (i, (preds, succs)) => (i, (preds, succs del_key y)))
   175       |> map_entry x (fn (i, (preds, succs)) => (i, (preds, succs del_key y)))
   176   else G;
   176   else G;
   177 
   177 
   178 fun diff_edges G1 G2 =
   178 fun diff_edges G1 G2 =
   179   flat (dest G1 |> map (fn (x, ys) => ys |> mapfilter (fn y =>
   179   flat (dest G1 |> map (fn (x, ys) => ys |> mapfilter (fn y =>
   180     if is_edge G2 (x, y) then None else Some (x, y))));
   180     if is_edge G2 (x, y) then NONE else SOME (x, y))));
   181 
   181 
   182 fun edges G = diff_edges G empty;
   182 fun edges G = diff_edges G empty;
   183 
   183 
   184 
   184 
   185 (* merge *)
   185 (* merge *)