3

Given the following depth-first search, why does the check if(Parent[currVertex] != successorVertex) in ProcessEdge method detect a cycle? This code follows the algorithm given in the book Algortim Design Manual by S.Skiena. It is possible that the check is a typo and is meant to be if(Parent[successorVertex] != currVertex). Please ask for any clarification. I'm really stuck at this.

    public void Search(int start)
    {
        /* NOTE: the differences from BFS are: this uses a stack instead of a queue AND this maintains 'time' variable */
        Stack<int> s = new Stack<int>();
        int currVertex;
        int successorVertex;
        int time = 0;

        s.Push(start);

        Discovered[start] = true;

        while (s.Count != 0)
        {
            currVertex = s.Pop();
            // time increments every time we enter a node (when discovered) and every time we exit a node (when processed_late, i.e. when all its neighbours have been processed)
            time++;
            EntryTime[currVertex] = time;

            ProcessVertexEarly(currVertex);
            Processed[currVertex] = true;

            for (int i = 0; i < Graph.Vertices[currVertex].Count; i++)
            {
                successorVertex = Graph.Vertices[currVertex][i].Y;
                if (!Processed[successorVertex] || Graph.IsDirected)
                {
                    ProcessEdge(currVertex, successorVertex);
                }
                if (!Discovered[successorVertex])
                {
                    s.Push(successorVertex);
                    Discovered[successorVertex] = true;
                    Parent[successorVertex] = currVertex;
                }
            }
            // time increments every time we enter a node (when discovered) and every time we exit a node (when processed_late, i.e. when all its neighbours have been processed)
            time++;
            ExitTime[currVertex] = time;
            ProcessVertexLate(currVertex);
        }
    }

    private void ProcessEdge(int currVertex, int successorVertex)
    {
        if(Parent[currVertex] != successorVertex) // then we've found a cycle
        {
            /* Found cycle*/
        }
    }

UPDATE

Found correction for this code in errata http://www.cs.sunysb.edu/~skiena/algorist/book/errata. See (*) Page 173, process_edge procedure -- the correct test should be

if (discovered[y] && (parent[x] != y)) { /* found back edge */

But will that detect cycles?? The if check will never pass because in DFS method, process_edge is only called when discovered[y] == false.

1
  • Re your update: Skiena's dfs calls process_edge if y is not discovered or not processed. Vertices are not marked processed until every edge leaving them are explored. Commented Aug 26, 2013 at 12:17

1 Answer 1

1

The code you posted has significant differences compared to Skiena's original: bfs-dfs.c and findcycle.c and the rest. Skiena's code is buggy (try the graph 3 2 1 2 2 3, a two-edge path), so perhaps the person who transliterated it into Java attempted some repairs. Unfortunately, the repaired version appears to be buggy as well, though I can't be sure without a complete program.

I believe that the intent of the line you highlighted was as follows. For depth-first search in undirected graphs, there are two types of edges, tree and back. The graph has a cycle if and only if there exists a back edge. Now, the representation of undirected graphs chosen by Skiena is to store each undirected edge as two directed arcs, one in each direction. If we use depth-first search to detect cycles in this directed graph, then the length-two cycles consisting of the two directed arcs corresponding to a single undirected edge are reported in error as cycles. As written, the check ensures that a candidate back arc y->x is not the reverse of a tree arc x->y.

Sign up to request clarification or add additional context in comments.

8 Comments

Thanks. Is the graph you mentioned above to be interpreted as: vertex 0 is connected to vertex 3, vertex 1 to vertex 2, vertex 2 to vertex 1 and so on?
Also, can you recommend a better way to store a graph? Thanks
@bytefire 3 vertices, 2 edges, first edge 1-2, second edge 2-3. The problem with Skiena's code is that it calls process_edge on the tree edges.
@bytefire Skiena's representation is not a bad way to store a simple undirected graph.
I see now! In an undirected graph without cycles, there will be at most one parent to any vertex. When processing the edge the second time round (i.e. reverse arc), if parent of starting vertex isn't the same as ending vertex then we have a cycle. Thanks for your help. Btw, I translated the code from C to C# but didn't use the recursive version in the book. I replaced the queue in the BFS code with stack. Haven't tested it yet so probably has other bugs.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.