Printing all paths between two nodes in a graph ( recursive method )

Graph is defined as follows

std::map<T, std::set<T> > graph;

Following is the way to print all the paths between two nodes in a graph.

template < class T>
void print_all_path(T src, T dest ) { 
    std::vector<T> visited;
    visited.push_back(src);
    compute_all_paths(visited,dest);
}
template < class T>
void print_all_path(T src, T dest ) { 
    std::vector<T> visited;
    visited.push_back(src);
    compute_all_paths(visited,dest);
}
template < class T>
void print_all_path(std::vector<T>& visited,  T dest ) {  
    T back           = visited.back();    
    std::set<T> adj_list = graph.find(back)->second;

    for ( std::set<T>::iterator itr = adj_list.begin();  itr != adj_list.end(); ++itr )  {  
        if ( std::find(visited.begin(), visited.end(), *itr) != visited.end())
            continue;
        if (*itr == dest) {
            visited.push_back( *itr );    
            std::copy(visited.begin(),visited.end(),std::ostream_iterator<T>(std::cout," "));
            std::cout << std::endl;  
            visited.erase( visited.begin() + (visited.size() - 1));    
            break;
        }
    }  
    for ( std::set<T>::iterator itr = adj_list.begin();  itr != adj_list.end();  itr++ )  {  
        if ( std::find(visited.begin(), visited.end(), *itr) != visited.end() || *itr == dest ) 
            continue;
        visited.push_back( *itr );    
        print_all_path(visited, dest );            
        visited.erase( visited.begin() + (visited.size() - 1));  
    }  
}  
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s