Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net