Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

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.

--Artist

Comment on Cycle in Directed Graph
Download Code
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?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://493633]
Approved by sk
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (8)
As of 2014-09-22 09:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (186 votes), past polls