External property map tied to std::vector in boost graph library

Question

I am currently trying to define external properties of a boost graph. I use some bundled properties as internal ones:

struct VertexProperties
{
  int demand;
};

struct EdgeProperties
{ 
  uint capacity;
  int cost;
};

typedef adjacency_list <vecS, vecS, bidirectionalS, VertexProperties, EdgeProperties> Graph;

However, during the algorithm I need some external properties, that is I want to be able to map edges/vertices of my graph to elements stored in a std::vector in such a way that I can access them via operator[] (Edge e). I am standing in front of the boost documentation without a clue. It seems like I need a property_map, but I don't know how to use these together with vectors. The only examples that I found so far concern maps from vertices to a vector, but as the vertices are unsigned ints this is trivial.

I am really frustrated by boost so far, I think it would have saved me a lot of time to implement and test a graph class by myself, I really don get this crazy template metaprogramming stuff...

Answer 1

You can create external property maps regardless of what internal and/or bundled properties are in your graph. Creating property maps on edges is somewhat more difficult because you need an edge_index map, and adjacency_list doesn't have those by default; compressed_sparse_row_graph does but its structure is mostly read-only after construction. You can either use associative_property_map on the edges, or create an edge index map as an internal property (if you don't change your graph too often), fill it, then use it to build the external property map (using shared_array_property_map, for example).

Answer 2

I ran into the same problem recently, and here is how I ended up attaching a vertex property (called degree in this code snippet):

// Graph has to have _index_ property (vector-based graphs get it implicitly)
typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
// Storage type for the _degree_ property
typedef std::vector<uint> DegreeVector;
// Type of the _degree_ property map
typedef iterator_property_map<typename DegreeVector::iterator, IndexMap> DegreeMap;

// Graph in question
Graph g(5);
// Actual storage
DegreeVector degree_storage(num_vertices(g));
// This is needed to construct _degree_ property map
IndexMap index_map = get(vertex_index, g);
// Create _degree_ property map
DegreeMap degree_map = make_iterator_property_map(degree_storage.begin(), index_map);

// Now degree_map is ready to be used
degree_map[some_vertex_id] = 10;