On 6/4/07, Dominik Heide wrote:

Hi there,

I want to delete a vertex from a graph and later reinsert it again. I did this by removing all edges from that vertex and later adding the edges again. But the behavior of the program quite strange.

First, I use a undirected adjacancy list

typedef adjacency_list Graph;

When, use

Graph g, gs;

// set g

typename graph_traits<GraphT>::vertex_iterator vi, ve, vii, vei; typename graph_traits<GraphT>::out_edge_iterator out_i, out_end, tmp; for( tie(vi, ve) = vertices(g); vi != ve; vi++) { gs = g; clear_vertex( *vi, g)

// some code

g = gs; }

everything is fine. I don't want to save the whole graph since I only delete a couple of edges. Therefore, I did

vector deletedEdges; typename vector::iterator dei;

typename graph_traits<GraphT>::vertex_iterator vi, ve, vii, vei; typename graph_traits<GraphT>::out_edge_iterator out_i, out_end, tmp;

...

for( tie(vi, ve) = vertices(g); vi != ve; vi++) { for( tie( out_i, out_end ) = out_edges( *vi, g); out_i != out_end; out_i++) { deletedEdges.push_back(target(*out_i, g)); } clear_vertex( *vi, g)

// some code

for(dei = deletedEdges.begin(); dei < deletedEdges.end(); ++dei) { add_edge( *vi, *dei, g); } }

This code does not restore the graph completely. Although it looks the same the shortest paths are different to the ones with the above code.

Is there something about clear_vertex() I don't know and therefore don't restore corectly?

Any help appreachiated, Thank you, Dominik

Hi Dominik, There doesn't seem to be anything logically wrong with your understanding of clear_vertex. You say that the shortest paths are different after using clear_vertex and restoring the cleared edges - does this mean that you get a different shortest path tree, or that the length of the two shortest paths returned are different? The former isn't a problem, but the latter is. Can you come up with some kind of minimal snippet of code like the one you've sketched above that included a series of clear_vertex calls and adds the edges back such that the graph you end up with is different from the one you started with? Regards, Aaron