Boost图表库：可能将捆绑属性与内部属性组合？ [英] Boost Graph Library: possible to combine Bundled Properties with Interior Properties?

问题描述

我使用 typedef 作为我的BGL图类型，图 struct VertexProperty 作为捆绑的顶点属性：

  struct VertexProperty {
 BeamType beam; 
 size_t index; 
}; 
 
 typedef typename boost :: adjacency_list< 
 boost :: listS，
 boost :: listS，
 boost :: bidirectionalS，
 VertexProperty 
>图形; 
  

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

  auto colorMap = boost :: make_two_bit_color_map（
 boost :: num_vertices（graph_），
 get（& VertexProperty :: index，graph_））; 
  

（ graph _ 图）。我最近的更改改变了 VertexProperty :: index 存储从文件读入的顶点索引号，而不是由我的代码自动生成。我的代码以前已经创建这些索引为基于0的连续索引，增加到添加到 graph _ 的每个新顶点。随着变化，我希望不再假设指数是连续的，或者它们将保持小于 graph_.size（） - 1 ;我只是不想把这个约束用户。但是，我继续使用 Vertex :: index 作为 two_bit_color_map 的属性，时间断言失败，并显示以下消息：

 断言失败！ 
 
程序：D：\school\thesis\code\build\test\bin\testChain.exe 
文件：D：\programming\lib\\ \\boost\boost_1_54_0 / boost / graph / two_bit_color_map.hpp，第72行
 
表达式：（std :: size_t）i< pm.n 
  

我知道我有 VertexProperty :: index 值高于或等于 graph_.size（）;是我的结论正确，这是什么导致断言失败？我在BGL文档中找不到对 make_two_bit_color_map 使用的索引属性有任何这样的约束。

所以，我的主要问题是：可以使用内部属性，特别是 property< vertex_index_t，int> em>绑定的顶点属性与BGL图，或者我困住一个或另一个？ （我想避免使用 VertexProperty 中的新成员重新实现连续索引）。我想象这可能看起来像这样，虽然可能与其他确切的语法：

  typedef typename boost :: adjacency_list& 
 boost :: listS，
 boost :: listS，
 boost :: bidirectionalS，
 property< vertex_index_t，int，property< VertexProperty> 
>图形; 
  

解决方案

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

大多数BGL搜索算法需要一个映射索引 - >顶点，其中索引在区间[0，num_vertices（g））中变化。例如，DFS，BFS，连接组件，A *等需要首先将每个顶点初始化为白颜色。

在BGL中，这个中心映射被称为vertex_index属性映射，如果这个属性映射是不正确的。

因此，您的任务AFAICT是确保您能够以连续的方式正确枚举您的顶点。通常，为了这个目的，需要向量与一些额外的散列或STL映射的组合。

在任何情况下，当你解决这个索引映射问题，你可能会得到一些实现映射的类。然后你的下一步将教会Boost，这是你的顶点索引属性。

如果您的类MyMappingClass表现为关联容器（即实现为STL映射或Boost unordered_map），您可以将其传递给类似DFS的算法使用惯例 make_assoc_property_map（mymap）其中mymap是MyMappingClass类型。

或者，你可以更复杂，方式如下所述。

由于通常此属性是只读的，因此您需要添加一个代码：

 命名空间提升{
 template<> 
 struct property_map< MyGraph，vertex_index_t> {
 typedef MyMappingClass const_type; 
 // typedef const_type type; 
 //  - 我们不定义类型为vertex_index_t的地图是只读的
};接下来，您的类MyMappingClass可以是一个完全兼容的BGL属性映射，意思是：B：B 
 
  

它会有一些声明如

  class MyMappingClass 
 {
 public：
 typedef readable_property_map_tag category ; 
 typedef int value_type; 
 typedef value_type reference; 
 typedef MyGraph :: vertex_descriptor key_type; 
};此外，为了使用这样的BGL兼容的属性映射，必须提供两个不同的get函数：首先是如何从图中get属性映射（如果你使MyMappingClass类是图的一个属性，可能是不必要的或微不足道的）。 
 
 
 
第二个函数是如何从一个给定的属性键值（也称为区间[0，num_vertices（）中的整数）获取属性值（也称为vertex_descriptor 
 
 
 
 
 code> MyMappingClass :: value_type // aka index 
 get（MyMappingClass mymap，
 MyMappingClass :: key_type key）// aka vertex_descriptor 
  
（注意，根据BGL，MyMappingClass应该是一个轻量级和可复制的结构）。
 
I'm using this typedef for my BGL graph type, Graph, using struct VertexProperty as a bundled vertex property:
struct VertexProperty {
    BeamType beam;
    size_t index;
};

typedef typename boost::adjacency_list<
        boost::listS,
        boost::listS,
        boost::bidirectionalS,
        VertexProperty
> Graph;
Before a recent change in my project, I'd been using the VertexProperty::index to construct a two_bit_color_map for use with depth_first_search:
auto colorMap = boost::make_two_bit_color_map(
        boost::num_vertices(graph_),
        get(&VertexProperty::index, graph_));
(the graph_ argument is a member variable of type Graph from above).  My recent change re-purposed VertexProperty::index to store a vertex index number read in from a file, rather than automatically generated by my code.  My code had previously been creating these indices as 0-based consecutive indices, incremented for each new vertex added to graph_.  With the change, I wish to no longer assume the indices are consecutive or that they will remain smaller than graph_.size() - 1; I just don't want to put that constraint on users.  However, I continued to use Vertex::index as the property for the two_bit_color_map, and this led to a run-time assertion failure with the message:
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
I know I have VertexProperty::index values that go higher than or equal to graph_.size(); is my conclusion correct that this is what is causing the assertion failure?  I can't find in the BGL docs if there is any such constraint on the index property used with make_two_bit_color_map.

So, my main quesion is: Is it possible to use both interior properties, specifically property<vertex_index_t, int> and bundled vertex properties with a BGL graph, or am I stuck with one or the other?  (I'd like to avoid implementing the consecutive indices again with a new member in VertexProperty).  I imagine this might look something like this, though probably with other exact syntax:
typedef typename boost::adjacency_list<
        boost::listS,
        boost::listS,
        boost::bidirectionalS,
        property<vertex_index_t, int, property<VertexProperty>>
> Graph;

解决方案
I think you are chasing a wrong problem. 

Majority of BGL search algorithms needs a mapping "index" --> "vertex" where index varies in interval [0, num_vertices(g)). For example, DFS, BFS, connectivity component, A*, etc. need to init each vertex to "white" color first. Instead, they essentially use a vector of size num_vertices(g).

In BGL this central mapping is called "vertex_index" property map and algorithms simply cannot work if this property map is incorrect. 

So your task, AFAICT, is to make sure you can enumerate your vertices correctly, in a continuous way. Quite often one needs a combination of vector with some extra hash- or STL map for this purpose. 

In any case, as you fix this index mapping issue you will likely end up with some class which implements the mapping. Then your next step will be to teach Boost that this is your vertex-index property. 

If your class MyMappingClass behaves as associative container (i.e. is implemented as STL map, or Boost unordered_map) than you can pass it to DFS-like algorithms using an idiom make_assoc_property_map(mymap) where mymap is of type MyMappingClass.

Alternatively, you can do it in more elaborate but also more flexible way described below. This flexibility can translate into more efficient code.

Since usually this property is read-only, you add a code like: 
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 
};
}
Next, your class MyMappingClass could be a fully-compliant BGL property map, meaning it would have some declarations like
class MyMappingClass
{    
public:    
    typedef readable_property_map_tag category; 
    typedef int value_type;
    typedef value_type reference;
    typedef MyGraph::vertex_descriptor key_type;     
};
Besides, to work with such BGL-compliant property map one has to provide two different "get" functions: first is how to "get" property map from your graph (may be unnecessary or trivial if you make the class MyMappingClass a property of the graph). 

The second function is how to "get" property value (aka "vertex_descriptor") from a given value of property key (aka integer in the interval [0,num_vertices(g))).

This second function can have a prototype similar to following: 
MyMappingClass::value_type //aka index
get(  MyMappingClass mymap,
      MyMappingClass::key_type key) //aka vertex_descriptor  
(Note, according to BGL, MyMappingClass should be a light-weight and copy constructable).

                        
这篇关于Boost图表库：可能将捆绑属性与内部属性组合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！