map implemented in boost and how to change it
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: ie using
//former is translated to the latter -->
get(NodeInfoPropertyTag(), G, "key") is equivalent to get (NodeMap, "key")
My question is:
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, ie, 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 (eg, 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.
链接地址: http://www.djcxy.com/p/51058.html上一篇: boost图形从txt文件循环创建图形
下一篇: 在boost中实现的地图以及如何更改它