commons-dev mailing list archives

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

--
Marco Speranza <marcosperanza@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


Mime
View raw message