get all the paths between 2 nodes in a directed graph

Question

I am trying to get all the paths in a directed graph between two nodes. I have a problem with a cycle and I cannot find the reason. Here is my graph (taken from http://www.technical-recipes.com) :

The problem appears because of the [1,2] edge : 1->2 . If I remove it, I have no problems. In this particular test, I want all the paths from 2 to 5. I will provide the small code at the end.

Case 1 : the output when I do NOT have [1,2] :

//g.addEdge( 1, 2 );    
g.addEdge( 1, 3 );    
g.addEdge( 1, 4 );    
g.addEdge( 2, 1 );    
g.addEdge( 2, 4 );    
g.addEdge( 2, 3 );    
g.addEdge( 3, 5 );    
g.addEdge( 4, 5 );    
g.addEdge( 5, 3 ); 

The output is ok :

2 1 3 5    
2 1 4 5  
2 3 5  
2 4 5

Case 2 : I introduce g.addEdge( 1, 2 ); => the output is :

2 3 5 
2 4 5

So when the current node is 1 and is taking 2 as child it does not work. Note: when I erase visited[], visited[] is still containing 2 (that is introduced in main, and I think it should be there)...I think because of context saving.

My code is pretty small and it looks like this:

MAIN function

    Graph g(5);         //graph with 5 nodes
    std::vector<int> visitedmain;
    visitedmain.push_back(2);    //introduce the start node 2 in the vector

g.addEdge( 1, 2 );    //this is wrong 
g.addEdge( 1, 3 );    
g.addEdge( 1, 4 );    
g.addEdge( 2, 1 );    
g.addEdge( 2, 4 );    
g.addEdge( 2, 3 );    
g.addEdge( 3, 5 );    
g.addEdge( 4, 5 );    
g.addEdge( 5, 3 );  

g.DFS(5, visitedmain);    // 5 is the required (target) node

DFS function

void Graph::DFS(int required, std::vector<int>& visited) {
    int i, j;
    //the current node, where I am in recursivity
    int x = visited.back();  

    int ok = 1;

    for (i = 1; i <= n; i++) {
        //for all children
        if (isConnected(x, i)) { 
            //need this for ok, explanation down
            for (j = 0; j < visited.size(); j++) 
                    {
                if (i == visited[j])
                    ok = 0;
            }
            //if it is in the vector already, exit for
            if (!ok)  
                continue;

            ok = 1;
            //If I reached the target, I have the vector containing the nodes from the path
            if (i == required) { 
                //introduce the target node in the path
                visited.push_back(i); 

                for (j = 0; j < visited.size(); j++) {
                    //print the path
                    errs() << visited[j] << " "; 
                }
                errs() << "\n";
                //delete the vector. create one vector every time when traversing the graph
                visited.erase(visited.begin() + visited.size() - 1); 
                break;
            }
        }
    }
    //the case when I still have to traverse undiscovered nodes
    for (i = 1; i <= n; i++) { 
        //for all children
        if (isConnected(x, i)) { 

            for (j = 0; j < visited.size(); j++) {
                if (i == visited[j])
                    ok = 0;
            }
            //if it is already in the vector OR I reached the target, I exit the for
            if (!ok || i == required) 
                continue;
            ok = 1;
            //introduce the child in the vector
            visited.push_back(i); 
            //recursive for this child
            Graph::DFS(required, visited);  
            //delete the old vector
            visited.erase(visited.begin() + visited.size() - 1); 
        }
    }
}

Thank you for every suggestion !

Answer 1

Your logic regarding ok looks suspicious.

You set ok=1 at the start of the function, and after tests which will only pass if ok=1 already.

I would recommend setting ok=1 just before the for loops that set it to 0.

i.e. change

for(j=0; j<visited.size(); j++) 

to

ok=1;
for(j=0; j<visited.size(); j++) 

in both places where this occurs.