編集済み - 12/03/12 @ 1:05 AM PST
次のようにコードを編集しました。ただし、まだパスを返すことができません。
繰り返しますが、このコードは、ユーザーが指定した開始頂点と距離を使用してパスを計算するものです。プログラムは、指定されたデータに一致する適切なパスをすべて返します。
これまでの私のコードは次のとおりです。
vector<vector<Vertex>> Graph::FindPaths(Graph &g, int startingIntersection, float distanceInMiles)
{
/* A vector which contains vectors which will contain all of the suitable found paths. */
vector<vector<Vertex>> paths;
/* Create an empty set to store the visited nodes. */
unordered_set<int> visited;
/* Vector which will be used to the hold the current path. */
vector<Vertex> CurrentPathList;
/* Will be used to store the currerntVertex being examined. */
Vertex currentVertex;
/* Will be used to store the next vertex ID to be evaluated. */
int nextVertex;
/* Will be used to determine the location of the start ID of a vertex within the VertexList. */
int start;
/* Stack containing the current paths. */
stack<Vertex> currentPaths;
/* CurrentPathDistance will be used to determine the currernt distance of the path. */
float currentPathDistance = 0;
/* The startingIntersection location must be found within the VertexList. This is because there is
* no guarantee that the VertexList will hold sequential data.
*
* For example, the user inputs a startingIntersection of 73. The Vertex for intersection #73 may
* be located at the 20th position of the VertexList (i.e. VertexList[20]). */
start = g.FindStartingIntersection(g, startingIntersection);
/* Push the startingIntersection onto the stack. */
currentPaths.push(g.VertexList[start]);
/* Continue to iterate through the stack until it is empty. Once it is empty we have exhaused all
* possible paths. */
while(!currentPaths.empty())
{
/* Assign the top value of the stack to the currentVertex. */
currentVertex = currentPaths.top();
/* Pop the top element off of the stack. */
currentPaths.pop();
/* Check to see if we are back to the startingIntersection. As a note, if we are just starting, it will
* put the startingIntersection into the paths. */
if(currentVertex.id == startingIntersection)
{
/* Add currentVertex to a list. */
CurrentPathList.push_back(currentVertex);
/* Find the current path distance. */
currentPathDistance = FindPathDistance(g, CurrentPathList);
/* Check the currentPathDistance. If it is within +/- 1 mile of the specified distance, then place
* it into the vector of possible paths. */
if((currentPathDistance + 1 >= distanceInMiles) && (currentPathDistance - 1 <= distanceInMiles))
{
paths.push_back(CurrentPathList);
}
}
else /* The ending vertex was not the user specified starting vertex. */
{
/* Remove all elements from the stack. */
while(!currentPaths.empty())
{
currentPaths.pop();
}
}
nextVertex = FindUnvisitedNeighbor(g, currentVertex, visited);
// repeat while current has unvisited neighbors
while(nextVertex != -1)
{
/* Find the new starting vertex. */
start = g.FindStartingIntersection(g, nextVertex);
/* Push the startingIntersection onto the stack. */
currentPaths.push(g.VertexList[start]);
/* Push the next vertex into the visted list. */
visited.insert(nextVertex);
nextVertex = FindUnvisitedNeighbor(g, currentVertex, visited);
}
}
/* Return the vector of paths that meet the criteria specified by the user. */
return paths;
私のコードFindingUnvistedNeighbor()は次のとおりです。
int FindUnvisitedNeighbor(Graph &g, Vertex v, unordered_set<int> visited)
{
/* Traverse through vertex "v"'s EdgeList. */
for(int i = 0; i + 1 <= v.EdgeList.size(); i++)
{
/* Create interator to traverse through the visited list to find a specified vertex. */
unordered_set<int>::const_iterator got = visited.find(v.EdgeList[i].intersection_ID_second);
/* The vertex was not found in the visited list. */
if(got == visited.end())
{
return v.EdgeList[i].intersection_ID_second;
}
}
return -1;
}