[boost] [graph] Faster strong_components-implementation

Subject: [boost] [graph] Faster strong_components-implementation
From: Alexander Lauser (alxlaus_at_[hidden])
Date: 2014-08-22 08:43:11

Hi all,

reimplementing Tarjan's dfs-visitor used in Boost.Graph's algorithm to
compute strong components yielded a performance gain of about 15 to 20%
(for adjacency_list-graphs). The problem is that due to bug #10231 [1],
this implementation does not work with a current vanilla version of
Boost. (See below for some details explaining my changes and the reason
it is affected by the bug.)

Is there interest in the faster implementation?

If so, what's the best way to proceed? Wait until the bug is fixed and
then incorporate the changes in a pull request? Create a pull request
and hope that is not merged before the bug is fixed?

Btw, my feeling is that the bug's not too involved and I tried to fix it
myself. It seems that it is not even in Boost.Graph itself, but in
Boost.TTI (in the macro-depths of which I got lost).

Should I file a separate bug for Boost.TTI?

For the details: My implementation is a back-to-the-root-approach,
following the classical formulations of Tarjan's algorithm more closely.
The current implementation somewhat "simulates" edge events upon leaving
a vertex by an additional loop over all edges incident to the vertex.
This can be avoided by using finish_edge -- which suffers from the above
mentioned bug. (In addition to the performance-boost, I think it is also
more natural to implement Tarjan's algorithm using finish_edge.)

Cheers,
Alex

[1] https://svn.boost.org/trac/boost/ticket/10231