What is a property map in BOOST?

Question

Can someone explain to a Boost beginner like me what is a property map is in Boost? I came across this when trying to use the BGL for calculating strong connected components. I went through the documentation for the property map and graph module and still don't know what to make of it. Take this code, for example:

• what is the make_iterator_property_map function doing?
• and what is the meaning of this code: get(vertex_index, G)?

---

#include <boost/config.hpp>
#include <vector>
#include <iostream>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/adjacency_list.hpp>

int main()
{
  using namespace boost;
  typedef adjacency_list < vecS, vecS, directedS > Graph;
  const int N = 6;
  Graph G(N);
  add_edge(0, 1, G);
  add_edge(1, 1, G);
  add_edge(1, 3, G);
  add_edge(1, 4, G);
  add_edge(3, 4, G);
  add_edge(3, 0, G);
  add_edge(4, 3, G);
  add_edge(5, 2, G);

  std::vector<int> c(N);
  int num = strong_components
    (G, make_iterator_property_map(c.begin(), get(vertex_index, G), c[0]));

  std::cout << "Total number of components: " << num << std::endl;
  std::vector < int >::iterator i;
  for (i = c.begin(); i != c.end(); ++i)
    std::cout << "Vertex " << i - c.begin()
      << " is in component " << *i << std::endl;
  return EXIT_SUCCESS;
}

Cerumen

I could just post all the documentation - what specifically don't you understand? It's a map (lookup) for properties. e.g. You can add names to edges, or colour to vertices. – Snath

+1. BGL would be far more useful if they had a decent default for property maps. The STL authors understood this, providing std::less as a default order for std::map. – Martita

@Martita Interesting. What would you consider a decent default in this particular example? With most property_maps the users needs a hold of them, how should that work here? – Natishanative

The default method of associating a value with an object is to make the value a member. I.e. struct Edge { float value; }. If you need more that one value, provide your own struct. Nothing really different from struct RGB { int R; int G; int B; }; std::vector<RGB>. BGL is so complex that I think you should roll your own in 90% of cases, using BGL only for the hardest 10%. Compare that to STL, which is sufficient for the simplest 90% of cases - the total opposite. – Martita

@Martita That way of associating values is one that has only been introduced in later versions and meta-programming with class members is painful as long as you don't have some introspection (like BOOST_FUSION_ADAPT_STRUCT) to help you. I had some code that introduces default property maps, iff your struct supports that, but it never went into the main branch. The consensus seems to be to leave BGL as it is rather than break it and go for a rewrite some time (at least one rewrite has already happened, but not up to Boost quality). – Natishanative

Answer 1

PropertyMaps at their core are an abstraction of data access. A problem that comes up very quickly in generic programming is: How do I get data associated with some object? It could be stored in the object itself, the object could be a pointer, it could be outside of the object in some mapping structure.

You can of course encapsulate data-access in a functor, but that becomes tedious very quickly and you look for a more narrow solution, the one chosen in Boost are PropertyMaps.

Remember this is just the concept. Concrete instances are for example an std::map (with some syntactic adaption), a function returning a member of the key (again, with some syntactic adaption).

Towards your edit: make_iterator_property_map builds an iterator_property_map. The first argument provides an iterator for a basis of offset calculations. The second argument is again a property_map to do the offset calculation. Together this provides a way to use an vertex_descriptor to write data to the vector based on the index of the vertex_descriptor.

Natishanative

could you elaborate on why encapsulating data-access in a functor would "becomes tedious very quickly"? – Selfdrive

For anyone struggling understanding Boost Property Maps and why (the heck) they are so important for the Boost Graph Library, I would recommand listening to the 2013 CppNow presentation by Boris Schaling. It makes a much nicer job than the documentation at introducing the concept :) – Selfdrive