shelton22 0 Newbie Poster

Hi Friends!
I have tried to find all possible paths between two nodes;

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include "fstream"
#define max_edges 16
#define MAX_NODES 5

using namespace std;

bool isadjacency_node_not_present_in_current_path(int node,vector<int>pathway);
int findpaths(int source ,int target );
void display_all_paths_map();

vector<vector<int> >GRAPH(100);

vector<int>pathway;

map<int,vector<int>> allpathsmap; 
map<int,vector<int>>:: iterator itapm; 
typedef pair<int,vector<int>> pairapm;

int main()
{
int origin,destin,source,dest,l_id;

ifstream file1 ("Link_ID.txt");
if (! file1.is_open())
        { cout << "Error opening file Link_ID.txt"; } //did not include 'return'

for(int i=1;i<=max_edges;i++)
            {
            file1 >>origin>>destin>>l_id;
            GRAPH[origin].push_back(destin);
            }


        cout<<"(source, dest)\n";
        cin>>source>>dest;

        findpaths(source,dest);

        display_all_paths_map();

file1.close();

    return 0;
}

//ADJACENCY NODE NOT PRESENT IN CURRENT PATH
bool isadjacency_node_not_present_in_current_path(int node,vector<int>pathway)
{
    for(unsigned int i=0;i<pathway.size();++i)
    {
        if(pathway[i]==node)
        return false;
    }
    return true;
}

//FINDS PATHS
int findpaths(int source ,int target )
{
    int mykey=1;
    pathway.push_back(source);
    queue<vector<int> >q;
    q.push(pathway);

    while(!q.empty())
    {
        pathway=q.front();
        q.pop();

        int last_nodeof_path=pathway[pathway.size()-1];
        if(last_nodeof_path==target)
        {
            allpathsmap.insert(pairapm(mykey++, pathway));
        }

        for(unsigned int i=0;i<GRAPH[last_nodeof_path].size();++i)
        {
            if(isadjacency_node_not_present_in_current_path(GRAPH[last_nodeof_path][i],pathway))
            {
                vector<int>new_path(pathway.begin(),pathway.end());
                new_path.push_back(GRAPH[last_nodeof_path][i]);
                q.push(new_path);
            }
        }
    }
    return 1;
}

//DISPLAY ALL PATHS IN MAP ALLPATHMM
void display_all_paths_map()
{
    for(itapm=allpathsmap.begin(); itapm!=allpathsmap.end(); ++itapm)
    {
        cout << endl << itapm->first <<" => ";
        for(size_t n=0; n<(*itapm).second.size(); ++n)
        {
            cout << itapm->second[n] <<" ";
        }
    }
}

This code works fine at once.

But, when I try this for more than one time using loop as,

for(int i=0;i<3;i++)
{
        cout<<"(source, dest)\n";
        cin>>source>>dest;

        findpaths(source,dest);

    display_all_paths_map();
}

it prints the path's previous source and destination paths.

Can any one fix this?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.