使用 boost 图库:如何通过从文件中读取边列表来创建图

2021-12-24 00:00:00 graph c++ boost

我是 boost 图库的新手，我想通过从文件中读取边列表来创建图.

I'm new to boost graph library and I'd like to create a graph by reading edge lists from a file.

edge_list.dat 文件的示例如下:

...
123 445
4535 343
3432 454
123 345
123 566
...

文件的每一行代表图的一条边，每行的两个数字是边对应的节点id.现在我想使用 boost 图形库从文件 edge_list.dat 创建一个图形.

Each line of the file represents an edge of the graph, and the two numbers in each line are the nodes' ids corresponding to the edge. Now I'd like to create a graph from the file edge_list.dat using boost graph library.

但是，我事先不知道图形的大小.我需要沿途将顶点添加到图中.然而，像这样为每个顶点创建一个顶点描述符是不切实际的:

However, I don't know the size of the graph in advance. I need to add the vertex into the graph along the way. However it is not practical to create a vertex descriptor for each vertex like this:

Graph::vertex_descriptor v0 = boost::add_vertex(g);
Graph::vertex_descriptor v1 = boost::add_vertex(g);

我想通过顶点 id 访问顶点.我真的不知道该怎么做.现在，我想出的解决方案是创建一个映射，其键是 id，值是 vertex_descriptor:

And I'd like to access the vertex through the vertex id. I don't really know how to do this. For now the solution that I come up with is to create a map for which the key is the id and the value is the vertex_descriptor:

std::map<int,Graph::vertex_descriptor> VertexList;
VertexList[123]=boost::add_vertex(g);

但是有没有一种方法可以在不创建地图的情况下做到这一点?

However is there a way that I can do this without creating the map?

提前致谢.

推荐答案

Soooo.雄心勃勃，嗯:)

Soooo. Ambitious, huh :)

Boost 图库.和文本解析.让我们看看我们能做些什么:提升图谱 + 提升灵气 = 良好的团队合作.

Boost Graph library. And text parsing. Let's see what we can do: Boost Graph + Boost Spirit Qi = nice teamwork.

看到它生活在 Coliru

See it Live On Coliru

#include <boost/fusion/adapted/std_pair.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/graph/edge_list.hpp>
#include <fstream>

typedef std::pair<int,int> Edge;
typedef std::vector<Edge> EdgeList;
typedef boost::edge_list<EdgeList::iterator> Graph;

namespace qi = boost::spirit::qi;

int main()
{
    std::ifstream ifs("input.txt");
    ifs >> std::noskipws;

    boost::spirit::istream_iterator f(ifs), l;

    std::vector<Edge> edges;
    bool parse_ok = qi::phrase_parse(f, l, (qi::int_ >> qi::int_) % qi::eol, qi::blank, edges);

    Graph g(edges.begin(), edges.end());

    if (parse_ok)
    {
        std::cout << "Graph parsed with " << num_edges(g) << " edges
";
    } else
        std::cout << "Parse error
";

    if (f!=l)
        std::cout << "Remaining unparsed input: '" << std::string(f,l) << "'
";
}

打印(对于上面的有效输入行):

Prints (for the valid input lines above):

Graph parsed with 5 edges
Remaining unparsed input: '
'

相关文章