如何在boost中实现boost :: property_map以及如何更改它

Question

我在想如何在提升图中实现属性映射。例如，

我已经顶点和边缘属性定义如下：

//vertex property:--> 
struct NodeInfo { int a , b , c; }; //actual bundled property 

struct NodeInfoPropertyTag {    // tag and kind (as in boost documentation) 
     typedef boost::vertex_property_tag kind; 
     static std::size_t const num; 
}; 

std::size_t const NodeInfoPropertyTag::num = (std::size_t) &NodeInfoPropertyTag::num; 

//typedef the Vertex Property 
typedef boost::property <NodeInfoPropertyTag, NodeInfo> NodeProperty; 


//Similar fashion for Edge Property --> some property for each edge of graph. 
typedef boost::property <EdgeInfoPropertyTag, EdgeInfo> EdgeProperty; 

My图表被typedef定义如下：现在

typedef boost::adjacency_list <vecS, vecS, undirectedS, NodeProperty, EdgeProperty, no_property, listS> Graph_t; 

，在初始化使用上述的typedef G中的曲线图，我可以分配属性到顶点和边的属性

例如：

Graph_t G; 
    typedef graph_traits<Graph_t>::vertex_descriptor vd_t; 
    // edge_descriptor ed_t; 

    NodeInfo ninfo1, ninfo2; //put some values in ninfo 
    vd_t v = add_vertex (ninfo1, G) //add a vertex in G with property ninfo1 
    vd_t u = add_vertex (ninfo2, G) //add a vertex in G with property ninfo2 


    EdgeInfo einfo; //initialize edgeinfo for edge property 
    add_edge (u, v, einfo, G) edge (u, v) with property einfo is added in G 

要访问节点属性的任何顶点的，我可以用任何的2种方法如下：

//method 1: direct method: using Tags 

// for a vertex "v" --> get() 
NodInfo info = boost::get (NodeInfoPropertyTag(), G, v) //get v's property 

//modify info 

//put the modified property 
    put (NodeInfoPropertyTag(), G, v, info) // (put in G, key = v, value = info) 


//method 2 : using property maps. 

//Edge Map and Node Map 
typedef typename boost::property_map <Graph_t, EdgeInfoPropertyTag>::type EdgeMap; 
typedef typename boost::property_map <Graph_t, NodeInfoPropertyTag>::type NodeMap; 


//edge e --> get 
EdgeInfo einfo = boost::get (EdgeMap, e) 

//modify einfo 

//put 
put (EdgeMap, e, einfo) //put in the EdgeMap key = e, value = einfo 

现在，无论是操作基本上是一样的：即使用

//former is translated to the latter --> 
    get(NodeInfoPropertyTag(), G, "key") is equivalent to get (NodeMap, "key") 

我的问题是：

1. 这些属性如何存储在Graph对象中。
2. 它是否存储在一个地图，如std :: map <>？或一些列表？或者一些有效的地图式数据结构。
3. 如果是这样，我怎么能修改底层数据结构为std :: unordered_map，甚至 concurrent_hashmap或boost :: vector_property_map？

注： 我不知道我可以使用vector_prop_map（在这里），但我真的很想让 顶点ID变成向量索引和更有效地使用它 - 在边缘>可能会导致问题虽然

My图表将包含一个万个顶点和许多许多的边缘，以这种方式 搜索的std ::地图<>仍然会的log（n）本身，但我想便携性改变 基础数据结构，以便我可以使用unordered_map/concurrent_hashmap

我需要concurrent_hashmap（来自英特尔TBB），因为我将并行化我的算法 ，因此会希望同时访问将由线程修改的属性图 。

请提出是否可以控制和修改增强图中用于存储边和顶点属性的底层数据结构。

Answer 1

这些属性如何存储在Graph对象中。

属性不单独存储或类似的东西。

顶点和边属性存储在图的顶点和边上。没有使用std::map或其他关联容器。无论您提供给adjacency_list的是什么，因为VertexProperties和EdgeProperties模板参数将存储在顶点和边缘中，即与使用std::list<T>时相同，其中T将存储在链接列表的节点中（以及必要的next-prev指针）。换句话说，adjacency_list将存储包含VertexProperties类型对象的顶点，以及所需的任何边界列表（入和出）。

当你使用property_map（通过get/put函数），它只是做一点模板元编程魔术来创建一个薄包装器，它将只读/写一个顶点或边的正确单个属性。从概念上讲，这就是等价：

NodeInfo info = boost::get (NodeInfoPropertyTag(), G, v); 

// is conceptual equivalent to: 

NodeInfo info = G[v].NodeInfoProperty; 

这是所有的财产，地图确实，它看起来了顶点属性（在给定的图形对象的顶点描述符），并获取数据成员（或子对象）对应于给定标签类型的顶点属性。弄清楚如何为正确的属性标签获取正确的数据成员（或子对象）是一种模板元编程魔术，可以在编译时计算出来（无运行时开销）。而且，通常，从顶点描述符查找顶点属性是一个常量操作（例如，取消引用指针，按索引查找等）。总体而言，读取（读取或写入）特定顶点的特定属性是恒定时间操作。就我所知，对于使用adjacency_list的模板参数所做的任何选择都是如此。

如果是这样，我该如何修改底层数据结构为std :: unordered_map，甚至是concurrent_hashmap或boost :: vector_property_map？

您可以通过OutEdgeList，VertexList和EdgeList指定如何存储顶点和边。这些属性本身没有额外的存储方法。在这些情况下使用地图或hashmaps并没有多大意义。

我真的想使用它，这样顶点ID变成向量索引

当您为VertexList参数指定vecS这已经是用的adjacency_list的情况。

我需要concurrent_hashmap（来自英特尔TBB），因为我会并行化我的算法，因此会希望并发访问将由线程修改的属性映射。

您应该考虑使用Parallel Graph库来代替。

请提出是否可以控制和修改升压图中用于存储边和顶点属性的基础数据结构。

您可以指定用于存储顶点和边界列表的数据结构。你可以（理论上）为这些添加新的容器类型。然而，根据我的经验，这很难实现，因为adjacency_list的实现很难将您的思想包装起来，并且交换其底层容器并不像在Boost网站上宣传的那么容易。