c++ - boost 图列表或 vec

Question

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

vector :

• 有一个索引，所以可以用它访问
• 删除顶点时，迭代器失效

名单:

• 没有索引
• 不会使迭代器失效

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

我有一个具有这种图结构的工作算法:

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 以类似 vecS 的方式运行，同时保持 listS 的优势？

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

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 结构的成员中。
• 就像我在 my comment 中所说的那样如果您存储 vertex_descriptor 而不是整数索引，您可能不需要任何这些。