to convert internal properties in boost graph to external properties container in boost graph

Question

With reference to the code mentioned in my question here enter link description here, I want to convert the internal properties

 struct NodeInfo {  int a , b , c; }; 
 struct EdgeInfo {  int timestamp; ... };
 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;

I want to use these properties as external graph properties. So my graph will become something like

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

In the previous code, property_maps were defined, graph was initialized, and to modify vertex or edge properties, I used a tag class to identify each vertex or edge and used this:

   //get
   NodInfo   info  =  boost::get (NodeInfoPropertyTag(), G, v) 

   //put 
    put (NodeInfoPropertyTag(), G, v, info)

Now, I want to make these NodeInfo and EdgeInfo as external properties: for_each(vertex) : store every vertex's property in a vector (say) for_each(edge) : store every edge's property in a vector (say)

I have seen similar questions on stackoverflow for adding/modifying external properties but unfortunately couldnt get it working for my requirements.

I wrote a iterator property map based on solution suggested in this code. I could use get() and put() functions as well : HERE

I want to write my own get() and put() function (in my own namespace) which instead of calling boost::get() and boost::put() but I need my implementation to be the same as that of boost::get() and put():

ie.
using namespace my_space {
  template <typename tag_t, typename graph_t, typename key_t, typename value_t>
  value_t get (tag_t tag, graph_t& G, key_t& key) {
  //TODO
  //return  from external property map  -->  vector map 
  }

  template <typename tag_t, typename graph_t, typename key_t, typename value_t>
  void put (tag_t& tag, graph_t&G, key_t& key, value_t& value) {
   //TODO
   // put in external property map
  }

1. Somehow I need a mechanism to use Tag_type and graph_t which will give me the actual external property map. i.e. :

   //when I use this, NodeInfo ninfo = my_space::get(my_vertex_tag, G, v); --->

   // it should call get() from my namespace and return the content of external container

   put (my_edge_tag, G, key, value) --> call my implemented put, --> insert or modify the property in vector for edge e which has index = key ( I dont know how exactly to link each edge_descriptor to a unique edge_index but i am working on it )

I read the documentation, but somehow I am not able to link the internal properties to the external properties. Is there any alternative to iterator property map? Can I use associative property map for storing vertex_properties externally ? My only requirement is: I want to use tags and graph G as parameters to get() and put(). There can be several tags and their corresponding external property containers and that get() and put() call should resolve to that particular container. Could I possible use template specialization for get() and put() ? I am not so sure how to do it

Reason: to reduce the size of Graph object G (because millions of edges and nodes) graph storing/serialization is easier comparatively.

please let me know if the questions is not clear

Answer 1

The best solution for this that I can see would be to use the iterator property map and then lock when you access it.

You will need a map to vertex indexes and a container then you will create an external property map.

//typedef an index map for vertex
typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap;

//Get the actual graph's vertex indexmap
VertexIndexMap vertexIndexMap = get(boost::vertex_index, G);

//Create a container with size equal to verts in G
vector<double> vertexWeights(num_vertices(G));

//Create the property map
boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
    vertexWeightMap(vertexWeights.begin(), vertexIndexMap);

This creates an iterator_property_map. This doesn't imply anything about the performance of using iterators. It maps a vertex_descriptor to an iterator (offset) in the container. I believe it uses unordered_map so the mapping is O(1) constant time.

This is the method I routinely use to wrap containers for use with boost graph.

To ensure that this container is synchronized you should lock access to it using a mutex. Check out using mutex locks. http://www.boost.org/doc/libs/1_55_0/doc/html/thread/synchronization.html

Or if you are using TBB as you mention in the other question I'm sure TBB will have their own mutexes and they may be better suited to your threading.

Finally consider why you are doing this. You need the container to be able to use boost tags. Why? Probably to take advantage of some built in boost algorithms. That's fine, but I don't think you will squeeze any extra performance out of the boost graph algorithms by using threads without tremendous effort. It will be difficult to speed up canonical graph algorithms (shortest path, min spanning tree,BFS,DFS) without a lot of effort and communication overhead. If you want to speed up stuff like Betweenness or Dijkstra, use a simpler algorithm and parallelize the all-pairs part. Maybe asking a question about the algorithm you are trying parallelize will get better responses.