I am trying to write a program which uses the boost graph library to construct a graph from a text file and then perform certain algorithms of the user's choice on it. My code runs fine, but once boost::dijkstra_shortest_paths() or boost::prim_minimum_spanning_tree() finishes executing, the predecessor property for each vertex is set to that self-same vertex! It's like the algorithm runs without doing its job. I am rather unsure why this is happening, and was wondering if someone could shine some light on the issue.
Here is my program:
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <stack>
#include <vector>
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
using namespace boost;
using namespace std;
typedef adjacency_list_traits<vecS, vecS, undirectedS> GraphTraits;
typedef GraphTraits::vertex_descriptor vertex_descriptor;
struct EdgeData // property bundle for edges
{
double weight;
EdgeData(double someWeight)
: weight(someWeight) {};
};
struct VertexData // property bundle for vertices
{
string first_name;
int dist;
vertex_descriptor pred;
default_color_type color;
};
struct do_nothing_dijkstra_visitor : default_dijkstra_visitor {};
typedef adjacency_list<vecS, vecS, undirectedS, // graph type
VertexData, EdgeData> MyGraphType; // this is the bundled version
vertex_descriptor findVertex(const string& name, const MyGraphType& G) // utility for finding a vertex_descriptor for a name
{
bool found = false;
auto it = vertices(G).first;
vertex_descriptor vDescriptor = *it;
auto vNameMap = get(&VertexData::first_name, G);
while (!found)
{
if (vNameMap[vDescriptor] == name)
{
found = true;
break;
}
it++;
vDescriptor = *it;
}
return vDescriptor;
}
int main()
{
MyGraphType G;
char userInput = ' ';
bool isRunning = true;
string graphFile;
cout << "Enter the name of the file in which your graph data is stored: " << endl;
cout << "(Please be sure you have one space between each vertex name and between each piece of edge data)" << endl;
cin >> graphFile;
ifstream ifs(graphFile);
if (!ifs) // error if file not opened
{
cout << "Error! could not read graph file. Please exit program and try again." << endl;
}
else
{
G;
string line = "";
string vertexName = "junk"; // current vertex name
getline(ifs, line); // takes out the "Vertices:" line
getline(ifs, line); // line of vertex names
istringstream isstream(line); // create string stream to parse vertex names from
int i = 0; // counter variable
while (isstream >> vertexName) // get the vertex names from input stream
{
string vName;
if (vertexName.size() != 1 && vertexName[vertexName.size() - 1] == ',') // potentially remove comma
{
vName = vertexName.substr(0, (vertexName.size() - 1));
}
else
{
vName = vertexName;
}
vertex_descriptor vd = add_vertex(G); // add a vertex for the current name
G[i].first_name = vName; // give the vertex its name
i++; // increment counter
}
getline(ifs, line); // takes out the "Edges:" line
while (getline(ifs, line)) // get the graph's edges
{
string vertex2; // the two vertices for the edge
string vertex1;
double inWeight = 0.0; // the edge's weight
istringstream iss(line); // create a string stream to parse edge data from
iss >> vertexName; // get first vertex name from input
vertex1 = vertexName.substr(1, (vertexName.size() - 2)); // remove comma and '('
iss >> vertexName; // get second vertex name from input
vertex2 = vertexName.substr(0, (vertexName.size() - 1)); // lopp off comma
iss >> inWeight; // get the weight
auto e = add_edge(findVertex(vertex1, G), findVertex(vertex2, G), { inWeight }, G).first; // add the edge
}
}
ifs.close();
while (isRunning)
{
cout << "What would you like to do?\n" << endl;
cout << "1.) Calculate the shortest path between two vertices" << endl;
cout << "2.) Calculate the minimum spanning tree" << endl;
cout << "3.) Calculate shortest path to visit all vertices (Traveling Salesman Problem)" << endl;
cout << " note: Only works on completely connected graph" << endl;
cout << "4.) Exit the program\n" << endl;
cout << "Please enter the number that corresponds with your choice:" << endl;
cin >> userInput;
switch (userInput)
{
case '1':
{
string startVertex;
string endVertex;
stack<vertex_descriptor> predStack; // stack for storing predecessor names
cout << "Enter the name of the starting vertex: ";
cin >> startVertex;
cout << "\nEnter the name of the ending vertex: ";
cin >> endVertex;
cout << endl;
dijkstra_shortest_paths(G, findVertex(startVertex, G),
get(&VertexData::pred, G), get(&VertexData::dist, G),
get(&EdgeData::weight, G), identity_property_map(),
less<double>(), plus<double>(), numeric_limits<double>::infinity(), 0,
do_nothing_dijkstra_visitor(), get(&VertexData::color, G));
vertex_descriptor eVertex = findVertex(endVertex, G); // vertex_descriptor for ending vertex
vertex_descriptor sVertex = findVertex(startVertex, G); // vertex_descriptor for starting vertex
vertex_descriptor counter = get(&VertexData::pred, G, eVertex);
predStack.push(counter); // prime the stack
while (counter != sVertex) // push predecessors onto stack
{
counter = G[counter].pred;
predStack.push(counter);
}
cout << "The shortest path between " << startVertex << " and " << endVertex << " is: ";
while (!predStack.empty()) // print the path
{
cout << get(&VertexData::first_name, G, predStack.top()) << ", ";
predStack.pop();
}
cout << endVertex << endl; // print the ending vertex
system("pause");
break;
}
case '2':
{
vector<vertex_descriptor> predecessors(num_vertices(G));
prim_minimum_spanning_tree(G, *vertices(G).first, &predecessors[0],
/*get(&VertexData::pred, G),*/ get(&VertexData::dist, G),
get(&EdgeData::weight, G), identity_property_map(),
do_nothing_dijkstra_visitor());
cout << "\nThe Minimum Spanning tree contains these edges: " << endl;
for (auto vd : make_iterator_range(vertices(G)))
{
auto p = G[vd].pred;
if (G[vd].first_name != G[p].first_name)
{
cout << "(" << G[vd].first_name << ", " << G[p].first_name << ")" << endl;
}
}
system("pause");
break;
}
case '3':
{
cout << "This would perform the TSP calculation, only it hasn't been written yet." << endl;
break;
}
case '4':
{
//delete graph;
isRunning = false;
break;
}
default:
cout << "The wheel's spinning, but the hamster's dead! " << userInput << " is not a choice!" << endl;
}
}
return EXIT_SUCCESS;
}
In case it is important, I am using MS visual studio 2017 and boost version boost_1_67_0.
