[graph] strong_components & depth_first_visit feature proposal
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
On 30 July 2014 22:14, Alexander Lauser <alxlaus@gmx.de> wrote:
* 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).
Have you tried deriving from default_dfs_visitor? Jeremy
* 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).
Have you tried deriving from default_dfs_visitor?
Yes, but why only make finish_edge optional? I think it would make user-code (slightly) clearer if all events were optional. It's no big deal, of course, and that's why it's a minor question. Alex PS: For the background, I'm quite new to Boost and for me it is somewhat arbitrary that everything is mandatory but finish_edge. The reason, however, seems to be historical: I recently saw that, at least in Boost version <= 1.39, there was no finish_edge-event.
participants (2)
-
Alexander Lauser -
Jeremy Murphy