增强图形列表或VEC

Question

我已经花了几天的时间来处理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一样？

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

Answer 1

的内部特性的制剂是：

property<tag, type, next_property>

当然，除非你Intersection_Graph 的行为像一个整数类型，你不能直接使用它作为类型的的vertex_index属性。它也可能不是您想要的。

这看起来更近：

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

它会声明两个属性：

1. 标记为vertex_index_t（类型int）的内部属性
2. 捆绑的属性（类型为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与图形类型相关联，因为您可以将其作为命名参数传递给所有相关算法AFAIK。这包括构造依赖于vertex_index的派生属性图（例如make_iterator_property_map）

• 我相信也可以使用图特征来关联顶点索引（但我过去从未这样做过）。如果您想将索引存储在Intersection_Graph结构的成员中，这似乎是一种不错的方法。
• 就像我在评论中说的那样，如果您存储vertex_descriptors而不是整数索引，则可能不需要任何这些。