为什么我不能使用我的无序地图从 boost 图形库中打印出该顶点的名称
Why can't I use my unordered map to print out a name for this vertex from boost graph library
我正在从文件中读取边列表,并尝试使用 boost 图形库从中制作图形。最终目标是实现 girvan newman 算法,但现在我只是在努力读入图表。我将数据读入为两个无序映射,它们与开关键和值对重复,这样我就可以使用.find 同时包含键和值。这是我的代码:
#include <iostream>
#include <utility> //std::pair
#include <algorithm> //std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/small_world_generator.hpp>
#include <boost/random/linear_congruential.hpp>
#include <fstream>
typedef adjacency_list< vecS, vecS, bidirectionalS, no_property,
property< edge_weight_t, float > >
Graph_type;
typedef std::pair< int, int > Edge;
typedef typename graph_traits< Graph_type >::vertex_descriptor Vertex;
void readInGraph(){
ifstream myFile("../data/put_data_here.txt");
//gets first line and turns it to int
string x;
myFile >> x;
stringstream geek(x);
int numEdges;
geek >> numEdges;
Edge edge_array[numEdges];
string prev = "prev";
string line;
myFile.ignore();
std::unordered_map<string, int> name;
std::unordered_map<int, string> inverseName;
int mapCounter = 0;
string tempVar;
//loops through file to store names
//only loops through first column of edges to minimize lookup time
while(getline(myFile, line)){
string delimiter = " ";
string token = line.substr(0, line.find(delimiter));
if(token != prev){
name[token] = mapCounter;
inverseName[mapCounter] = token;
mapCounter++;
}
prev = token;
}
myFile.clear();
myFile.seekg(0, ios::beg);
myFile >> tempVar; //gets rid of first line of file
myFile.ignore();
// loops through the second column of edges and adds any vertices that weren't
// previously added to the map
while(getline(myFile, line)){
string delimiter = "-";
string token = line.substr(line.find(delimiter) + 2, string::npos);
if(name.count(token) == 0){
name[token] = mapCounter;
inverseName[mapCounter] = token;
mapCounter++;
}
}
int numVertices = name.size();
cout << numVertices;
//now that all the names are collected we can read in the edge array
//and store it as the integer mapped to that name in the map
myFile.clear();
myFile.seekg(0, ios::beg);
myFile >> tempVar; //gets rid of first line of file
myFile.ignore();
for(int i = 0; i < numEdges; i++){
string hyphen; //gets rid of hyphen
myFile >> tempVar;
edge_array[i].first = name.find(tempVar)->second;
myFile >> hyphen;
myFile >> tempVar;
edge_array[i].second = name.find(tempVar)->second;
}
float transmission_delay[] = { 1 }; //no edge weights
Graph_type newGraph(edge_array, edge_array + numEdges, transmission_delay, numVertices);
std::for_each(vertices(newGraph).first, vertices(newGraph).second, exercise_vertex< Graph_type >(newGraph, inverseName));
读入所有数据后,我创建了我的图形 g,然后调用了 boost 图形库使用的练习顶点函数。在他们的实现中,他们使用了 char* name = "ABCDE"
,他们可以使用它来为练习顶点中的每个获取获得不同的输出。我想对我的地图执行此操作,但它不起作用。
template < class Graph > struct exercise_vertex
{
//state vars
Graph& g;
//const char* name; this is the from the original code
std::unordered_map<int, string> inverseName;
//Constructor
exercise_vertex(Graph& g_, std::unordered_map<int, string> name_) : g(g_), inverseName(name_) {}
//exercise_vertex(Graph& g_, const char name_[]) : g(g_), name(name_) {} from the original code
//vertex descriptor
typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
void operator()(const Vertex& v) const
{
typename property_map< Graph, vertex_index_t >::type vertex_id
= get(vertex_index, g);
std::cout << "vertex: " << get(vertex_id, v) << std::endl;
//std::cout << "vertex: " << name[get(vertex_id, v)] << std::endl; this is from the original code
//std::cout << "vertex: " << inverseName.find(get(vertex_id, v))->second << std::endl; this is what I would want to do but it doesn't work
// Write out the outgoing edges
std::cout << "\tout-edges: ";
typename graph_traits< Graph >::out_edge_iterator out_i, out_end;
typename graph_traits< Graph >::edge_descriptor e;
for (boost::tie(out_i, out_end) = out_edges(v, g); out_i != out_end; ++out_i)
{
e = *out_i;
Vertex src = source(e, g), targ = target(e, g);
std::cout << "(" << get(vertex_id, src) << ","
<< get(vertex_id, targ) << ") ";
}
std::cout << std::endl;
// Write out the incoming edges
std::cout << "\tin-edges: ";
typename graph_traits< Graph >::in_edge_iterator in_i, in_end;
for (boost::tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
{
e = *in_i;
Vertex src = source(e, g), targ = target(e, g);
std::cout << "(" << get(vertex_id, src) << ","
<< get(vertex_id, targ) << ") ";
}
std::cout << std::endl;
// Write out all adjacent vertices
std::cout << "\tadjacent vertices: ";
typename graph_traits< Graph >::adjacency_iterator ai, ai_end;
for (boost::tie(ai, ai_end) = adjacent_vertices(v, g); ai != ai_end;
++ai)
std::cout << get(vertex_id, *ai) << " ";
std::cout << std::endl;
}
};
我一整天都在努力让它工作,但我不确定还能尝试什么。我认为问题在于练习顶点函数,因为我在我的 readInGraph 函数中做了一些测试,并且能够列出所有具有相应名称的边。我认为这可能与我访问地图的方式有关。在原始代码中,在构造函数中,我必须删除这些括号才能使其编译,我不确定为什么。我认为这可能与我的问题有关,也许它实际上没有将名称识别为地图,因此 .find 函数正在运行。我的另一个想法是 get(vertex_id, v)
不会返回地图中的内容,但如果该值以前可以用作 char* name
中的索引,那么我认为搜索我的地图应该没问题。
这是我的输入文件的简化版本,仅供参考:
78
丙-乙
D - B
D - C
E - B
E - C
E - D
你的初始边权重
transmission_delay[] = {1}; // no edge weights
是单个元素,因此图形构造调用 Undefined Behaviour.
您需要一个对边数有效的迭代器。这些构造函数有点“不安全”,因为它们使用原始迭代器,因此不检查它们。
BGL 在那里显示出一些年龄。
修复该问题(以及 C99 可变长度数组的使用):¹
std::vector<float> transmission_delay(edge_array.size(),
1.f); // no edge weights
int const numVertices = mappings.size();
return Graph_type(edge_array.data(), edge_array.data() + edge_array.size(),
transmission_delay.data(), numVertices);
¹ 好的,我又做了一些 review/refactor 因为这个问题被删除了一段时间。
你不需要过于笼统的“exercise_vertex”——那是针对非vecS
情况的。
以下简化 readInGraph
以使用单个 Bimap 作为名称,并通过文件一次传递来解析、索引和创建边缘:
using Graph_type =
boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS,
boost::no_property,
boost::property<boost::edge_weight_t, float>>;
using Vertex = typename boost::graph_traits<Graph_type>::vertex_descriptor;
using Edge = std::pair<Vertex, Vertex>;
Graph_type readInGraph(std::string const& fname, Mappings& mappings) {
std::ifstream myFile(fname);
// gets first line and turns it to int
unsigned numEdges = 0;
myFile >> numEdges;
std::vector<Edge> edge_array;
for (std::string src, hyphen, tgt;
edge_array.size() < numEdges && myFile >> src >> hyphen >> tgt;) {
// combined lookup/insert:
auto s = mappings.insert(Mappings::value_type(src, mappings.size()))
.first->get_right();
auto t = mappings.insert(Mappings::value_type(tgt, mappings.size()))
.first->get_right();
// now that all the names are collected we can read in the edge array
// and store it as the integer mapped to that name in the map
edge_array.emplace_back(s, t);
}
std::vector<float> transmission_delay(edge_array.size(),
1.f); // no edge weights
int const numVertices = mappings.size();
return Graph_type(edge_array.data(), edge_array.data() + edge_array.size(),
transmission_delay.data(), numVertices);
}
注意我们现在 return 图表,所以主程序可以像
Mappings mappings;
auto g = readInGraph("put_data_here.txt", mappings);
auto& invmap = mappings.right;
for (Vertex v : boost::make_iterator_range(vertices(g))) {
std::cout << "Vertex " << v << " name '" << invmap.at(v) << "':\n";
for (auto e : boost::make_iterator_range(out_edges(v, g))) {
auto t = target(e, g);
std::cout << " - adjacent to " << t << " (" << invmap.at(t) << ")\n";
}
}
现场演示
版画
Vertex 0 name 'C':
- adjacent to 1 (B)
Vertex 1 name 'B':
Vertex 2 name 'D':
- adjacent to 1 (B)
- adjacent to 0 (C)
Vertex 3 name 'E':
- adjacent to 1 (B)
- adjacent to 0 (C)
- adjacent to 2 (D)
我正在从文件中读取边列表,并尝试使用 boost 图形库从中制作图形。最终目标是实现 girvan newman 算法,但现在我只是在努力读入图表。我将数据读入为两个无序映射,它们与开关键和值对重复,这样我就可以使用.find 同时包含键和值。这是我的代码:
#include <iostream>
#include <utility> //std::pair
#include <algorithm> //std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/small_world_generator.hpp>
#include <boost/random/linear_congruential.hpp>
#include <fstream>
typedef adjacency_list< vecS, vecS, bidirectionalS, no_property,
property< edge_weight_t, float > >
Graph_type;
typedef std::pair< int, int > Edge;
typedef typename graph_traits< Graph_type >::vertex_descriptor Vertex;
void readInGraph(){
ifstream myFile("../data/put_data_here.txt");
//gets first line and turns it to int
string x;
myFile >> x;
stringstream geek(x);
int numEdges;
geek >> numEdges;
Edge edge_array[numEdges];
string prev = "prev";
string line;
myFile.ignore();
std::unordered_map<string, int> name;
std::unordered_map<int, string> inverseName;
int mapCounter = 0;
string tempVar;
//loops through file to store names
//only loops through first column of edges to minimize lookup time
while(getline(myFile, line)){
string delimiter = " ";
string token = line.substr(0, line.find(delimiter));
if(token != prev){
name[token] = mapCounter;
inverseName[mapCounter] = token;
mapCounter++;
}
prev = token;
}
myFile.clear();
myFile.seekg(0, ios::beg);
myFile >> tempVar; //gets rid of first line of file
myFile.ignore();
// loops through the second column of edges and adds any vertices that weren't
// previously added to the map
while(getline(myFile, line)){
string delimiter = "-";
string token = line.substr(line.find(delimiter) + 2, string::npos);
if(name.count(token) == 0){
name[token] = mapCounter;
inverseName[mapCounter] = token;
mapCounter++;
}
}
int numVertices = name.size();
cout << numVertices;
//now that all the names are collected we can read in the edge array
//and store it as the integer mapped to that name in the map
myFile.clear();
myFile.seekg(0, ios::beg);
myFile >> tempVar; //gets rid of first line of file
myFile.ignore();
for(int i = 0; i < numEdges; i++){
string hyphen; //gets rid of hyphen
myFile >> tempVar;
edge_array[i].first = name.find(tempVar)->second;
myFile >> hyphen;
myFile >> tempVar;
edge_array[i].second = name.find(tempVar)->second;
}
float transmission_delay[] = { 1 }; //no edge weights
Graph_type newGraph(edge_array, edge_array + numEdges, transmission_delay, numVertices);
std::for_each(vertices(newGraph).first, vertices(newGraph).second, exercise_vertex< Graph_type >(newGraph, inverseName));
读入所有数据后,我创建了我的图形 g,然后调用了 boost 图形库使用的练习顶点函数。在他们的实现中,他们使用了 char* name = "ABCDE"
,他们可以使用它来为练习顶点中的每个获取获得不同的输出。我想对我的地图执行此操作,但它不起作用。
template < class Graph > struct exercise_vertex
{
//state vars
Graph& g;
//const char* name; this is the from the original code
std::unordered_map<int, string> inverseName;
//Constructor
exercise_vertex(Graph& g_, std::unordered_map<int, string> name_) : g(g_), inverseName(name_) {}
//exercise_vertex(Graph& g_, const char name_[]) : g(g_), name(name_) {} from the original code
//vertex descriptor
typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
void operator()(const Vertex& v) const
{
typename property_map< Graph, vertex_index_t >::type vertex_id
= get(vertex_index, g);
std::cout << "vertex: " << get(vertex_id, v) << std::endl;
//std::cout << "vertex: " << name[get(vertex_id, v)] << std::endl; this is from the original code
//std::cout << "vertex: " << inverseName.find(get(vertex_id, v))->second << std::endl; this is what I would want to do but it doesn't work
// Write out the outgoing edges
std::cout << "\tout-edges: ";
typename graph_traits< Graph >::out_edge_iterator out_i, out_end;
typename graph_traits< Graph >::edge_descriptor e;
for (boost::tie(out_i, out_end) = out_edges(v, g); out_i != out_end; ++out_i)
{
e = *out_i;
Vertex src = source(e, g), targ = target(e, g);
std::cout << "(" << get(vertex_id, src) << ","
<< get(vertex_id, targ) << ") ";
}
std::cout << std::endl;
// Write out the incoming edges
std::cout << "\tin-edges: ";
typename graph_traits< Graph >::in_edge_iterator in_i, in_end;
for (boost::tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
{
e = *in_i;
Vertex src = source(e, g), targ = target(e, g);
std::cout << "(" << get(vertex_id, src) << ","
<< get(vertex_id, targ) << ") ";
}
std::cout << std::endl;
// Write out all adjacent vertices
std::cout << "\tadjacent vertices: ";
typename graph_traits< Graph >::adjacency_iterator ai, ai_end;
for (boost::tie(ai, ai_end) = adjacent_vertices(v, g); ai != ai_end;
++ai)
std::cout << get(vertex_id, *ai) << " ";
std::cout << std::endl;
}
};
我一整天都在努力让它工作,但我不确定还能尝试什么。我认为问题在于练习顶点函数,因为我在我的 readInGraph 函数中做了一些测试,并且能够列出所有具有相应名称的边。我认为这可能与我访问地图的方式有关。在原始代码中,在构造函数中,我必须删除这些括号才能使其编译,我不确定为什么。我认为这可能与我的问题有关,也许它实际上没有将名称识别为地图,因此 .find 函数正在运行。我的另一个想法是 get(vertex_id, v)
不会返回地图中的内容,但如果该值以前可以用作 char* name
中的索引,那么我认为搜索我的地图应该没问题。
这是我的输入文件的简化版本,仅供参考:
78
丙-乙
D - B
D - C
E - B
E - C
E - D
你的初始边权重
transmission_delay[] = {1}; // no edge weights
是单个元素,因此图形构造调用 Undefined Behaviour.
您需要一个对边数有效的迭代器。这些构造函数有点“不安全”,因为它们使用原始迭代器,因此不检查它们。 BGL 在那里显示出一些年龄。
修复该问题(以及 C99 可变长度数组的使用):¹
std::vector<float> transmission_delay(edge_array.size(),
1.f); // no edge weights
int const numVertices = mappings.size();
return Graph_type(edge_array.data(), edge_array.data() + edge_array.size(),
transmission_delay.data(), numVertices);
¹ 好的,我又做了一些 review/refactor 因为这个问题被删除了一段时间。
你不需要过于笼统的“exercise_vertex”——那是针对非vecS
情况的。
以下简化 readInGraph
以使用单个 Bimap 作为名称,并通过文件一次传递来解析、索引和创建边缘:
using Graph_type =
boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS,
boost::no_property,
boost::property<boost::edge_weight_t, float>>;
using Vertex = typename boost::graph_traits<Graph_type>::vertex_descriptor;
using Edge = std::pair<Vertex, Vertex>;
Graph_type readInGraph(std::string const& fname, Mappings& mappings) {
std::ifstream myFile(fname);
// gets first line and turns it to int
unsigned numEdges = 0;
myFile >> numEdges;
std::vector<Edge> edge_array;
for (std::string src, hyphen, tgt;
edge_array.size() < numEdges && myFile >> src >> hyphen >> tgt;) {
// combined lookup/insert:
auto s = mappings.insert(Mappings::value_type(src, mappings.size()))
.first->get_right();
auto t = mappings.insert(Mappings::value_type(tgt, mappings.size()))
.first->get_right();
// now that all the names are collected we can read in the edge array
// and store it as the integer mapped to that name in the map
edge_array.emplace_back(s, t);
}
std::vector<float> transmission_delay(edge_array.size(),
1.f); // no edge weights
int const numVertices = mappings.size();
return Graph_type(edge_array.data(), edge_array.data() + edge_array.size(),
transmission_delay.data(), numVertices);
}
注意我们现在 return 图表,所以主程序可以像
Mappings mappings;
auto g = readInGraph("put_data_here.txt", mappings);
auto& invmap = mappings.right;
for (Vertex v : boost::make_iterator_range(vertices(g))) {
std::cout << "Vertex " << v << " name '" << invmap.at(v) << "':\n";
for (auto e : boost::make_iterator_range(out_edges(v, g))) {
auto t = target(e, g);
std::cout << " - adjacent to " << t << " (" << invmap.at(t) << ")\n";
}
}
现场演示
版画
Vertex 0 name 'C':
- adjacent to 1 (B)
Vertex 1 name 'B':
Vertex 2 name 'D':
- adjacent to 1 (B)
- adjacent to 0 (C)
Vertex 3 name 'E':
- adjacent to 1 (B)
- adjacent to 0 (C)
- adjacent to 2 (D)