Finding Cycle in directed graph misbehavior

[asder]

I am making a directed Graph class. I want find if there is any Euler Cycle and update a vector with it's path accordingly. My Function some times work but others add two times the last edge of the path.

Graph{
    private:
        int V;			// No. of vertices
        list<int> *adj; // Pointer to array containing adjacency lists
        isCyclicUtil(int v, bool visited[], bool *recStack, vector<int> &path) const
        ...
     public:
        bool Graph::cycle(vector<int> &path) const; 
    };

.

 bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack, vector<int> &path) const {
        if (visited[v] == false) {
            // Mark the current node as visited and part of recursion stack
            visited[v] = true;
            recStack[v] = true;
    
            // Recur for all the vertices adjacent to this vertex
            list<int>::iterator i;
            for (i = adj[v].begin(); i != adj[v].end(); ++i) {
                if (!visited[*i] && isCyclicUtil(*i, visited, recStack, path)){
                    path.push_back(*i);
                    return true;}
                else if (recStack[*i]){
                    path.push_back(*i);
                    return true;}
            }
        }
        recStack[v] = false; // remove the vertex from recursion stack
        path.pop_back();
        return false;
    }
    
    bool Graph::cycle(vector<int> &path) const {
        // Mark all the vertices as not visited and not part of recursion stack
        bool *visited = new bool[V];
        bool *recStack = new bool[V];
        for (int i = 0; i < V; i++) {
            visited[i] = false;
            recStack[i] = false;
        }
        // Call the recursive helper function to detect cycle in different DFS trees
        for (int i = 0; i < V; i++){
            path.push_back(i);
            if (isCyclicUtil(i, visited, recStack, path)) {
                reverse(path.begin(),path.end());
                //path.pop_back();
                return true;
            }
            path.clear();
        }
        path.clear();
        return false;
    }

Example:
having a Graph with these paths

0->1, 0->2, 1->2, 2->3, 3->4, 4->0, 4->6, 1->5, 5->6

should set the vector to `[0 2 3 4 ]` or somethings else valid

[tpb]

Your code is based on this: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/

Notice in the code that recStack contains the information about which nodes make up the cycle but not the order. If you make recStack int instead of bool and set it to the current recursion depth (with maybe -1 meaning that the vertex hasn't been visited) then you can recover the order from it and your path variable would be redundant.

[asder]

@tpb thanks for your response , I didn't understood what benefit i will have if i know the depth. I thnink the problems occurs when It fails to find a path on an edge and finds it next( min depth 2)

Also I think `path.pop_back();` Causes some unexpected behavior

[tpb]

I haven't tested this, but I think it should be more like this:

bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack, vector<int> &path) const {
    if (visited[v] == false) {
        // Mark the current node as visited and part of recursion stack
        visited[v] = true;
        recStack[v] = true;

        // Recur for all the vertices adjacent to this vertex
        list<int>::iterator i;
        for (i = adj[v].begin(); i != adj[v].end(); ++i) {
            if (!visited[*i]) {
                path.push_back(*i);
                if (isCyclicUtil(*i, visited, recStack, path))
                    return true;
            }
            else if (recStack[*i])
                return true;
        }
    }
    recStack[v] = false; // remove the vertex from recursion stack
    path.pop_back();
    return false;
}

My point about recStack is that if you stored the recursion depth instead of just true in it, you could use it to print the path, so path is kind of redundant.

[asder]

I if remove push_back on the else if it skips some edges