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

5 Aug 2006


      Cromwell Enage wrote:
...
--- Alejandro Aragon  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