how is boost::property_map implemented in boost and how to change it

Question

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:

1. how are these properties are stored in the Graph object.
2. Is it stored in a map such as std::map<> ? or some list ? or some efficient map-like data structure.
3. 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.

Answer 1

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.