是如何的boost :: property_map在推动实施，以及如何去改变它 [英] how is boost::property_map implemented in boost and how to change it
问题描述
我想知道的属性映射如何在提振图形来实现。例如，
我有这样定义的顶点和边属性：
//顶点属性： - ＆GT;
结构的nodeinfo {int的A，B，C; }; //实际的捆绑物业
结构NodeInfoPropertyTag {//标签和种类（如升压文档）
TYPEDEF提振:: vertex_property_tag样;
静态的std ::为size_t常量NUM;
};
的std ::为size_t常量NodeInfoPropertyTag :: NUM =（标准::为size_t）及NodeInfoPropertyTag :: NUM;
//类型定义的顶点属性
TYPEDEF提振::财产和LT; NodeInfoPropertyTag，将nodeinfo＆GT; NodeProperty;
//类似的时尚边缘物业 - ＆GT;一些属性图的每个边缘。
TYPEDEF提振::财产和LT; EdgeInfoPropertyTag，EdgeInfo＆GT; EdgeProperty正是;
我的图表typedef定义如下：
的typedef的boost ::的adjacency_list＆LT; vecS的，vecS的，undirectedS，NodeProperty，EdgeProperty正是，no_property，列表＆GT; Graph_t;
现在，在初始化使用上面的typedef克图，我可以用的属性分配属性点和边
有关，例如：
Graph_t G组;
的typedef graph_traits＆LT; Graph_t＆GT; ::顶点描述vd_t;
// edge_descriptor ed_t;
将nodeinfo ninfo1，ninfo2; //把一些值n信息
vd_t V = add_vertex（ninfo1，G）//在G中增加一个顶点财产ninfo1
vd_t U = add_vertex（ninfo2，G）//在G中增加一个顶点财产ninfo2
EdgeInfo einfo; //初始化edgeinfo的边属性
的add_edge（U，V，einfo，G）边（u，v）的财产einfo在G中添加
要访问任何顶点的节点属性我可以用任何的2种方法如下：
//方法1：直接法：使用标签
//为顶点的V - ＆GT;得到（）
NodInfo信息=提振::得到（NodeInfoPropertyTag（），G，V）//获取五世的财产
//修改信息
//把修改的属性
放（NodeInfoPropertyTag（），G，V，资讯）//（放在G，关键= V，值=信息）
//方法二：使用属性映射。
//边缘地图和节点地图
的typedef typename的提振:: property_map＆LT; Graph_t，EdgeInfoPropertyTag＆GT; ::类型EdgeMap;
的typedef typename的提振:: property_map＆LT; Graph_t，NodeInfoPropertyTag＆GT; ::类型NodeMap;
//边e - ＆GT;得到
EdgeInfo einfo =提振::得到（EdgeMap，E）
//修改einfo
//放
放（EdgeMap，E，einfo）//放在EdgeMap键= E，值= einfo
现在，无论是操作基本上是相同的：即采用
//前者转换为后者 - ＆GT;
得到（NodeInfoPropertyTag（）中，G，钥匙）等效于得到（NodeMap，钥匙）
我的问题是：
- 如何在这些属性将存储在图形对象。
- 是它存储在一张地图，如std ::地图＆LT;>？或者一些名单？或者一些有效的地图状的数据结构。
- 如果是这样，我怎么可以修改底层的数据结构为std :: unordered_map甚至 concurrent_hashmap或升压:: vector_property_map？
请注意： 我不知道我可以使用vector_prop_map（在这里），但我真的很喜欢使用它，使 顶点ID变为矢量指数更有效率 - >它可能会导致问题的边缘，虽然
My图表将包含一万个顶点和许多许多边缘，以这种方式在搜索中 在std ::地图＆LT;>仍然会的log（n），因为这样，但我想在便携性改变 底层的数据结构，这样我就可以使用unordered_map / concurrent_hashmap
我需要concurrent_hashmap（英特尔TBB），因为我将我的并行算法 所以会想要并发访问的属性映射这将是 通过线程修改。
请建议是否是有可能控制和修改这样的底层数据结构在升压图形，用于存储边缘和顶点属性
如何在这些属性将存储在图形对象。
的属性不是单独或任何存储类的。
的顶点和边缘的属性存储在顶点和图形的边缘内。有没有使用的std ::地图或其它关联容器。无论你提供的VertexProperties和EdgeProperties模板参数将被存储在顶点和边，即的adjacency_list，它是一样的，当你使用的std ::名单＆公升; T＆GT; 其中T将被储存在连接表的节点（以及必要的next- $ P $光伏指针）。换言之，将的adjacency_list存储包含类型VertexProperties的对象的顶点，加上任何边缘列表（输入和输出）所需要
在使用 property_map （通过GET / PUT功能），它只是做了一些模板元编程的魔法就形成了一层包装，将刚读/写入正确的个人财产的顶点或边。概念上，这是等价
的nodeinfo信息=的boost ::得到（NodeInfoPropertyTag（），G，V）;
//是概念等同于：
将nodeinfo信息= G [V] .NodeInfoProperty;
这是所有的属性映射确实，它查找顶点属性（由顶点描述符中给定的图形对象），它提取对应的顶点属性的数据成员（或子对象）给定的标签类型。搞清楚如何获取正确的数据成员（或子对象）为正确的属性标记是一块模板元编程魔法的数字出来，在编译时（不运行时开销）。而且，在一般情况下，查找从顶点描述符的顶点属性是一个固定时间操作（例如，解引用一个指针，查找由指数，等）。
总的来说，提取（读或写）的特定顶点的特定属性是一个固定时间操作。这适用于任何的选择您与的adjacency_list的模板参数，因为据我所知。
如果是这样，我怎么可以修改底层的数据结构为std :: unordered_map甚至concurrent_hashmap或升压:: vector_property_map？
您可以指定希望顶点和边进行存储，通过OutEdgeList，VertexList时，和EdgeList都。没有额外的存储方法的属性本身。而使用地图或包含HashMap并没有真正太大的意义在这些情况下。
我真的很喜欢用它，这样的顶点ID变为矢量指数
这是已经与的adjacency_list在指定的情况下 vecS的为 VertexList时，参数。
我需要concurrent_hashmap（英特尔TBB），因为我会并行我的算法，因此会渴望并发访问的属性映射，这是会被线程进行修改。
您应该考虑使用并行图库，而不是。
请建议是否是有可能控制和修改这样的底层数据结构在升压图形，用于存储边缘和顶点属性
您可以指定用于存储顶点和边列表的数据结构。你可以（理论上）增加新的类型的容器对那些为好。但是，这真的很难，在我的经验，因为的adjacency_list的实施是非常困难的周围包裹你的头脑，并交换其底层的容器是几乎没有那么容易，因为广告上的升压网站。
I was wondering how the property maps are implemented in a boost Graph. For example,
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 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
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:
- how are these properties are stored in the Graph object.
- Is it stored in a map such as std::map<> ? or some list ? or some efficient map-like data structure.
- If so, how can I modify the underlying data structure to std::unordered_map or even concurrent_hashmap or 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
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
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.
Please suggest whether is it possible to control and modify such underlying data structures in boost graph for storing edge and vertex properties.
how are these properties are stored in the Graph object.
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.
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:
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.
If so, how can I modify the underlying data structure to std::unordered_map or even concurrent_hashmap or 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.
I would really like to use it so that the vertex id becomes the vector index
This is already the case with adjacency_list when you specify vecS for the VertexList parameter.
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.
You should look into using Parallel Graph library instead.
Please suggest whether is it possible to control and modify such underlying data structures in boost graph for storing edge and vertex properties.
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.
这篇关于是如何的boost :: property_map在推动实施，以及如何去改变它的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
