commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Marco Speranza <>
Subject Re: [graph] Kosaraju's SCC algorithm
Date Thu, 01 Mar 2012 21:18:51 GMT
great work :-)

Marco Speranza <>
Google Code:

Il giorno 01/mar/2012, alle ore 21:26, Thomas Neidhart ha scritto:

> Hi,
> I have checked in my version of Kosaraju's strongly connected components
> algorithm. It is a first version and I would be glad if someone can do a
> review.
> The implementation is roughly based on
> but the search has been implemented in an iterative manner instead of
> the outlined recursive variant (which is stupid anyway in the case of
> graphs, as this can quickly lead to StackOverflowExceptions imho).
> The interface for SccAlgorithmSelector has been updated, so you can call
> the algo in two different ways:
>    Set<V> applyingKosarajuSharir( V source );
>    Set<Set<V>> applyingKosarajuSharir();
> to either get the Set of SCCs for one vertex, or the Set of Sets of SCCs
> for the whole graph.
> The unit test has been updated too, and runs through this time (feel
> ashamed ;-)
> Currently there are two helper methods for the algorithm that reside in
> the same DefaultSccAlgorithmSelector class, which may be better
> offloaded to an algorithm specific auxiliary class to reduce complexity.
> The currently existing KosarajuSharirVisitHandler is not used at the
> moment due to the problems described in the other thread wrt the current
> visitor implementation, but has been kept at the moment. Maybe in the
> future we can use a more generic approach.
> Thomas
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message