Finding a cycle path in directed graph

[gklempe27]

I am making a directed Graph class. I want find if there is any 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.

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.
What I have tried:

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

class Graph {
private:
    int V;
    list<int> *adj;
    bool isCyclicHelp(int v, bool visited[], bool *rs, vector<int> &path) const{
        if(visited[v] == false) {
            visited[v] = true;
            rs[v] = true;

            list<int>::iterator i;
            for(i=adj[v].begin(); i!=adj[v].end(); i++) {
                if(!visited[*i] && isCyclicHelp(*i, visited, rs, path)) {
                    path.push_back(*i);
                    return true;
                }
                else if(rs[*i]) {
                    return true;
                }
            }
        }
        rs[v] = false;
        path.pop_back();
        return false;
    }
public:
    Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }
    ~Graph() {

    }
    void addEdge(int v, int w) {
        if(v != w) {
            adj[v].push_back(w);
        }
    }
    bool cycle(vector<int> &path) const {
        bool *visited = new bool[V];
        bool *recStack = new bool[V];
        for(int i=0; i<V; i++) {
            visited[i] = false;
            recStack[i] = false;
        }

        for(int i=0; i<V; i++) {
            path.push_back(i);
            if(Graph::isCyclicHelp(i, visited, recStack, path)) {
                reverse(path.begin(), path.end());
                return true;
            }
            path.clear();
        }
        path.clear();
        return false;
    }
};

[JRManx]

@gklempe27,

PLEASE USE CODE TAGS (the <> formatting button to the right), when posting code!

Along with the proper indenting, it makes it easier to read your code, and thus also easier to respond to your post.

Tutorials on how to use code tags:

http://www.cplusplus.com/articles/jEywvCM9/
http://www.cplusplus.com/articles/z13hAqkS/

I've found the second link to be the most help.

Hint: You can hit "edit post", highlight your code and then press the <> formatting button.
Note: This will not automatically indent your code! That part is up to you!

I've found it's easiest to copy and paste pre-indented code directly from the IDE, that way it is already properly formatted.

You can use the "preview" button at the bottom to see how it looks.

Using Code Tags, @Handy Andy, from cplusplus.com

Also, what is your computer's operating system, and what IDE or compiler are you using?

Thanks!
max

[gklempe27]

My computer's operating system is Windows and IDE Eclipse

[keskiverto]

@agent max: I don't see what IDE has to do with this.

@gklempe27:

    Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }
    ~Graph() {

    }
    void addEdge(int v, int w) {
        if(v != w) {
            adj[v].push_back(w);
        }
    }

Two scary bits in this:
1. You leak memory. The dynamically allocated memory is never released. (Not to mention the lacking copy/move ctors/assignments.)
2. There is no test whether v and w are valid. what would happen in

Graph g(7);
g.addEdge( 42, 69 );

Lines 45-46 allocate memory too, but where is the delete []?

You do use std::vector already. You could use it more.

bool isCyclicHelp( int, bool [], bool *, vector<int>& ) const
Two array of bool arguments, yet with different syntax? Is that some hint to the reader?


There is no driver to compile and test this class. I would probably make isCyclicHelp() print out what it is doing. (Some prefer debugger for that.)

[seeplus]

L9 - 10 should be:

int V {};
list<int> *adj {};

The constructor becomes:

Graph(int V_) : V(V_), adj(new list<int>[V_]) {}

and the destructor becomes:

~Graph() {
    delete [] adj;
}

and until a copy constructor and operator= are provided, also have as public:

Graph(const Graph&) = delete;
Graph& operator=(const Graph&) = delete;

as per keskiverto's comment above - why are you allocating dynamic memory in L45 - 46 and never freeing it? Why dynamic memory and not a vector?