Re: [Boost-users] [Graph] remove edges and reinsert them

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-06-05 21:54:23

On 6/4/07, Dominik Heide <dheide_at_[hidden]> 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<vecS, vecS, undirectedS, no_property, no_property>
> 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<typename graph_traits<GraphT>::vertex_descriptor> deletedEdges;
> typename vector<typename graph_traits<GraphT>::vertex_descriptor>::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