Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight

Cycle in Directed Graph

by artist (Parson)
on Sep 21, 2005 at 01:09 UTC ( #493633=perlquestion: print w/replies, xml ) Need Help??
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.


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.

    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.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://493633]
Approved by sk
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (4)
As of 2017-04-28 06:03 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (519 votes). Check out past polls.