Re: [Boost-users] BGL memory inefficient/hog problem

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