great work :-) -- Marco Speranza <marcospera...@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-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
