I have a weird mistake that I just can't find.
I create an adjacency_list using the Boost Graph library and populate the list of vertices with a vector. When I repeat the vector, it will print all the vertices correctly, however, when I execute algorithms such as Shortjest Dijkstra, the last vertex displays an empty one.
For example:
Shortest path from C to R
C -> H = 55
H -> = 97
-> R = 56
Distance: 208
To make things worse, if I write a simple search to select a specific vertex, the last vertex in the vector is again a problem, since it assumes that it is not there.
std::string start_vertex;
bool valid = false;
std::cout << "Vertices:" << std::endl;
for (auto &i : _vertices) {
std::cout << i << " ";
}
std::cout << std::endl;
while (!valid) {
std::cout << "Enter starting vertex: ";
std::cin >> start_vertex;
for (auto &i : _vertices) {
if (i == start_vertex) {
valid = true;
break;
}
}
}
The above when searching for the top of the problem continues the cycle, and all other vertices work correctly. As mentioned earlier, vertices are all printed during iteration otherwise.
, foreach , . , , , . , , .
.
#include <fstream>
#include <iostream>
#include <string>
#include <boost/tokenizer.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/config.hpp>
#include <boost/algorithm/string.hpp>
#include <utility>
#include <vector>
#include <map>
int main(int , const char * argv[]) {
std::ifstream input(argv[1]);
typedef int Weight;
typedef boost::property<boost::vertex_name_t, std::string> VertexNameProperty;
typedef boost::property<boost::edge_weight_t, Weight> EdgeWeightProperty;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
VertexNameProperty, EdgeWeightProperty> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::property_map<Graph, boost::vertex_index_t>::type IndexMap;
typedef boost::property_map<Graph, boost::vertex_name_t>::type NameMap;
typedef boost::iterator_property_map<Vertex*, IndexMap, Vertex, Vertex&>
PredecessorMap;
typedef boost::iterator_property_map<Weight*, IndexMap, Weight, Weight&>
DistanceMap;
std::string line, vertex;
std::getline(input, line);
std::getline(input, line);
boost::char_separator<char> sep(",");
typedef boost::tokenizer<boost::char_separator<char> > tokenizer;
tokenizer tok(line, sep);
std::vector<std::string> _vertices;
for (auto &i : tok) {
_vertices.push_back(i);
}
Graph g(sizeof(_vertices));
std::map<std::string, Vertex> vertex_map;
for (auto &i : _vertices) {
vertex_map[i] = boost::add_vertex(std::string(i), g);
}
char c;
struct GraphParameters {
char vertex_one, vertex_two;
Weight edge_weight;
};
std::getline(input, line);
while (getline(input, line)) {
GraphParameters p;
std::istringstream iss(line);
iss >> c >> p.vertex_one >> c >> p.vertex_two >> c >> p.edge_weight >> c;
std::string v1, v2;
std::stringstream ss1 ,ss2;
ss1 << p.vertex_one;
ss1 >> v1;
ss2 << p.vertex_two;
ss2 >> v2;
boost::add_edge(vertex_map[v1], vertex_map[v2], p.edge_weight, g);
}
std::string start_vertex, end_vertex;
bool valid = false;
std::cout << "Vertices:" << std::endl;
for (auto &i : _vertices) {
std::cout << i << " ";
}
std::cout << std::endl;
while (!valid) {
std::cout << "Enter starting vertex: ";
std::cin >> start_vertex;
for (auto &i : _vertices) {
if (i == start_vertex) {
valid = true;
break;
}
}
}
while (valid) {
std::cout << "Enter ending vertex: ";
std::cin >> end_vertex;
for (auto &i : _vertices) {
if (i == end_vertex) {
valid = false;
break;
}
}
}
std::vector<Vertex> predecessors(boost::num_vertices(g));
std::vector<Weight> distances(boost::num_vertices(g));
IndexMap indexMap = boost::get(boost::vertex_index, g);
PredecessorMap predecessorMap(&predecessors[0], indexMap);
DistanceMap distanceMap(&distances[0], indexMap);
boost::dijkstra_shortest_paths(g, vertex_map[start_vertex],
boost::distance_map(distanceMap)
.predecessor_map(predecessorMap));
NameMap nameMap = boost::get(boost::vertex_name, g);
std::cout << std::endl;
typedef std::vector<Graph::edge_descriptor> PathType;
PathType path;
Vertex v = vertex_map[end_vertex];
for(Vertex u = predecessorMap[v]; u != v; v = u, u = predecessorMap[v]) {
std::pair<Graph::edge_descriptor, bool> edgePair = boost::edge(u, v, g);
Graph::edge_descriptor edge = edgePair.first;
path.push_back(edge);
}
std::cout << "Shortest path from " << start_vertex << " to " << end_vertex
<< std::endl;
for(PathType::reverse_iterator pathIterator = path.rbegin(); pathIterator
!= path.rend(); ++pathIterator) {
std::cout << nameMap[boost::source(*pathIterator, g)] << " -> "
<< nameMap[boost::target(*pathIterator, g)]
<< " = " << boost::get(boost::edge_weight, g, *pathIterator)
<< std::endl;
}
std::cout << std::endl;
std::cout << "Distance: " << distanceMap[vertex_map[end_vertex]] << std::endl;
std::cout << std::end;
return EXIT_SUCCESS;
}
:
Vertices:
S,H,R,C,G
Edges
(S,C,39)
(R,S,86)
(G,S,74)
(C,H,55)
(R,C,126)
(G,C,68)
(R,H,111)
(G,R,56)
(H,G,97)
(S,H,27)