Click here to Skip to main content
15,171,303 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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.So i guess it needs to be tydied up. (If others parts of my code are too simple, so I didn't include them)


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 anything else valid.

I can obviously do something like this:
if (path.end()[-2]==path.end()[-1]) path.pop_back();
but I don't like it and still I don't understand why this occurres .

What I have tried:

C++
Graph{
    private:
        int V;			// No. of vertices
        list<int> *adj; // Pointer to array containing adjacency lists
        ...
    };
          

    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;
    }
Posted
Updated 7-Jun-18 7:14am
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900