Hello all,
I am having difficulties implementing a function checking if the path exists from one node to another in a graph. In my way of thinking it should simply be a modification of either a breadth or depth first traversal where the City keys (yes, traveling salesman problem) are passed in. I typecast the city objects to Vertex objects in order to hopefully allow for comparison. The isReachable is called from main by
CODE
for(i = 1; i <= g.size(); i ++)
{
for(j = 1; j <= g.size(); j++)
{
try
{
g.isReachable(City(j, " "), City(i, " "));
wt = 1;
}
catch(GraphException e)
{
wt = 0;
}
cout << setw (4) << wt << " ";
}
cout<<endl;
}
break;
*********************************************
CODE
bool Graph<T>::isReachable(T fromKey, T toKey) const
{
Vertex<T>* walkPtr;
Vertex<T>* toPtr;
Queue<Vertex<T>*> queue;
Edge<T>* edgeWalk;
Vertex<T>* tmp;
if (isEmpty())
return 0;
toPtr = (Vertex<T> *) &toKey;
walkPtr = (Vertex<T> *) &fromKey;
walkPtr = first;
while (walkPtr != NULL)
{
walkPtr->processed = 0;
walkPtr = walkPtr->pNextVertex;
}
walkPtr = first;
while (walkPtr != NULL)
{
if (walkPtr->processed < 2)
{
if (walkPtr->processed < 1)
{
queue.enqueue(walkPtr);
walkPtr->processed = 1;
}
}
while (!queue.isEmpty())
{
try
{
tmp = queue.dequeue();
//visit(tmp->data);
tmp->processed = 2;
edgeWalk = tmp->pEdge;
while (edgeWalk != NULL)
{
toPtr = edgeWalk->destination;
if(toPtr == walkPtr)
return 1;
if (toPtr->processed == 0)
{
toPtr->processed = 1;
queue.enqueue(toPtr);
}
edgeWalk = edgeWalk->pNextEdge;
}
}
catch(QueueException e)
{
cerr<<e.what();
exit(1);
}
}
walkPtr = walkPtr->pNextVertex;
}
The code compiles properly but I am unable to generate any paths. I use Totalview as a debugger and it seems that everything is going through properly.
Any suggestions would be appreciated.
26 Mar, 2006 - 05:03 PM
| 