我正在尝试编写一个程序,该程序使用Boost图形库从文本文件构造图形,然后对它执行用户选择的某些算法。我的代码运行良好,但是一旦boost::dijkstra_shortest_paths()
或boost::prim_minimum_spanning_tree()
完成执行,每个顶点的predecessor属性将设置为该相同的顶点!就像算法没有执行就运行一样。我不太确定为什么会这样,并且想知道是否有人可以对此问题发表一些看法。
这是我的程序:
#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;
}
如果很重要,我将使用MS Visual Studio 2017和Boost版本boost_1_67_0。
最佳答案
解析非常挑剔,不检查任何错误。更糟糕的是,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)
并输入“input.txt 1 a d 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:
¹通常您不会在C++中那么幸运。使用valgrind和asan / ubsan!