Re: [Boost-users] [BGL] Properties in a set-based adjacency list

Subject: Re: [Boost-users] [BGL] Properties in a set-based adjacency list
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-02-13 08:46:28

>
> How can I use an external property map with an adjacency list which uses a
> setS for the vertex list? I got property maps (with arrays as storage for
> the property values) working fine with a vecS adjacency list, but I can't
> seem to get them to work after changing the template to setS. I understand
> the reason is lack of automatic indexing, but don't know how to get around
> that. Using set/map for storage of property values would most convenient for
> me.
>
> On a similar note, perhaps it's possible to use a map to store the
> vertices, mapping ints to Vertex descriptors? (that was the original custom
> implementation of graph class which I'm porting to BGL).
>

Not easily :) [Why do all of my responses seem to start this way?]

Your solution is actually pretty close to correct, although you should
prefer to use an unordered_map to retain constant time lookups. There are
two parts to a property map: the container and the map. The container
actually implements the mapping and the (property) map abstracts it to the
syntax required by the BGL algorithms. For example, you might have:

typedef unordered_map<Vertex, int> IdMap;
typedef associative_property_map<IdMap> IdPropMap;

IdMap ids(num_vertices(g));
IdPropMap idmap(ids)
foreach(v, vertices(g)) { // Probably won't work
  put(idmap, v, i++)
}

Andrew Sutton
andrew.n.sutton_at_[hidden]