ocaml-containers
ocaml-containers copied to clipboard
Enable identification of cycle-creating edge during topographical sort (CCGraph)
I had need of a topographical sort that additionally reported which edge happened to offend in the case of a cyclic graph. To get there, I added this to my module:
module Topo (V : sig type t val pp : Format.t -> t -> unit end) = struct
(* this code copy-pasted from CCGraph so that we can raise an exception on cycles
that includes the offending `Back edge *)
open CCGraph
exception Cycle of V.t * V.t
let _ =
Printexc.register_printer
(function
| Cycle (src, dst) -> Some (Format.asprintf "Cycle (%a -> %a)" V.pp src V.pp dst)
| _ -> None)
let topo_sort_tag ~eq ?(rev=false) ~tags ~graph iter =
(* use DFS *)
let l =
Traverse.Event.dfs_tag ~eq ~tags ~graph iter
|> Iter.filter_map
(function
| `Exit v -> Some v
| `Edge (src, _e, dst, `Back) -> raise (Cycle (src, dst))
| `Enter _
| `Edge _ -> None
)
|> Iter.fold (fun acc x -> x::acc) []
in
if rev then List.rev l else l
let topo_sort ~eq ?rev ~tbl ~graph iter =
let tags = {
get_tag=tbl.mem;
set_tag=(fun v -> tbl.add v ());
} in
topo_sort_tag ~eq ?rev ~tags ~graph iter
end
As you can see, the bodies of these two functions are effectively identical to that found in CCGraph.ml now, except that the exception raised on a cycle includes the `Back
edge.
I'd be happy to produce a PR for this if you'd like, but:
- it seems like it would be a breaking change
- I can imagine wanting to include the label (
_e
) from the offending edge in theCycle
exception as well?
Wouldn't you want the full cycle, in your use case? I think it could be done by maintaining a stack at enter/exit events, but it probably deserves to be in a different function (which also means it doesn't break compat).
I do, and you're right that maintaining a stack as one approach, but then you're talking about a completely different (and more expensive) topo sort routine.
I haven't gotten around to it quite yet, but I can get the full cycle otherwise (snip the offending edge reported by the exception and then depth-first-search back to the node on the other side), and I figured that would be preferable to maintaining a separate topo routine. :man_shrugging:
A common trick I do for retrocompat is make the actual implem the most general one, and reimplement the old function in terms of the new one (ie. with a with Cycle_full _ -> raise Cycle
)
is this still relevant @cemerick ?
A fair question; I'm not sure. I'll try to look again in this area early next week.
FWIW, this does still seem like a worthwhile addition, but is no longer relevant for me (I've moved all our graph stuffs to graphlib/ocamlgraph since opening this issue). Whether to leave it open or close (for now?) I leave up to you. :-)