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

I have a directed graph with edges are colored with few different colors. I am looking for cycles in this graph, such that each edge in the cycle, should have different color. Looking for appropriate module.
--Artist

Replies are listed 'Best First'.
Re: Cycle in Directed Graph
by sk (Curate) on Sep 21, 2005 at 01:22 UTC

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.

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.

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.
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:
1. Does it work?
2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
Re: Cycle in Directed Graph
by jdporter (Canon) 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(NC), which isn't too bad.