Boost图库：可以捆绑性与内在性质相结合？(Boost Graph Library: possib

我使用这个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() ; 我的结论正确，这是什么原因造成的断言失败？ 我不能在BGL文档寻找是否有与使用的索引属性的任何这样的约束make_two_bit_color_map 。

所以，我的主要quesion是 ：是否有可能同时使用内部性能，特别是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的向量（克）。

在BGL这个中心的映射被称为“的vertex_index”属性映射和算法，如果该物业的地图不正确，根本无法正常工作。

所以，你的任务，AFAICT，就是要确保你能正确地列举你的顶点，以连续的方式。 很多时候，人们需要载体的一些额外的散列或STL地图用于此目的的组合。

在任何情况下，当你解决这个索引映射问题，你可能会与一些类，它实现映射结束。 然后，你的下一个步骤将是教加速，这是你的顶点索引属性。

如果您的类MyMappingClass行为与关联容器（即实现为STL地图，或升压unordered_map）比你可以把它传递给使用成语DFS样算法make_assoc_property_map(mymap) ，其中mymap中类型MyMappingClass的。

另外，您也可以在下面描述的更精细也更灵活的方式做到这一点。 这种灵活性可以转化为更高效的代码。

因为通常这个属性是只读的，你添加喜欢的代码：

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的属性图形）。

第二个功能是如何从属性键的给定值“获取”属性值（又名“vertex_descriptor的”）（又名整数在区间[0，为num_vertices（G）））。

这第二个功能可以有类似于以下的原型：

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

（注意，根据BGL，MyMappingClass应该是轻重量和复制施工的）。

文章来源: Boost Graph Library: possible to combine Bundled Properties with Interior Properties?