Re: [Boost-users] [BGL] connected components algorithm

From: Alejandro Aragon (aaragon2_at_[hidden])
Date: 2006-08-05 06:54:08

Cromwell Enage wrote:
> --- Alejandro Aragon <aaragon2_at_[hidden]> wrote:
>> Hello everyone.  I'm trying to implement Fleury's
>> algorithm to find an Eulerian path in a graph.
>> Every time I erase an edge in the graph, I need
>> to check how many connected components I have
>> (because I can't erase an edge that is a
>> "bridge").  Also, I was using in the beginning
>> graphs with VertexList=VecS but it turns out
>> that when you erase an edge all the vertex
>> descriptors are invalidated.
> 
> Vertex descriptors should only be invalidated upon a
> remove_vertex call, not a remove_edge call.
> 

Yes, you're right.  I didn't include all the code but of course I have
to remove a vertex to work with the connected components algorithm.  The
reason behind this is that if you remove all the edges from a vertex,
you end up having 2 or more components.  Therefore, once all the edges
from a vertex are removed, then you have to remove the vertex so that
the connected components can give you only 1 component.

>> Thus, I had to copy my graph to another one with
>> VertexList=listS.
>>
>> I was wondering if the connected components
>> algorithm works with this type of graph.  I'm
>> having an error.
> 
> An adjacency_list with VertexList=listS does not
> automatically contain a vertex_index property map, as
> it would with VertexList=vecS.

I know this also, and if you look at the code, then you'll see that
before I copy all the information I need from the previous graph, then I
 assign indexes using a property map.

> 
>                               HTH,
>                               Cromwell D. Enage
> 
> 
> __________________________________________________
> Do You Yahoo!?
> Tired of spam?  Yahoo! Mail has the best spam protection around 
> http://mail.yahoo.com 

I was thinking in another way to solve this problem.  It would be nice
if the connected components  could work only on a subgraph of an
existing one.  Let's say that you just color the edges and vertexes that
you don't want the algorithm to work on.  In this way, I don't need to
remove edges from the graph and the VertexList=vecS is still valid for
my problem.  I would have to define another visitor for this but I
really don't know how to do this.  Even though I know how to program in
C++, I don't know much about generic programming.

Alejandro Aragon