Re: [jgrapht-users] cycles in an undirected graph From: Joris Kinable - 2011-08-05 07:57 ```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 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 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 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) > ```
 Re: [jgrapht-users] cycles in an undirected graph From: Joris Kinable - 2011-08-03 08:47 ```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 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 > ```
 Re: [jgrapht-users] cycles in an undirected graph From: Joris Kinable - 2011-08-05 07:57 ```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 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 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 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) > ```