You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Thomas Neidhart <th...@gmail.com> on 2012/03/01 21:26:57 UTC
[graph] Kosaraju's SCC algorithm
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
http://algowiki.net/wiki/index.php?title=Kosaraju%27s_algorithm
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: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [graph] Kosaraju's SCC algorithm
Posted by Marco Speranza <ma...@apache.org>.
great work :-)
--
Marco Speranza <ma...@apache.org>
Google Code: http://code.google.com/u/marco.speranza79/
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
>
> http://algowiki.net/wiki/index.php?title=Kosaraju%27s_algorithm
>
> 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: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org