Парсинг очень привередливый и не проверяет на какие-либо ошибки.Что еще хуже, findVertex будет делать «что угодно», когда будет искать имя, которое не существует (например, если синтаксический анализ прошел неправильно и он ищет пустую строку).Если вам повезет, это приведет к сбою.
Если вы отладите программу (или добавите трассировку, как я), вы можете обнаружить, что на всех ваших ребрах будут добавлены неправильные вершины.
Кроме того, ваше свойство dist имеет значение int, которое не может представлять указанное вами infinity.
Исправляя их, я смог, по крайней мере, запустить первый алгоритм:
Live On Coliru
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <boost/config.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/property_map/property_map.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;
double 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;
}
std::cout << "Found " << vDescriptor << " for " << std::quoted(name) << "\n";
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 {
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
std::cout << "Debug: " << std::quoted(vName) << " --> " << vd << "\n";
}
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
std::cout << "Parsing " << std::quoted(line) << " into edge (" << vertex1 << ", " << vertex2 << ", " << inWeight << ")\n";
auto e = add_edge(findVertex(vertex1, G), findVertex(vertex2, G), { inWeight }, G).first; // add the edge
}
boost::print_graph(G, get(&VertexData::first_name, G));
}
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;
}
С input.txt:
Vertices:
a b c d
Edges:
(a, b, 1)
(b, c, 2)
(b, d, 4)
(c, d, 1)
And input "input.txt 1 ad 4 ", печать:
Enter the name of the file in which your graph data is stored:
(Please be sure you have one space between each vertex name and between each piece of edge data)
Debug: "a" --> 0
Debug: "b" --> 1
Debug: "c" --> 2
Debug: "d" --> 3
Parsing "(a, b, 1)" into edge (a, b, 1)
Found 0 for "a"
Found 1 for "b"
Parsing "(b, c, 2)" into edge (b, c, 2)
Found 1 for "b"
Found 2 for "c"
Parsing "(b, d, 4)" into edge (b, d, 4)
Found 1 for "b"
Found 3 for "d"
Parsing "(c, d, 1)" into edge (c, d, 1)
Found 2 for "c"
Found 3 for "d"
a <--> b
b <--> a c d
c <--> b d
d <--> b c
What would you like to do?
1.) Calculate the shortest path between two vertices
2.) Calculate the minimum spanning tree
3.) Calculate shortest path to visit all vertices (Traveling Salesman Problem)
note: Only works on completely connected graph
4.) Exit the program
Please enter the number that corresponds with your choice:
Enter the name of the starting vertex:
Enter the name of the ending vertex:
Found 0 for "a"
Found 3 for "d"
Found 0 for "a"
The shortest path between a and d is: a, b, c, d
sh: 1: pause: not found
What would you like to do?
1.) Calculate the shortest path between two vertices
2.) Calculate the minimum spanning tree
3.) Calculate shortest path to visit all vertices (Traveling Salesman Problem)
note: Only works on completely connected graph
4.) Exit the program
Please enter the number that corresponds with your choice:
usually в c ++ вам обычно не везет.Используйте валгринд и асан / убсан!