[Q] `finish_edge` in non-recursive DFS

[qbit86]

Could you please clarify implementation of directed and undirected DFS, non-recursive ones?

Take a look at these lines: depth_first_search.hpp#L173..L178

Here is comment:

finish_edge has to be called here, not after the loop. Think of the pop as the return from a recursive call.

But in undirected DFS this event is raised after the loop: undirected_dfs.hpp#L104..L105

Why it's different in this case?

[qbit86]

To make this issue more like feature request than forum-like question: please, add pseudocode for non-recursive version of DFS on these documentation pages:

• depth_first_search.html
• undirected_dfs.html

[qbit86]

Speaking on directed and undirected searches applied to undirected graphs.

Why do you need a separate undirected version of DFS, but don't need a special version of undirected BFS? What's wrong with running directed depth_first_search() on undirected graph? If there are some reasons — why the same reasons don't apply to breadth_first_search()?

In undirected_dfs() you have a color map for tracking edges, so the algorithm does not emit events for inverted edges. Why then don't you add undirected version of BFS with the same property? So less non_tree_edge would be emitted for inverted edges.

[qbit86]

Another question about the design of BFS. Why do you need all three events: non_tree_edge, gray_target, black_target? A pair of non_tree_edge_with_gray_target and non_tree_edge_with_black_target looks sufficient, isn't it?

And one more question, on naming. I've looked through a dozen of books on graph algorithms, and never met there a notion of “source” and “target” applying to endpoints of an edge; only “tail” and “head”. Why did you decide to call them so (which conflicts with conventional names for start and finish vertices of the path)?