为什么我不能使用我的无序贴图从Boost图形库中打印出该顶点的名称 [英] Why can't I use my unordered map to print out a name for this vertex from boost graph library

问题描述

我正在从文件中读取边缘列表，并尝试使用增强图形库从中制作一个图形.最终目标是实现girvan newman算法，但是现在我正在努力读取图形.我将数据读取为两个无序映射，它们与switch键和值对重复，因此可以使用.同时找到键和值.这是我的代码:

I am reading in an edge list from a file and trying to make a graph out of it using boost graph library. The final goal is to implement the girvan newman algorithm, but right now I'm just working on getting the graph read in. I read the data in as two unordered maps that are duplicated with switch key and value pairs, that way I can use .find with both the key and value. Here is my code:

#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));

读完所有数据后，创建Graph g，然后调用boost图库使用的练习顶点函数.在他们的实现中，他们使用 char * name ="ABCDE" ，他们可以使用它们为锻炼顶点中的每个获取不同的输出.我想对我的地图执行此操作，但是它不起作用.

After I read in all the data, I create my Graph g and then call the exercise vertex function that boost graph library uses. In their implementation they use a char* name = "ABCDE" which they can use to get different outputs for each of the gets in exercise vertex. I am wanting to do this with my map, but it is not working.

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 *名称然后我认为搜索地图应该没问题.

I have been trying to get this working for a whole day now, and I'm not sure what else to try. I think the problem is with the exercise vertex function because I did some testing in my readInGraph function and was able to list all the edges with their corresponding names. I think it might have to do with how i'm accessing the map. In the original code, in the constructor, there were these brackets that I had to remove to get it to compile and I'm not sure why. I think that might have something to do with my problem, maybe its not actually recognizing name as a map and therefore the .find function is working. My other thought was that the get(vertex_id, v) isnt returning something that is in the map, but if the value could previously be used as an index in the char* name then I figured it should be fine to search my map.

这是我的输入文件的简化版本，仅供参考:

Here is a shortened version of my input file just for reference:

78

C-B

D-B

D-C

E-B

E-C

E-D

推荐答案

您的初始边缘权重

 transmission_delay[] = {1}; // no edge weights

是单个元素，因此图形构造会调用未定义的行为.

is a single element, so the graph construction invokes Undefined Behaviour.

您需要一个对边数有效的迭代器.这些构造函数有点不安全".从某种意义上说，它们使用原始迭代器，因此不进行检查.BGL在那显示年龄.

You need an iterator that is valid for the number of edges. These constructors are a bit "unsafe" in the sense that they use raw iterators and hence they aren't checked. BGL is showing some age there.

解决此问题(以及C99可变长度数组的使用):¹

Fix that (as well as the C99 variable length array use):¹

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);

¹好的，因为该问题被删除了一段时间，所以我进行了更多的审查/重构.

¹ Okay I did some more review/refactor since the question was deleted for a while.

您不需要过于笼统的"exercise_vertex"-适用于非 vecS 个案例.

You don't need the overly generalized "exercise_vertex" - that's for non-vecS cases.

以下内容简化了 readInGraph ，以使用单个Bimap作为名称，并通过文件一次以解析，索引和创建边缘:

The following simplifies the readInGraph to use a single Bimap for the names, and a single pass through the file to parse, index, and create the edges:

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);
}

请注意，我们现在返回图形，因此主程序可以像

Notice that we now return the graph, so the main program can be like

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";
    }
}

实时演示

在Coliru上直播

Live Demo

Live On Coliru

打印

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图形库中打印出该顶点的名称的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！