[Boost-users] how to clear a Graph

From: Ufuk Okuyucu (ufuk.okuyucu_at_[hidden])
Date: 2006-12-01 12:50:50

Hi,
I've just been handed a code using boost's cuthill-mckee algorithm. I 
found a memory leak within the code block where a number of edges being 
added to a graph but never cleaned at the end.

Now, graph has a "clear" method where it's supposed to delete vertices 
and edges but it does not effect the memory leak, when I check the used 
memory size its still there. I need a way to delete a graph object and 
free all its internal mallocations if any.

...and I haven't used boost before...

Here is the code block:

//create incidence graph G2 from adj_list
//apply cuthill-mckee on G2
//write out resulting permutation to perm_result

Graph G2(matrix_size); //Graph data structure used in Cuthill-Mckee

//add all the edges in adj_list to G2
for(int row=0;row<matrix_size;row++) {
for(ROW_ADJ::iterator col=adj_list[row].begin(); col != 
adj_list[row].end(); col++) {
add_edge (row, *col, G2); //<<-----this is where it gets all that memory

}
}

cout <<"edges added\n";
print_system_stats();

graph_traits<Graph>::vertex_iterator ui, ui_end;

property_map<Graph,vertex_degree_t>::type deg = get(vertex_degree, G2);
for (boost::tie(ui, ui_end) = vertices(G2); ui != ui_end; ++ui)
deg[*ui] = degree(*ui, G2);

property_map<Graph, vertex_index_t>::type
index_map = get(vertex_index, G2);

//printf("original bandwidth: %d\n",bandwidth(G2));
printf("# vertices: %d\n",num_vertices(G2));
printf("# edges: %d\n",num_edges(G2));

vector<Vertex> inv_perm(num_vertices(G2));
vector<size_type> perm(num_vertices(G2));

Vertex start_vertex = vertex(0,G2);

cuthill_mckee_ordering(G2, start_vertex, inv_perm.rbegin(), 
get(vertex_color, G2), get(vertex_degree, G2));

for (size_type c = 0; c != inv_perm.size(); ++c)
perm[index_map[inv_perm[c]]] = c;

//cout << " bandwidth: " << bandwidth(G2, 
make_iterator_property_map(&perm[0], index_map, perm[0])) << endl;

//perm has the new ordering, copy it to perm_result
for (int i=0;i<matrix_size;i++)
perm_result[i] = perm[i];

G2.clear(); //<<-------this statement does not release all the memory
inv_perm.clear();
perm.clear();
-- 
* Ufuk Okuyucu**
*