Hi, I'm trying to use the biconnected_components algorithm from v1.33 of the BGL in some code and I've encountered a problem that I just can't seem to get past. The algorithm requires a property map argument that's used to output which component each edge maps to; this is the argument that's giving me fits. I started with a simple-ish case derived from an example in the BGL docs: //------------------------------------------------------------------ namespace boost { struct edge_component_t { enum { num = 555 }; typedef edge_property_tag kind; } edge_component; typedef property< edge_component_t, std::size_t > edge_prop_t; } int main() { using namespace boost; typedef adjacency_list < vecS, vecS, undirectedS, no_property, edge_prop_t >graph_t; typedef graph_traits < graph_t >::vertex_descriptor vertex_t; graph_t g(5); add_edge(0, 1, edge_prop_t(3), g); add_edge(1, 2, edge_prop_t(3), g); add_edge(0, 2, edge_prop_t(3), g); add_edge(2, 3, edge_prop_t(1), g); add_edge(3, 5, edge_prop_t(1), g); typedef property_map < graph_t, edge_component_t >::type edge_map_t; edge_map_t edge_map = get(edge_component, g); graph_traits<graph_t>::edge_iterator edge,endEdges; for(tie(edge,endEdges)=boost::edges(g); edge!=endEdges;++edge){ std::cout << " >Edge1: " << source(*edge,g) << "-" << target(*edge,g) << " <- " << edge_map[*edge] << std::endl; } edge_map_t components = get(edge_component, g); std::size_t num_comps = biconnected_components(g, components); for(tie(edge,endEdges)=boost::edges(g); edge!=endEdges;++edge){ std::cout << " >Edge2: " << source(*edge,g) << "-" << target(*edge,g) << " <- " << edge_map[*edge] << std::endl; } return 0; } //------------------------------------------------------------------ When I run this, I get reasonable results for the connected components, but here's what prints:
Edge1: 0-1 <- 3 Edge1: 1-2 <- 3 Edge1: 0-2 <- 3 Edge1: 2-3 <- 1 Edge1: 3-5 <- 1 Edge2: 0-1 <- 2 Edge2: 1-2 <- 2 Edge2: 0-2 <- 2 Edge2: 2-3 <- 1 Edge2: 3-5 <- 0
Note that the graph's property map values for the edges have changed (Edge2 values vs Edge1 values). So calling biconnected_components() has modified the graph, even though the graph argument is const. This made me sad, but I figured that I should be able to work around it using an exterior property map. According to the docs: "The ComponentMap type must be a model of Writable Property Map. The value type shouch be an integer type, preferably the same as the edges_size_type of the graph. The key type must be the graph's edge descriptor type." So as my next experiment, I decided to attempt to use an associative property map matching these requirements. I tried to define components like this: //------------ typedef std::map< graph_traits<graph_t>::edge_descriptor, int > map_t; map_t base_map; associative_property_map< map_t > components(base_map); //------------ That doesn't compile, the definition of base_map generates an error whose explanation begins with: //---------------- C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\functional(139) : error C2784: 'bool std::operator <(const std::stack<_Ty,_Container> &,const std::stack<_Ty,_Container> &)' : could not deduce template argument for 'const std::stack<_Ty,_Container> &' from 'const boost::graph_traits<G>::edge_descriptor' with [ G=graph_t ] //---------------- My apologies for the horrible interaction between this message and gmail's line wrapping. If it's useful, I can send the entire error message as an attachment. I next tried to create some other kind of exterior property map, but the documentation for how to do this seems to be out of date. There's an explanation of this in the boost wiki at URL: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Documentation... search for "random_access_iterator_property_map" So my question is: how can I make a call to biconnected_components in a manner that doesn't modify my graph (or any of its associated property maps)? In the event that it matters, I'm building these tests under win2k using visual c++ 7.1 and boost v1.33. -greg