Fidning a cycle in a directed graph.

This is a discussion on Fidning a cycle in a directed graph. within the C++ Programming forums, part of the General Programming Boards category; Hi, I have to find a cycle in a directed graph. I thought about such algorithm: 1) Create a queue ...

  1. #1
    Registered User
    Join Date
    May 2005
    Posts
    76

    Fidning a cycle in a directed graph.

    Hi,
    I have to find a cycle in a directed graph. I thought about such algorithm:
    1) Create a queue Q.
    2) Mark all vertexes as they are in a cycle.
    2) Add to Q all vertexes which don't have an edge leading to another vertex (mark each vertex as it is not in a cycle).
    3) While Q is not empty:
    3.a) take a front element (let's say F) from Q.
    3.b) for all F predecessors decrease the number of vertexes which F's predeccesor lead. If the numer is <= 0 add to Q and mark this vertex as it is not in a cycle.

    Is it correct algorithm? For small examples it seems to be good but in some bigger graphs which I can't draw on paper it says that there is a cycle but for sure there is not.
    Thanks,
    apacz

  2. #2
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    This looks like a correct algorithm (if there are finitely many nodes). Are you implementing it exactly as you've described it? It would be even more correct if you used the word 'vertices.' :-)

    What you have written down is essentially the same algorithm as topological sort, which will visit every node if and only if there are no cycles. ('Topological sort' has an extra step, (3.c), that pushes F onto a list that gets returned.)

  3. #3
    Registered User
    Join Date
    May 2005
    Posts
    76
    Thanks for reply. Yes, I implemented it as I've described and really I have no clue what's wrong there - I'm working on it since yesterday and can't find the bug or what it is.

  4. #4
    Registered User
    Join Date
    May 2005
    Posts
    76
    Hm... Can I use this algorithm for directed multi graphs? Maybe becouse of that it doesn't work but from the logical point of view it should work ok.

    --
    I find an example for which this algorithm doesn't work properly.
    We have a graph with 6 vertices and 6 edges:
    A pari (a b) means that there is an edge from a to b (a->b):
    2 2
    1 2
    3 4
    4 2
    4 2
    2 6
    So at the beggining we add to Q vertex number 6 (it doesn't lead to any other vertex) and 5 (it is separated from the rest of the graph).
    We take a 6 from queue and check that 2 leads to 6. So we decrease the numer of vertices that 2 lead but it is still > 0. Queue is empty so we stop the algorithm.
    And in a 'cycle' we have 1 2 3 4 but there should be only 2. (2->2 and 2<-2).
    Last edited by apacz; 10-31-2005 at 05:50 AM.

  5. #5
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    The algorithm doesn't find cycles; it only finds if there exists a cycle.

    If you want some particular cycle, you can use a modification of depth-first transversal.

  6. #6
    Registered User
    Join Date
    May 2005
    Posts
    76
    Hi,
    I want to find which vertices are in a cycle - it doesn't matter if in different cycle or in the same - I just want to know if each vertex is in a cycle. Can you recommend me any algorithm for that ? I need it done in O(n). Btw... What is exactly "depth-first transversal" ?
    Regards.

  7. #7
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Exactly what information do you want returned by the algorithm? And what do you mean by 'n'?

  8. #8
    Registered User
    Join Date
    May 2005
    Posts
    76
    I have a graph which consist n vertices and an array bool cycle[n] and I want algorithm to fill that array of cycle[x]=1 if and only if vertex is in a cycle.
    Regards.

  9. #9
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Okay.

    Step 1. Run the algorithm posted above.
    Step 2. Reverse the direction of all the remaining edges in the graph (that don't point to or from marked nodes).
    Step 3. Run the algorithm posted above with whatever nodes are left.

    The remaining unmarked nodes are all part of some cycle.

    Note that you really shouldn't implement the algorithm this way. IMO, your graph datastructure is best designed so that from a given node, you can immediately see incoming and outgoing edges and iterate through them in O(I+O) time, where I+O is the indegree and outdegree of that node. If this is the case, then there's no need for step 2 -- you can implement step three with a slightly different algorithm (possibly calling the same function or entering the same loop that performs step one, only with a different value for some boolean flag).

    (If you actually perform step 2, reversing the direction of all remaining edges, the algorithm takes O(N+E) time, where E is the number of edges, and that can be as large as O(N^2). For some algorithms, this is unavoidable, and O(N+E) is considered linear time. But cycle finding can be done more quickly.)
    Last edited by Rashakil Fol; 10-31-2005 at 03:38 PM.

  10. #10
    Registered User
    Join Date
    May 2005
    Posts
    76
    Thank you very much for such comprehensive anwer. Now I got it all .

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 08:55 PM
  2. How to use C++ graphs?
    By eur0dad in forum C++ Programming
    Replies: 4
    Last Post: 10-14-2006, 12:37 PM
  3. Help w/ graph as adjacency matrix
    By ac251404 in forum C++ Programming
    Replies: 4
    Last Post: 05-09-2006, 11:25 PM
  4. determining a path through the graph
    By Mist in forum C Programming
    Replies: 2
    Last Post: 02-27-2005, 12:21 PM
  5. Minimize crossing edges in undirected graph
    By Shiro in forum C Programming
    Replies: 0
    Last Post: 12-26-2001, 04:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21