[boost] [graph] strong_components & depth_first_visit feature proposal

Subject: [boost] [graph] strong_components & depth_first_visit feature proposal
From: Alexander Lauser (alxlaus_at_[hidden])
Date: 2014-07-30 08:14:08

Hi all,

I am writing two minor extensions for Boost.Graph, making
strong_components and depth_first_visit more generic. This mail is to
assess interest in publishing these features.

* Question 1: What about extending strong_components to allow the user
to (optionally) hook into DFS-events?

The rationale for that is that when computing strong components, one may
also be interested in connecting paths between any two distinct vertices
in a component. With the ability to hook into the events, the paths can
be traced, using tree_edge and back_edge to store paths to/fro the root
of the component.

One may possibly even allow additional events with respect to the
discovery and finishing of components as well as the adding of vertices.
What do you think about that?

A technical question w.r.t the implementation of such a visitor: Why is
the name dispatching for the named parameters of strong_components done
"by hand" and not using the same facilities as depth_first_search? (I'm
quite new to Boost and most of its notions like named parameters, so I
may have missed something trivial. If so I beg to forgive the question.)

* Question 2: What about introducing a new (optional) event for
finish_tree_edge during a depth_first_visit? This event would be called
when backtracking a tree_edge.

Even though I cannot give a specific application where such an event
would be essential, I still think it's a event during a
depth-first-search that is natural enough to allow the user to hook in.
(N.b. that similar events finish_back_edge and
finish_forward_or_cross_edge would not make sense as they get always
called immediately after back_edge and
forward_or_cross_edge, respectively.)

* Another minor question: Why are not all events of a
DFS-visitor optional (like finish_edge is)? I think this would make
implementing a partial DFS-visitors easier (by not having to derive from
dfs_visitor in order to provide events that one is not interested in).

A problem in the implementation of this would be that there is currently
a bug (ticket 10231) with the current implementation that makes
finish_edge optional.

- Alex