Menu
▾
▴
Re: [Jung-support] finding all cycles in a directed graph
|
From: Marcel S. <mar...@en...> - 2005-04-26 11:02:59
|
>> I am currently working on a problem related to cycles in a graph. >> What I need is a method to count all the cycles in a directed graph. >> At the moment, I don't necessarily need to generate all cycles - a >> simple count would do. However, generating all cycles would be a plus >> in the future. > > I suspect that one is about as simple as the other (that is, you > should be able to just add each one to a list as you identify it, as > easily as incrementing a counter). That's right - but the issue is not only simplicity, but rather speed. > You are correct: we have an algorithm that will identify the _weak_ > components (algorithms.cluster.WeakComponentClusterer), but not one > for the strong components. (We have a decent selection of algorithms, > but mostly those that the developers or contributors have needed for > something they've been working on, so there are a few odd holes.) > However, as I recall, the strong component algorithm is a pretty > straightforward algorithm. > > If you do write an implementation of either of these algorithms (the > cycle finder and the strong component finder), please let us know if > you'd be willing to donate them to JUNG. Yes. Peter Pachebo from the University of San Francisco was so kind to send me his implementation of a strong component algorithm, and I implemented the cycle finding algorithm around it. I also made an implementation of the Weinblatt algorithm, which works fine as long as the number of cycles does not increase +/- 1000. Otherwise, it's just too slow (it takes days to find > 100,000 cycles). Anyways, the Johnson algorithm solves that problem. So I'd be happy to donate the strong component algorithm and the johnson cycle algorithm, which I have to refactor both in order to use it within JUNG. Any helpful information on how to do that best? Best regards, Marcel ---------------------------------------------------------------- Marcel Salathe ETH Zuerich Ecology & Evolution ETH-Zentrum NW CH - 8092 Zuerich mar...@en... http://www.eco.umnw.ethz.ch/portraits/salathe/ Phone +41 1 632 7105 Fax +41 1 632 1271 ---------------------------------------------------------------- |
