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

I was wondering how the property maps are implemented in a boost Graph. For example,

我想知道如何在boost图中实现属性映射。例如，

I have vertex and edge properties defined like this:

我有像这样定义的顶点和边缘属性：

 //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 graph is typedef'd as below:

我的图表是typedef，如下所示：

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

Now, while initializing the graph G using above typedef, I can assign properties to vertices and edges with the properties

现在，在使用上面的typedef初始化图形G时，我可以使用属性为顶点和边指定属性

for eg:

例如：

  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

To access node property of any vertex I can use the any of the 2 methods as follows:

要访问任何顶点的节点属性，我可以使用以下两种方法中的任何一种：

 //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

Now, both the operations are essentially same: i.e. using

现在，两个操作基本相同：即使用

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

My question is:

我的问题是：

1. how are these properties are stored in the Graph object.
2. 这些属性如何存储在Graph对象中。
3. Is it stored in a map such as std::map<> ? or some list ? or some efficient map-like data structure.
4. 它存储在std :: map <>等地图中吗？还是一些清单？或者一些有效的类似地图的数据结构。
5. If so, how can I modify the underlying data structure to std::unordered_map or even concurrent_hashmap or boost::vector_property_map ?
6. 如果是这样，我如何将底层数据结构修改为std :: unordered_map甚至concurrent_hashmap或boost :: vector_property_map？

Note: I am not sure I could use vector_prop_map (here) but I would really like to use it so that the vertex id becomes the vector index and more efficient --> it could cause problem in edges though

注意：我不确定我是否可以使用vector_prop_map（这里），但我真的想使用它，以便顶点id成为矢量索引并且更有效 - >它可能会导致边缘问题

My graph would contain a million vertices and many many edges, in this way searching in the std::map<> would still be log(n) as such but I want the portability to change the underlying data structure so that I can use unordered_map / concurrent_hashmap

我的图形将包含一百万个顶点和许多边缘，这样在std :: map <>中搜索仍然是log（n），但我希望可移植性更改底层数据结构，以便我可以使用unordered_map / concurrent_hashmap

I need concurrent_hashmap (from Intel TBB) because I would be parallelizing my algorithm and so would desire concurrent access the to the property map which is going to be modified by threads.

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

Please suggest whether is it possible to control and modify such underlying data structures in boost graph for storing edge and vertex properties.

请建议是否可以在boost图中控制和修改这些底层数据结构，以存储边缘和顶点属性。

1 个解决方案

#1

how are these properties are stored in the Graph object.

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

The properties are not stored individually or anything like that.

属性不是单独存储的，也不是类似的存储。

The vertex and edge properties are stored within the vertices and the edges of the graph. There is no use of std::map or some other associative container. Whatever you provide to the adjacency_list as the VertexProperties and EdgeProperties template parameter will be stored in the vertices and edges, i.e., it is the same as when you use std::list<T> where T will be stored in the nodes of the linked-list (along with the necessary next-prev pointers). In other words, adjacency_list will store vertices that contain an object of type VertexProperties, plus whatever edge-lists (in and out) that is needed.

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

When you use property_map (via get/put functions), it is only doing a bit of template meta-programming magic to create a thin wrapper that will just read/write the correct individual property for a vertex or edge. Conceptually, this is the equivalence:

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

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

// is conceptual equivalent to:

NodeInfo info = G[v].NodeInfoProperty;

This is all the property-map really does, it looks up the vertex property (by the vertex-descriptor in the given graph object), and it fetches the data member (or sub-object) of the vertex property that corresponds to the given tag type. Figuring out how to obtain the correct data member (or sub-object) for the correct property tag is a piece of template meta-programming magic that figures it out at compile-time (no run-time overhead). And, in general, looking up the vertex property from the vertex-descriptor is a constant-time operation (e.g., dereference a pointer, lookup by index, etc.).

这是属性映射的全部实际，它查找顶点属性（通过给定图形对象中的顶点描述符），并且它获取与给定对应的顶点属性的数据成员（或子对象）标签类型。弄清楚如何为正确的属性标记获取正确的数据成员（或子对象）是一个模板元编程魔术，它在编译时计算出来（没有运行时开销）。并且，通常，从顶点描述符查找顶点属性是恒定时间操作（例如，取消引用指针，通过索引查找等）。

Overall, fetching (for read or write) a specific property for a specific vertex is a constant-time operation. This is true for any of the choices you make with the template arguments of adjacency_list, as far as I know.

总的来说，获取（读取或写入）特定顶点的特定属性是一个恒定时间操作。对于你用adjacency_list的模板参数做出的任何选择都是如此，据我所知。

If so, how can I modify the underlying data structure to std::unordered_map or even concurrent_hashmap or boost::vector_property_map ?

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

You can specify how you want vertices and edges to be stored, via the OutEdgeList, VertexList, and EdgeList. There is no additional storage method for the properties themselves. And using maps or hashmaps doesn't really make much sense in these contexts.

您可以通过OutEdgeList，VertexList和EdgeList指定要存储顶点和边的方式。属性本身没有额外的存储方法。在这些上下文中使用map或hashmaps并没有多大意义。

I would really like to use it so that the vertex id becomes the vector index

我真的想使用它，以便顶点id成为矢量索引

This is already the case with adjacency_list when you specify vecS for the VertexList parameter.

当您为VertexList参数指定vecS时，adjacency_list就是这种情况。

I need concurrent_hashmap (from Intel TBB) because I would be parallelizing my algorithm and so would desire concurrent access the to the property map which is going to be modified by threads.

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

You should look into using Parallel Graph library instead.

您应该考虑使用Parallel Graph库。

Please suggest whether is it possible to control and modify such underlying data structures in boost graph for storing edge and vertex properties.

请建议是否可以在boost图中控制和修改这些底层数据结构，以存储边缘和顶点属性。

You can specify the data structures used to store vertex and edge lists. And you can (theoretically) add new types of containers for those as well. However, this is really difficult, in my experience, because the implementation of adjacency_list is very hard to wrap your mind around, and swapping its underlying containers is not nearly as easy as advertised on the Boost website.

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