Re: [jgrapht-users] cycles in an undirected graph
Brought to you by:
barak_naveh,
perfecthash
Menu
▾
▴
Re: [jgrapht-users] cycles in an undirected graph
|
From: Joris K. <de...@gm...> - 2011-08-05 07:57:20
|
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 <ma...@cs...> 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 <de...@gm...> 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 : >> www.cs.sunysb.edu/~algorith/video-lectures/2007/lecture12.pdf >> >> br, >> >> Joris >> >> On Tue, Aug 2, 2011 at 6:17 PM, zara75 <con...@gm...> 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 >> > jgr...@li... >> > https://lists.sourceforge.net/lists/listinfo/jgrapht-users >> > > > > > -- > Azzam Maraee > Department of Computer Science > Ben-Gurion University > ISRAEL > ma...@cs... > 972-8-6428044 (o) > |
