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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
