graph

I want to find input-output paths for directed acyclic graph.I want to find if given graph (calling object) is a DAG, the vector rpt is populated such that:
rpt[u].npaths = number of io-paths passing through vertex u.
Recall: an IO path starts at an input vertex and ends at an output vertex.
I write this function.but it is not working and giving error.
this is .cpp file for that function.

// utility function for printing
// the found path in graph
/*void printpath(vector<vertax_label>& rpt)
{
int size = rpt.size();
for (int i = 0; i < size; i++)
cout << rpt[i] << " ";
cout << endl;
}
*/
// utility function to check if current
// vertex is already present in path
/*int isNotVisited(int x, vector<vertax_label>& rpt)
{
int size = rpt.size();
for (int i = 0; i < size; i++)
if (rpt[i] == x)
return 0;
return 1;
}

// uti lity function for finding paths in graph
// from source to destination
void findpaths(vector<vector<int> >&g, int src,
int dst, int v)
{
// create a queue which stores
// the paths
queue<vector<int> > q;

// path vector to store the current path
vector<int> path;
path.push_back(src);
q.push(path);
while (!q.empty()) {
path = q.front();
q.pop();
int last = path[path.size() - 1];

// if last vertex is the desired destination
// then print the path
if (last == dst)
printpath(path);

// traverse to all the nodes connected to
// current vertex and push new path to queue
for (int i = 0; i < g[last].size(); i++) {
if (isNotVisited(g[last][i], path)) {
vector<int> newpath(path);
newpath.push_back(g[last][i]);
q.push(newpath);
}
}
}
}*/

/* bool dag_num_paths(vector<vertex_label> & rpt) {
if(has_cycle())
return false;
// your code here...
//in
// create a queue which stores
// the paths
std::queue<int> q;

// path vector to store the current path
std::vector<int> rpt;
rpt.push_back(src);
q.push(rpt);
while (!q.empty()) {
rpt = q.front();
q.pop();
int last = rpt[rpt.size() - 1];

// if last vertex is the desired destination
// then print the path
if (last == dst)
//printpath(rpt);
dag_num_paths(vector rpt);
// traverse to all the nodes connected to
// current vertex and push new path to queue
for (int i = 0; i < g[last].size(); i++) {
if (isNotVisited(g[last][i], rpt)) {
vector<int> newrpt(rpt);
newrpt.push_back(g[last][i]);
q.push(newrpt);
}
}

return true;
}
Topic archived. No new replies allowed.