0

So, I made the following code for DFS:

void dfs (graph * mygraph, int foo, bool arr[]) // here, foo is the source vertex
{
    if (arr[foo] == true)
        return;
    else
    {
        cout<<foo<<"\t";
        arr[foo] = true;
        auto it = mygraph->edges[foo].begin();
        while (it != mygraph->edges[foo].end())
        {
            int k = *it;
            if (arr[k] == false)
            {
                //cout<<k<<"\n";
                dfs(mygraph,k,arr);
                //cout<<k<<"\t";
            }
            it++;
        }
    }
    //cout<<"\n";
}

Now, I read up that in an undirected graph, if while DFS, it returns to the same vertex again, there is a cycle. Therefore, what I did was this,

bool checkcycle( graph * mygraph, int foo, bool arr[] )
{

    bool result = false;
    if (arr[foo] == true)
    {
        result = true;
    }
    else
    {
        arr[foo] = true;
        auto it = mygraph->edges[foo].begin();
        while (it != mygraph->edges[foo].end())
        {
            int k = *it;
            result = checkcycle(mygraph,k,arr);     
            it++;
        }
    }
    return result;
}

But, my checkcycle function returns true even if their is no cycle. Why is that? Is there something wrong with my function? There is no execution problem, otherwise I would have debugged, but their seems to be something wrong in my logic.

John Lui
  • 1,434
  • 3
  • 23
  • 37
  • Is `checkcycle` being called after `dfs`? Are doing proper clean up? – André Fratelli Jul 20 '15 at 21:07
  • No, they are seperate functions called from main using a switch case. It's not called after it or before it. After inserting the edges, I straight away call the `checkcycle` function. – John Lui Jul 20 '15 at 21:11

2 Answers2

2

Notice that your function doesn't quite do what you think it does. Let me try to step through what's happening here. Assume the following relationships: (1,2), (1,3), (2,3). I'm not assuming reflexibility (that is, (1,2) does not imply (2,1)). Relationships are directed.

  1. Start with node 1. Flag it as visited
  2. Iterate its children (2 and 3)
  3. When in node 2, recursively call check cycle. At this point 2 is also flagged as visited.
  4. The recursive call now visits 3 (DEPTH search). 3 is also flagged as visited
  5. Call for step 4 dies returning false
  6. Call for step 3 dies returning false
  7. We're back at step 2. Now we'll iterate node 3, which has already been flagged in step 4. It just returns true.

You need a stack of visited nodes or you ONLY search for the original node. The stack will detect sub-cycles as well (cycles that do not include the original node), but it also takes more memory.

Edit: the stack of nodes is not just a bunch of true/false values, but instead a stack of node numbers. A node has been visited in the current stack trace if it's present in the stack.

However, there's a more memory-friendly way: set arr[foo] = false; as the calls die. Something like this:

bool checkcycle( graph * mygraph, int foo, bool arr[], int previousFoo=-1 )
{
    bool result = false;
    if (arr[foo] == true)
    {
        result = true;
    }
    else
    {
        arr[foo] = true;
        auto it = mygraph->edges[foo].begin();
        while (it != mygraph->edges[foo].end())
        {
            int k = *it;

            // This should prevent going back to the previous node
            if (k != previousFoo) {
                result = checkcycle(mygraph,k,arr, foo);
            }

            it++;
        }
        
        // Add this
        arr[foo] = false;
    }
    return result;
}

I think it should be enough.

Edit: should now support undirected graphs. Node: this code is not tested

Edit: for more elaborate solutions see Strongly Connected Components

Edit: this answer is market as accepted although the concrete solution was given in the comments. Read the comments for details.

Community
  • 1
  • 1
André Fratelli
  • 5,920
  • 7
  • 46
  • 87
  • So, I should make a stack of nodes that I set true? – John Lui Jul 20 '15 at 21:19
  • The above will work for both undirected and directed graphs, alike? – John Lui Jul 20 '15 at 21:24
  • Well, it won't work with undirected graphs unless you are careful enough not to follow the relationship backwards. That is, if you travel from A to B, be sure not to go back to A from B immediately. Given that assumption I think it should work – André Fratelli Jul 20 '15 at 21:35
  • But that's something which will be handled by recursion, not by me. It will be great if you can suggest me a solution by which I can modify it for undirected graphs? – John Lui Jul 20 '15 at 21:37
  • Notice that this version discards cycles caused by direct relationships. This might or might not be desirable. – André Fratelli Jul 20 '15 at 21:43
  • Thank you for your extended help, but I am really sorry, it's not desirable. I guess I will have to implement it through some other logic. Thanks for the help though. However, any inputs as to how can I start implementing it using DFS because clearly, the above isn't working properly, – John Lui Jul 20 '15 at 21:45
  • Well, I expected it to work at a basic level, at least. As I mentioned in my last edit, maybe you need stronger algorithms, such as [Kosaraju's](https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm) – André Fratelli Jul 20 '15 at 21:47
  • Actually, I just found this: http://stackoverflow.com/questions/526331/cycles-in-an-undirected-graph?rq=1 – André Fratelli Jul 20 '15 at 21:48
  • Hey, thanks for the link. This will be a great help. Thanks! I am marking your answer as accepted because of your extended help. :) – John Lui Jul 20 '15 at 21:51
  • Well, in that case it seemed appropriate to include a note on the answer :) – André Fratelli Jul 20 '15 at 22:01
0

are all of the bools in arr[] set to false before checkcycle begins?

are you sure your iterator for the nodes isn't doubling back on edges it has already traversed (and thus seeing the starting node multiple times regardless of cycles)?

dufresnb
  • 135
  • 10