Find all the paths between two nodes in a graph

Question

Following is how my graph is defined.

std::map< std::string, std::set<std::string> > g_db;

and Following is how I have written function to compute all the paths between two nodes, based on some of the previous question on this site.

void compute_all_paths(std::vector<std::string>& visited,  std::string& dest ) {  
    std::string back           = visited.back();    
    std::set<std::string> adj_stations = g_db.find(back)->second;

    for ( std::set<std::string>::iterator itr = adj_stations.begin();  itr != adj_stations.end(); ++itr )  {  
        if ( std::find(visited.begin(), visited.end(), *itr) != visited.end())
            continue;
        if (*itr == dest) {
            visited.push_back( *itr );    
            for ( std::vector<std::string>::size_type idx = 0; idx < visited.size(); idx++ ){  
                std::cout << visited[idx] << " ";  
            }
            std::cout << std::endl;  
            visited.erase( visited.begin() + (visited.size() - 1));    
            break;
        }
    }  
    for ( std::set<std::string>::iterator itr = adj_stations.begin();  itr != adj_stations.end();  itr++ )  {  
        if ( std::find(visited.begin(), visited.end(), *itr) != visited.end() || *itr == dest ) 
            continue;
        visited.push_back( *itr );    
        compute_all_paths(visited, dest );            
        visited.erase( visited.begin() + (visited.size() - 1));  
    }  
}

My graph is very huge, this function is crashing with huge list of calls to recursive function with the following message:

Unhandled exception at 0x7c812afb in Railways.exe: Microsoft C++ exception: std::bad_alloc at memory location 0x00033748

For small graph this works very well but not for huge graph.

Can anybody help me to find the issue.

What are you trying to achieve? Are you trying to find an optimum path? — Andrew Shepherd, Dec 14 '11 at 10:25
@Andrew Shepherd : I want to find all possible paths between the two nodes. — Avinash, Dec 14 '11 at 10:27
Consider `using namespace std;` *(or at least the individual classes like `using std::set;`, `using std::string;`)*. It reduces clutter when trying to absorb code samples like this. — HostileFork says dont trust SE, Dec 14 '11 at 10:27
@Avinash: Do you get any message, or does it just stop? What exactly happens when it crashes? — Björn Pollex, Dec 14 '11 at 10:28
@Björn Pollex : I get following error during running through debugger Unhandled exception at 0x7c812afb in Railways.exe: Microsoft C++ exception: std::bad_alloc at memory location 0x00033748.. — Avinash, Dec 14 '11 at 10:30
Your program is running out of memory. You should try to profile the memory-usage, and see if you can reduce it. — Björn Pollex, Dec 14 '11 at 10:32

score 4 · Accepted Answer · answered Dec 14 '11 at 10:28

4

Too many levels of recursivity can cause a stack overflow crash. That's why recursivity is not well suited for large data sets.

But all recursive calls can be reduced to loops. You should try removing recursive calls and replace them with loops.

answered Dec 14 '11 at 10:28

Luchian Grigore

253,575
64
457
625

is there an iterative way to find all possible paths in a graph. – Avinash Dec 14 '11 at 10:36
1

Yes - http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration – Luchian Grigore Dec 14 '11 at 10:37
1

@Avinash: You are getting a `bad_alloc` rather than a stack-overflow. I don't think recursion is the problem - you simply don't have enough memory. – Björn Pollex Dec 14 '11 at 10:38
@BjörnPollex agreed, but he only edited the answer after I had answered the question. – Luchian Grigore Dec 14 '11 at 10:51

Find all the paths between two nodes in a graph

1 Answers1