From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-02-13 19:14:47
On Feb 13, 2006, at 4:56 PM, David Brumley wrote:
> for(i = 0; i < 50; i++){
> array[i] = i + 0x8000000;
> }
[snip]
> for(i = 0; i < 50; i++){
> add_edge(array[i % 50], array[ (i+1) % 50], g);
> }
> }
[snip]
> What am I doing wrong here? I would like to index each node in the
> graph
> by its address, which is in the range 0x8000000-0xffffffff. (I would
> rather not keep a separate index in the range 0-num(verticies)).
add_edge(u, v, g) works on vertex "descriptors", which abstractly
represent the vertex. Descriptors are somewhat like indices, but with
adjacency_list<> class decides how to do the indexing. When the
VertexListS template argument to adjacency_list is "vecS" (as in your
example), the vertex descriptors are values in [0, num_vertices(g)).
In that specific case, add_edge(u, v, g) has some interesting
behavior when u and v are values >= the number of vertices in the
graph: it silently expands the graph to accommodate u and v as
vertices. So those add_edge calls are trying to allocate another
space for 134M vertices, hence the bad_alloc.
Since the graph type essentially gets to decide what the descriptors
will be, you'll probably need to have an external mapping from
addresses to vertex descriptors.
Doug