[BGL] connected components algorithm
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<listS, listS, undirectedS, property<vertex_index_t, std::size_t>, no_property > graph_t; graph_traits<graph_t>::out_edge_iterator out,out_end; graph_t copy(num_vertices(*gPtr)); // obtain a property map for the vertex_index property property_map<graph_t, vertex_index_t>::type index = get(vertex_index, copy); // initialize the vertex_index property values graph_traits<graph_t>::vertex_iterator vi, vend; graph_traits<graph_t>::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<graph_t>::vertex_descriptor Vertex; graph_traits<graph_t>::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<size_t> component(num_vertices(copy)); num = connected_components(copy, &component[0]);
--- Alejandro Aragon <aaragon2@uiuc.edu> 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.
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. HTH, Cromwell D. Enage __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
Cromwell Enage wrote:
--- Alejandro Aragon <aaragon2@uiuc.edu> 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
participants (2)
-
Alejandro Aragon -
Cromwell Enage