DFS and BFS use a strange order about ocamlgraph

[backtracking]

Indeed, it may seem confusing at first sight. But there is nothing wrong with this API (unless I'm mistaken).

The idea is that the meaningful functions are rather iter/fold_component, where the starting point of the DFS is user-provided. I guess this is exactly what you suggest in your third solution.
If you look for instance in Sedgewick&Wayne's Algorithms, you'll see that this is the only function in the DFS API. See https://algs4.cs.princeton.edu/41graph/DepthFirstSearch.java.html

The iter and fold functions are also provided, for your convenience. Indeed they perform as you observed: they run the user-provided iter/fold_vertex functions and, for each vertex not yet visited, start a new DFS from this vertex. Hence the rather cryptic comment saying that iterating over DFS roots only is fine. Said otherwise, it is up to you to come up with an iter_vertex function that will identify suitable DFS roots, e.g. vertices with no predecessors.

My understanding is that you'd like some additional function in the DFS API that would identify vertices with no predecessors for you and run DFS from these vertices. Indeed we could do that, though it would raise some issues such as what to do when you have a strongly-connected component (i.e. with no vertex with no predecessors).

I hope I understood your question correctly.

[eponier]

You perfectly understood my question and carefully answered it.

I had missed the documentation of fold in DFS that could have hinted me in the right direction.

The function is applied each time a node is reached for the first time, before idoterating¹ over its successors. Tail-recursive.

I think the main issue, here, is documentation. A few points could be improved:

• The functions in BFS could get the same documentation as in DFS. For instance, the documentation quoted above appears only in DFS.
• The documentation could highlight that the *_component versions are probably the ones to be used.
• The descriptions of iter_vertex and fold_vertex could explain that the order is important if the user wants to use the non-component versions of the functions.

Thanks for taking the time to answer me!

¹The typo is present in the documentation.

[backtracking]

Fixed in commit a2d7918.