提升图表或vec [英] Boost graph list or vec

问题描述

我已经花了好几天的时间使用boost graph库。据我所知，当考虑VertexList和EdgeList存储时：

I've been spending quite a few days working with the boost graph library. As far as I understand, when considering VertexList and EdgeList storage :

vecS：

• 拥有一个索引，因此可以访问它


• 在删除顶点时，迭代器无效

listS：

• 无索引


• 不会使迭代器无效

这有点短，但这是我的问题的要点。

It's a bit short but that's to the point for my problem. I need those index number and I want to be able to easily remove vertices later on.

我有一个工作算法与这个图结构：

I have a working algorithm with this graph structure :

typedef boost::adjacency_list<
        boost::vecS, boost::vecS, boost::undirectedS, 
        topologicalmap::Intersection_Graph ,
        boost::edge_weight_t, 
        boost::no_property > Graph_boost;

我有一个自定义结构 Intersection_Graph 我需要使用的顶点。这里我使用vecS。

I have a custom structure Intersection_Graph for my vertices that I need to use. Here I use vecS.

我想使用listS来删除顶点。同样，我想能够使用它以后用Dijkstra算法。

I want to use listS instead to be able to remove vertices. As well, I want to be able to use it later with Dijkstra algorithm.

我理解我需要在我的列表中有 boost :: vertex_index_t ，但我真的很困惑如何做到，并保持我的自定义结构在同一时间。

I kind of understand that I need to have boost::vertex_index_t in my list but I am really confused as to how to do it and keep my custom struct at the same time.

我尝试过这些行：

typedef boost::adjacency_list<
        boost::listS, boost::listS, boost::undirectedS, 
        boost::property<boost::vertex_index_t, topologicalmap::Intersection_Graph>,
        boost::edge_weight_t, 
        boost::no_property > Graph_boost;

但我甚至不能访问我的自定义结构。另外，索引访问不起作用。

But I can't even access my custom struct anymore. Plus, index access don't work.

我真的需要索引访问能力，因为算法我的图将依赖返回父节点的索引。我觉得我可以放弃使用顶点而不是索引，但它将意味着一个重大的代码重写，我想知道如果我可以避免它。

I really need that index access capability since the algorithm my graph will depend on return the index of the parent node. I feel like I could get away with using a Vertex instead of indexes but it would imply a major re-writing of the code and I want to know if I can avoid it.

所以我的问题是：有没有办法让listS以vecS喜欢的方式行为，同时保持listS的优点？

So my question is : is there any way to have listS behaving in a vecS like manner while keeping the advantages of listS ?

请跟我一起，如果它听起来笨。我现在很困惑，所以我可能会说一些愚蠢。

Please, bear with me if it sounds stupid. I'm quite confuse at the moment, so I might have say something stupid. If you need more information, just ask.

推荐答案

内部属性配方是：

property<tag, type, next_property>

当然，除非你 Intersection_Graph behave 作为一个整数类型，你不能直接使用它作为 vertex_index 属性的类型。

Of course, unless you make Intersection_Graph behave like an integral type you cannot use it directly as the type of the vertex_index property. It's also likely not what you wanted.

这看起来更接近：

boost::property<boost::vertex_index_t, int, topologicalmap::Intersection_Graph>

它会声明两个属性：

And it would declare two properties:

1. 一个内部属性标记为 vertex_index_t （类型 int ）


2. 一个捆绑的属性（键入 Intersection_Graph ）。请注意，捆绑的属性可通过 vertex_bundle_t 标记隐式访问。

1. an interior property tagged vertex_index_t (type int)
2. a bundled property (typed Intersection_Graph). Note that bundled properties are implicitly accessible through the vertex_bundle_t tag.

Live on Coliru

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/iteration_macros.hpp>

#include <random>
#include <iostream>

using namespace boost;

namespace topologicalmap {
    struct Intersection_Graph {
        std::string bundled;
    };
}

typedef boost::adjacency_list<
        boost::listS, boost::listS, boost::undirectedS, 
        boost::property<boost::vertex_index_t, int, topologicalmap::Intersection_Graph>,
        boost::edge_weight_t, 
        boost::no_property > Graph_boost;

int main() {

    std::mt19937 prng { std::random_device {} () };
    Graph_boost g;

    generate_random_graph(g, 10, 20, prng);

    // assign indices
    int i = 0;
    BGL_FORALL_VERTICES(v, g, Graph_boost) { 
        get(vertex_index, g)[v] = i; 
        g[v].bundled = "id:" + std::to_string(i);

        i++;
    }

    // print the graph using the `bundled` property as a label:
    print_graph(g, get(&topologicalmap::Intersection_Graph::bundled, g));

    // do some index accesses:
    for (int i : {1,7})
        std::cout << "\nVertex at index #" << i << " has a bundled property of '" << g[vertex(i,g)].bundled << "'";
}

（每次运行时随机生成）

Which prints e.g. (random generated each run)

id:0 <--> id:8 id:8 id:7 id:6 id:1 
id:1 <--> id:3 id:4 id:4 id:3 id:0 id:2 
id:2 <--> id:7 id:1 
id:3 <--> id:1 id:7 id:1 id:9 id:4 
id:4 <--> id:1 id:1 id:5 id:6 id:3 
id:5 <--> id:4 id:9 
id:6 <--> id:0 id:9 id:4 id:8 
id:7 <--> id:3 id:0 id:2 id:9 
id:8 <--> id:0 id:0 id:6 
id:9 <--> id:7 id:6 id:3 id:5 

Vertex at index #1 has a bundled property of 'id:1'
Vertex at index #7 has a bundled property of 'id:7'

注意：

• 图表知道 vertex_index 现在并不意味着它被维护;你必须自己填写：

• the fact that the graph "knows" vertex_index now doesn't mean it gets maintained; you have to fill it yourself:

int i = 0;
BGL_FORALL_VERTICES(v, g, Graph_boost) get(vertex_index, g)[v] = i++; 

你实际上不需要 vertex_index 与您的图类型相关联，因为您可以将其作为命名参数传递给所有相关的算法AFAIK。这包括构造依赖于vertex_index的派生属性映射（例如 make_iterator_property_map ）

you don't actually need to have vertex_index associated with your graph type, because you can pass it in as a named parameter to all relevant algorithms AFAIK. This includes constructing derived property maps that rely on a vertex_index (e.g. make_iterator_property_map)

这篇关于提升图表或vec的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！