c++ - 提升图形库 : possible to combine Bundled Properties with Interior Properties?

Question

我正在使用这个 typedef对于我的 BGL 图类型，Graph , 使用 struct VertexProperty作为捆绑的顶点属性:

struct VertexProperty {
    BeamType beam;
    size_t index;
};

typedef typename boost::adjacency_list<
        boost::listS,
        boost::listS,
        boost::bidirectionalS,
        VertexProperty
> Graph;

在最近更改我的项目之前，我一直在使用 VertexProperty::index构建一个two_bit_color_map用于 depth_first_search :

auto colorMap = boost::make_two_bit_color_map(
        boost::num_vertices(graph_),
        get(&VertexProperty::index, graph_));

(graph_ 参数是类型为 Graph 的成员变量)。我最近的更改重新调整了用途 VertexProperty::index存储从文件中读取的顶点索引号，而不是我的代码自动生成的。我的代码之前一直将这些索引创建为基于 0 的连续索引，并为添加到 graph_ 的每个新顶点递增。 .随着变化，我希望不再假设索引是连续的或者它们将保持小于 graph_.size() - 1。 ;我只是不想对用户施加这种限制。但是，我继续使用 Vertex::index作为 two_bit_color_map 的属性，这导致运行时断言失败并显示以下消息:

Assertion failed!

Program: D:\school\thesis\code\build\test\bin\testChain.exe
File: D:\programming\lib\boost\boost_1_54_0/boost/graph/two_bit_color_map.hpp, Line 72

Expression: (std::size_t)i < pm.n

我知道我有 VertexProperty::index高于或等于 graph_.size() 的值;我的结论是否正确，这是导致断言失败的原因？如果与 make_two_bit_color_map 一起使用的索引属性有任何此类约束，我无法在 BGL 文档中找到.

所以，我的主要问题是:是否可以同时使用两个内部属性，特别是 property<vertex_index_t, int> 和 将顶点属性与 BGL 图捆绑在一起，还是我坚持使用其中一个？ (我想避免使用 VertexProperty 中的新成员再次实现连续索引)。我想这可能看起来像这样，尽管可能使用其他确切的语法:

typedef typename boost::adjacency_list<
        boost::listS,
        boost::listS,
        boost::bidirectionalS,
        property<vertex_index_t, int, property<VertexProperty>>
> Graph;

Answer 1

我认为您正在追逐一个错误的问题。

大多数 BGL 搜索算法需要映射“索引”-->“顶点”，其中索引在区间 [0, num_vertices(g)) 内变化。例如，DFS、BFS、连接组件、A*等需要先将每个顶点初始化为“白色”颜色。相反，他们基本上使用大小为 num_vertices(g) 的 vector 。

在 BGL 中，这个中心映射称为“vertex_index”属性映射，如果这个属性映射不正确，算法就无法工作。

因此，AFAICT，您的任务是确保您能够以连续的方式正确枚举顶点。为此，通常需要将 vector 与一些额外的哈希或 STL 映射结合使用。

无论如何，当您解决这个索引映射问题时，您很可能会得到某个实现映射的类。然后你的下一步将是告诉 Boost 这是你的顶点索引属性。

如果您的类 MyMappingClass 表现为关联容器(即作为 STL 映射或 Boost unordered_map 实现)，那么您可以使用成语 make_assoc_property_map(mymap) 将其传递给类似 DFS 的算法，其中 mymap 是类型为 MyMappingClass。

或者，您可以通过下面描述的更详细但也更灵活的方式来完成。这种灵 active 可以转化为更高效的代码。

由于通常此属性是只读的，因此您添加如下代码:

namespace boost {
template<>
struct property_map< MyGraph, vertex_index_t > {
    typedef MyMappingClass const_type;
    //typedef const_type type; 
    //-- we do not define type as "vertex_index_t" map is read-only 
};
}

接下来，您的类 MyMappingClass 可以是一个完全兼容的 BGL 属性映射，这意味着它会有一些声明，例如

class MyMappingClass
{    
public:    
    typedef readable_property_map_tag category; 
    typedef int value_type;
    typedef value_type reference;
    typedef MyGraph::vertex_descriptor key_type;     
};

此外，要使用此类符合 BGL 的属性映射，必须提供两个不同的“获取”函数:第一个是如何从图形中“获取”属性映射(如果将类 MyMappingClass 设为图的属性)。

第二个函数是如何从属性键的给定值(也就是区间 [0,num_vertices(g)) 中的整数)“获取”属性值(也就是“vertex_descriptor”)。

第二个函数可以有一个类似于下面的原型(prototype):

MyMappingClass::value_type //aka index
get(  MyMappingClass mymap,
      MyMappingClass::key_type key) //aka vertex_descriptor  

(注意，根据 BGL，MyMappingClass 应该是轻量级和可复制构造的)。