CODEWITHSUNDEEP
c++boostboost-graph
Neel Basu
Neel Basu

Reputation: 12904

BGL indexing a vertex by keys

My requirement is to have a graph structure where each vertex is uniquely identified by a boost::uuids::uuid. All vertices have a color property by which vertices of similar category will be grouped. I am not working on a static map, vertices and edges will be created and removed dynamically.

typedef boost::adjacency_list<
      boost::listS,
      boost::listS,
      boost::bidirectionalS,
      boost::property<boost::vertex_index_t, boost::uuids::uuid, 
        boost::property<boost::vertex_color_t, resource_color,
          boost::property<boost::vertex_underlying_t,   boost::shared_ptr<actual_object*> > > >,
      detail::edge_property
      > graph_type;
graph_type _graph;
boost::property_map<graph_type, boost::vertex_index_t>::type    _index_map;
boost::property_map<graph_type, boost::vertex_color_t>::type    _color_map;
boost::property_map<graph_type, boost::vertex_underlying_t>::type   _underlying_map;

In constructor I am creating all 3 maps

_index_map = boost::get(boost::vertex_index_t(), _graph);
_color_map = boost::get(boost::vertex_color_t(), _graph);
_underlying_map = boost::get(boost::vertex_underlying_t(), _graph);

while adding a vertex

add_resource(resource_color c, actual_object* o){
  graph_type::vertex_descriptor v = boost::add_vertex(o->uuid(), _graph);
  _color_map[v] = c;
  _underlying_map[v] = o;
}

For listing UUID's of a vertex

uuid_list list;
boost::graph_traits<graph_type>::vertex_iterator vi, vi_end;
for(boost::tie(vi, vi_end) = boost::vertices(_graph); vi != vi_end; ++vi){
  list.push_back(_index_map[*vi]);
}
return list;

This way i am always iterating through vertices of the graph and getting its properties. However I want the other way too. From UUID to vertex like a parallel std::map which will be auto updated with add/remove operations or somethign similar.

Also I cannot keep an external std::map and sync manually, because boost::adjacency_list<boost::listS, boost::listS>::vertex_descriptor evaluates to void* and I need serialization support.

So is the following things doable

  1. find vertex through boost::vertex_index_t value
  2. iterate through a boost::property_map
  3. synchronizing an external std::map or bimap with index property

Upvotes: 2

Views: 1656

Answers (1)

sehe
sehe

Reputation: 393934

I remember the library has a labeled_graph utility that supports this roughly. It has a high convenience factor and I seem to remember it being less interesting in terms of efficiency¹. There should be a sample using it:

Regardless (and referring back to your previous question) you can certainly use an external property map. This has benefits:

  • you can keep entries that aren't in the graph at all times

  • you can have the reverse index that you require, see e.g.

    • Cut set of a graph, Boost Graph Library (where it is used to get reverse-lookup of the colour map).

      It also contains an equivalent approach but using Boost Multi-index Containers, which is much more flexible even

Answer bullets:

  1. find vertex through boost::vertex_index_t value

    Yes, but if you want to be efficient, indeed you need to either have an external mapping for the reverse lookup OR use your own datastructure and adapt it to model the Graph Concepts you require (much more work, obviously)

  2. iterate through a boost::property_map

    You can. Use boost::get(tag, graph) to get the property map, iterate across all entities you want to visit and invoke the property map for each property. E.g.

    boost::property_map<Graph, boost::vertex_index_t>::type pmap = boost::get(boost::vertex_index, graph);
boost::graph_traits<Graph>::vertex_iterator b, e;
for (boost::tie(b,e) = boost::vertices(graph); b!=e; ++b)
    std::cout << "The vertex ID is: " << boost::get(pmap, *b) << "\n";

  3. synchronizing an external std::map or bimap with index property

    The above links should give you ideas

¹ that would explain I haven't used it myself.

Upvotes: 3

Related Questions