Hm, as Ethan pointed out correctly you were asking for *all* cycles in
a graph. I should read more carefully! In that case, the problem is of
a completely different level and you won't be able to solve it with a
simple Depth first search as it is indeed an NP-complete problem. You
might want to check this article http://dx.doi.org/10.1137/0205007
from SIAM (you probably need university credentials to log in to that
website). At least jgraph hasnt any method to find *all* cycles in a
graph (feel free to add such a method though :) ).
Perhaps this discussion is usefull:
http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph
You might want to reconsider whether you really need to find *all*
cycles in a graph for your problem. Perhaps some less heavy approach
would be sufficient? Maybe you could find *a* cycle and remove one
edge such thereby breaking the cycle and repeat until you cannot find
cycles anymore (and possibly end up with a disconnected graph). I
haven't tested this nor seen this so I have no clue how well this
works . It probably will give you a lower bound on the number of
cycles.
br,
Joris
On Wed, Aug 3, 2011 at 11:03 AM, azzam <mari@...> wrote:
> Dear Joris,
> Thanks a lot about your reply
> Actually, I tried Googling how to find all cycles in graph (undirected),
> but I wondered if the jgraph package includes an implementation for this
> method. I think that there is such method for the directed graph. From your
> answer, I realized that there is no implementation for the undirected
> graph.
> I will read the attached link, and try to implement the method alone. From
> your answer, I think that this is not so difficult. :)
> Azzam
>
>
> On Wed, Aug 3, 2011 at 10:47 AM, Joris Kinable <deus87@...> wrote:
>>
>> Have you actually tried Googling how to find a cycles in a graph...
>> this usually helps a lot ;).
>>
>> Quick answer: run a depth first search on your node. (A depth first
>> search algorithm is included in the jgraph package). If the depth
>> first search algorithm re-encounters a node, then you know that there
>> is a cycle. Check for example these slides :
>> http://www.cs.sunysb.edu/~algorith/video-lectures/2007/lecture12.pdf
>>
>> br,
>>
>> Joris
>>
>> On Tue, Aug 2, 2011 at 6:17 PM, zara75 <consistency75@...> wrote:
>> > I need to find all cycles in an undirected graph, and all cycles passing
>> > from
>> > a given node /e/, also in an
>> > undirected graph.
>> >
>> > I would appreciate any help
>> >
>> >
>> > A.
>> >
>> >
>> > --
>> > View this message in context:
>> > http://jgrapht-users.107614.n3.nabble.com/cycles-in-an-undirected-graph-tp3219434p3219434.html
>> > Sent from the jgrapht-users mailing list archive at Nabble.com.
>> >
>> >
>> > ------------------------------------------------------------------------------
>> > BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA
>> > The must-attend event for mobile developers. Connect with experts.
>> > Get tools for creating Super Apps. See the latest technologies.
>> > Sessions, hands-on labs, demos & much more. Register early & save!
>> > http://p.sf.net/sfu/rim-blackberry-1
>> > _______________________________________________
>> > jgrapht-users mailing list
>> > jgrapht-users@...
>> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>> >
>
>
>
> --
> Azzam Maraee
> Department of Computer Science
> Ben-Gurion University
> ISRAEL
> mari@...
> 972-8-6428044 (o)
>
|