commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thomas Neidhart <thomas.neidh...@gmail.com>
Subject [graph] Kosaraju's SCC algorithm
Date Thu, 01 Mar 2012 20:26:57 GMT
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


Mime
View raw message