dijkstra 的算法不计算我的提升图中顶点的前辈
dijkstra's algorithm not computing the predecessors of the vertices in my boost graph
我正在尝试编写一个程序，该程序使用 boost 图形库从文本文件构建图形，然后在其上执行用户选择的某些算法。我的代码运行良好，但是一旦 boost::dijkstra_shortest_paths() 或 boost::prim_minimum_spanning_tree() 完成执行，每个顶点的前任 属性 将设置为同一个顶点！这就像算法在没有完成其工作的情况下运行。我不太确定为什么会这样，并且想知道是否有人可以阐明这个问题。
这是我的程序：
#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_1_67_0。
解析非常挑剔，不检查任何错误。更糟糕的是，findVertex 在查找不存在的名称时会执行 "whatever"（例如，如果解析出错并且查找空字符串）。如果幸运的话，它会崩溃。¹
如果您调试程序（或者，确实像我一样添加了一些跟踪），您可能会发现所有的边都添加了错误的顶点。
此外，您的dist属性是int，不能代表您指定的infinity。
修复这些，我至少可以 运行 第一个算法：
#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!
我正在尝试编写一个程序，该程序使用 boost 图形库从文本文件构建图形，然后在其上执行用户选择的某些算法。我的代码运行良好，但是一旦 boost::dijkstra_shortest_paths() 或 boost::prim_minimum_spanning_tree() 完成执行，每个顶点的前任 属性 将设置为同一个顶点！这就像算法在没有完成其工作的情况下运行。我不太确定为什么会这样，并且想知道是否有人可以阐明这个问题。
这是我的程序：
#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_1_67_0。
解析非常挑剔，不检查任何错误。更糟糕的是，findVertex 在查找不存在的名称时会执行 "whatever"（例如，如果解析出错并且查找空字符串）。如果幸运的话，它会崩溃。¹
如果您调试程序（或者，确实像我一样添加了一些跟踪），您可能会发现所有的边都添加了错误的顶点。
此外，您的dist属性是int，不能代表您指定的infinity。
修复这些，我至少可以 运行 第一个算法：
#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!