[BGL] connected components algorithm

4 Aug 2006

      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.  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.  It seems that the compiler does
not recognize this function.

/usr/include/boost/graph/connected_components.hpp:46: error: no matching
function for call to ‘put(unsigned int*&, void*&, unsigned int&)’
make: *** [graph.o] Error 1

Any ideas?  Thank you,

aa

My code is shown below:

    typedef adjacency_list,
	no_property
        > graph_t;

    graph_traits::out_edge_iterator out,out_end;
    graph_t copy(num_vertices(*gPtr));

    // obtain a property map for the vertex_index property
    property_map::type
    index = get(vertex_index, copy);

    // initialize the vertex_index property values
    graph_traits::vertex_iterator vi, vend;
    graph_traits::vertices_size_type cnt = 0;
    for(tie(vi,vend) = vertices(copy); vi != vend; ++vi)
	put(index, *vi, cnt++);

    for (tie(ei, ei_end) = edges(*gPtr); ei != ei_end; ++ei){
	add_edge(vertex(source(*ei,*gPtr), copy),
vertex(target(*ei,*gPtr), copy), copy);	
    }

    graph_traits::vertex_descriptor Vertex;
    graph_traits::edge_iterator ei,ei_end;

    vertex_descriptor u,v;
    u = vertex(0,copy);

	for (tie(out, out_end) = out_edges(u,copy); out != out_end; ++out){

	    u = source(*out,copy);
	    v = target(*out,copy);

 	    remove_edge(u,v,copy);

	    std::vector component(num_vertices(copy));
	    num = connected_components(copy, &component[0]);

Alejandro Aragon

Cromwell Enage

Alejandro Aragon

tags

participants (2)