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

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

我的顶点和边属性定义如下：

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

我的图表的类型定义如下：

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

现在，在使用上面的 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

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

 //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 成为向量索引并且更高效 --> 但它可能会导致边缘问题

我的图将包含一百万个顶点和许多边，以这种方式搜索 std::map 仍然是 log(n) 本身，但我希望可移植性改变 底层数据结构，以便我可以使用 unordered_map /并发_hashmap

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

请建议是否可以控制和修改boost graph中的此类底层数据结构来存储边和顶点属性。

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

这些属性不会单独存储或类似存储。

顶点和边属性存储在图的顶点和边内。没有用std::map或一些其他关联容器。无论您向 adjacency_list 提供什么作为 VertexProperties 和 EdgeProperties 模板参数，都将存储在顶点和边中，即，与使用时相同std::list<T>其中 T 将存储在链表的节点中（以及必要的下一个指针）。换句话说，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 甚至并发_hashmap 或 boost::vector_property_map ？

您可以通过 OutEdgeList、VertexList 和 EdgeList 指定如何存储顶点和边。属性本身没有额外的存储方法。在这些上下文中使用映射或哈希图并没有多大意义。

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

当您指定时，adjacency_list 已经是这种情况vecS为了VertexList范围。

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

你应该考虑使用平行图 http://www.boost.org/doc/libs/1_55_0/libs/graph_parallel/doc/html/index.html图书馆代替。

请建议是否可以控制和修改boost graph中的此类底层数据结构来存储边和顶点属性。

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