[WIP] Traverse.Dfs.has_cycle returns the cycle as a list of vertices

[dCastanho]

This patch proposes to update the has_cycle function, from module Traverse.Dfs, to return a list of vertices that represent the cycle found in the graph, whenever there is such a cycle. The return value of the function is now a pair: the first component is a Boolean value (whether there is a cycle); the second component is the list of vertices representing the cycle. In case no cycle is found, it returns (false, []).

All the tests and benchmarks have been updated accordingly (i.e., function signatures and function calls). A new test_traverse.ml file was added to the /tests folder, together with a .expected file.

Regarding the case where there is no cycle, I would like to pose two questions to the OCamlgraph maintainers:

1. Instead of returning the empty list, would it be better to return a topological sort (as a list)?
2. If so, should I build the topological sorting as we traverse the graph in search of a cycle, or should it be after we've established there are no cycles?

[backtracking]

Many thanks for this patch. Indeed, it makes sense to provide a way to obtain the cycle when there is one. Yet I'm a bit worried about changing the API and (possibly) the efficiency of has_cycle (even by a constant factor). In my opinion, it would make sense to provide a second function

val find_cycle: G.t -> G.V.t list

that returns a cycle, if any, and raises Not_found otherwise. What do you think?

PS: And of course, it would be trivial to derive the current function has_cycle from the new function find_cycle, provided the efficiency is the same.

[backtracking]

Note: It would be nice to document the returned list with a proper specification. Is my understanding correct if I say that it is a list [v0;v1;...;vn] with

• n at least 1 for a directed graph and at least 2 for an undirected graph
• distinct vertices
• edges v(i)->v(i+1) and vn->v0 in the graph ?