Enable identification of cycle-creating edge during topographical sort (CCGraph)

[cemerick]

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:

1. it seems like it would be a breaking change
2. I can imagine wanting to include the label (_e) from the offending edge in the Cycle exception as well?

[c-cube]

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).

[cemerick]

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. 🤷‍♂️

[c-cube]

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)

[c-cube]

is this still relevant @cemerick ?

[cemerick]

A fair question; I'm not sure. I'll try to look again in this area early next week.

[cemerick]

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. :-)