Re: [Boost-users] Can't link subgraphs because remove_vertex is a TODO

Subject: Re: [Boost-users] Can't link subgraphs because remove_vertex is a TODO
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-10-19 12:20:28

On Wed, 13 Oct 2010, Trevor Harmon wrote:

> Hi,
>
> I have two directed subgraphs that I want to link together in a particular 
> way. To illustrate:
>
> BEFORE
> 1 ---> 2 ---> 3
> 4 ---> 5 ---> 6
>
> AFTER
> 1 ---> 2 ---> 3
> \---> 5 ---> 6
>
> Note that vertex 4 is removed, and the edge that was linking 4 to 5 now links 
> 1 to 5.
>
> Seems simple enough, but there are two problems, one minor and one major:
>
> 1) To rewire the edge's source from 4 to 1, I'd like to simply change the 
> edge's source. But that doesn't seem possible in Boost. It appears I must 
> remove the edge and add a new one with the desired source. This can get 
> complicated when it comes to preserving the edge's properties, index maps, 
> and such, but hey, at least it's doable.

Yes, you do need to remove the edge and re-add it.  Remember that changing 
an edge's source in an adjacency list structure does not just involve 
changing one value, but removing the edge from one list and adding it to 
another.  Thus, changing the source vertex is basically the same as 
removing the edge and re-adding it with the new source.

> 2) This one I can't work around. Calling remove_vertex on a subgraph gives an 
> assertion failure:
>
> Assertion failed: (false), function remove_vertex, file 
> /usr/local/boost_1_43_0/boost/graph/subgraph.hpp, line 733.
>
> It turns out that subgraph's remove_vertex method is not implemented at all, 
> which is quite the showstopper for my project. I don't know enough about 
> Boost to implement it myself. Any suggestions? Thanks,

I've now #if 0'ed it out so code using remove_vertex on subgraphs no 
longer compiles, rather than getting a run-time error.  I don't know the 
code well enough to implement it either.  What exactly are you trying to 
do with subgraphs?  Maybe there is another way to do it that doesn't hit 
these problems.

-- Jeremiah Willcock