Cycle in Directed Graph

artist has asked for the wisdom of the Perl Monks concerning the following question:

Replies are listed 'Best First'.
Re: Cycle in Directed Graph by sk (Curate) on Sep 21, 2005 at 01:22 UTC
How about Graph? Relevant parts from the document - `has_a_cycle $g->has_a_cycle Returns true if the graph has a cycle, false if not. find_a_cycle $g->find_a_cycle Returns a cycle if the graph has one (as a list of vertices), an e +mpty list if no cycle can be found. Note that this just returns the vertices of a cycle: not any parti +cular cycle, just the first one it finds. A repeated call might find +the same cycle, or it might find a different one, and you cannot call + this repeatedly to find all the cycles.` [download] Update: I am looking for cycles in this graph I hope you are not trying to find out "all" cycles in the graph which is NP-complete.	[reply] [d/l] [select]
Re^2: Cycle in Directed Graph by cbrandtbuffalo (Deacon) on Sep 21, 2005 at 17:56 UTC
In my experience with the Graph module in one script, the first cycle it found was always the same one. It was correct, but I couldn't get it to find other cycles unless I removed that one. If you just want one cycle, you should be OK.	[reply]
Re: Cycle in Directed Graph by dragonchild (Archbishop) on Sep 21, 2005 at 02:18 UTC
sk's answer is technically correct. However, my experiences has been that one very rarely has a completely generic graph. Usually, there's additional information about how the graph is built that can remove the NP-completeness from a find_all_cycles() function. A few items to look for could be: You don't have any edges that loopback to the same vertex. You can guarantee either an even or odd number of edges leading into or out of every vertex. You can break your graph up into sub-graphs where any cycles cannot contain vertices in more than one sub-graph. My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]
Re: Cycle in Directed Graph by jdporter (Paladin) on Sep 21, 2005 at 13:52 UTC
Given your constraints, I might be inclined to try going about it the other way: find all paths that have no more than one edge of any color, and check each one to see if it is (or contains) a cycle. Given `C` colors, and about `N` edges of each color, the number of edge sets to consider is `O(N^C)`, which isn't too bad.	[reply] [d/l] [select]