增强图列表或向量

我已经花了好几天的时间来使用 boost 图形库。据我了解，在考虑 VertexList 和 EdgeList 存储时：

vecS :

• 拥有索引，因此可以通过它进行访问
• 删除顶点时，迭代器失效

listS :

• no index
• 不会使迭代器无效

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

我有一个具有此图形结构的工作算法：

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;

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

我确实需要索引访问功能，因为我的图所依赖的算法返回父节点的索引。我觉得我可以使用顶点而不是索引，但这意味着对代码的重大重写，我想知道是否可以避免它。

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

如果这听起来很愚蠢，请耐心等待。我现在很困惑，所以我可能会说一些愚蠢的话。如果您需要更多信息，请询问。

The 内部属性公式为：

property<tag, type, next_property>

当然，除非你让Intersection_Graph behave就像整型一样，你不能直接使用它作为type of the vertex_index财产。这也可能不是您想要的。

这看起来更接近：

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

它会声明two特性：

1. 已标记的内部属性vertex_index_t (type int)
2. 捆绑属性（键入Intersection_Graph）。请注意，捆绑属性可以通过隐式访问vertex_bundle_t tag.

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

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'

Notes:

• 图表“知道”这一事实vertex_index现在并不意味着它得到维护；你必须自己填写：

  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)

• 我相信也可以使用图特征关联顶点索引（但我过去没有这样做过）。如果您例如，这似乎是一个不错的方法。想要将索引存储在您的成员中Intersection_Graph struct.
• 就像我在我的评论如果你存储了，你可能不需要任何这些vertex_descriptors 而不是整数索引。