c++ - boost 图形列表或vec

我已经花了几天的时间来处理Boost图形库。据我了解，在考虑VertexList和EdgeList存储时:

vecS:

具有索引，因此可以使用它进行访问

删除顶点时，迭代器无效

listS:

没有索引

不会使迭代器

无效

这有点短，但这是我的问题的关键。我需要这些索引号，并且希望以后能够轻松删除顶点。

我有一个与此图结构有效的算法:

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。

我想改用listS来删除顶点。同样，我希望以后可以在Dijkstra算法中使用它。

我有点理解，我需要在列表中包含boost::vertex_index_t，但对于如何做到并同时保留自定义结构，我确实感到困惑。

我尝试了一些方法:

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;

但是我什至无法访问我的自定义结构。另外，索引访问不起作用。

我确实需要该索引访问功能，因为我的图的算法将取决于返回父节点的索引。我觉得我可以摆脱使用Vertex而不是索引的习惯，但这意味着对代码进行大量的重写，我想知道是否可以避免使用它。

所以我的问题是:在保持listS优势的同时，有什么方法可以使listS以类似于vecS的方式运行？

拜托，如果这听起来很蠢，请多多包涵。我现在很困惑，所以我可能会说些愚蠢的话。如果您需要更多信息，请询问。

最佳答案

内部性能公式为:

property<tag, type, next_property>

当然，除非使Intersection_Graph表现得像整数类型，否则不能将其直接用作vertex_index属性的类型。它也可能不是您想要的。

这看起来更近:

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

它会声明两个属性:

一个内部属性，标记为vertex_index_t(类型int)

捆绑属性(类型为Intersection_Graph)。请注意，可通过vertex_bundle_t标记隐式访问捆绑的属性。

现在考虑到这一点，一切都应该一帆风顺:

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

哪个打印例如(每次运行都会随机产生)

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并不意味着它得到了维护。您必须自己填写:

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

实际上，您不需要将vertex_index与图形类型相关联，因为您可以将make_iterator_property_map作为命名参数传递给所有相关算法AFAIK。这包括构造依赖于vertex_index(例如 Intersection_Graph )

的派生属性映射

我相信也可以使用图特征来关联顶点索引(但我过去从未这样做过)。例如，这似乎是个不错的选择想要将索引存储在vertex_descriptor结构的成员中。

就像我在my comment中所说的那样，如果您存储了ojit_code而不是整数索引，则可能不需要任何这些。

关于c++ - boost 图形列表或vec，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30243908/

lists

c++ - boost 图形列表或vec