[BGL] using biconnected_components with an exterior property map
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
Greg Landrum wrote:
[..] //------------ 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: [..] 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)?
If you want to use external property map for edges, you must use edge_index instead of edge_descriptor. But, you must provide edge_index property by yourself. See exterior_properties.cpp for example. -- Regards, Janusz
Janusz Piwowarski wrote:
Greg Landrum wrote:
[..] 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)?
If you want to use external property map for edges, you must use edge_index instead of edge_descriptor. But, you must provide edge_index property by yourself. See exterior_properties.cpp for example.
The example in exterior_properties.cpp seems to require that the graph have a boost::edge_index_t property map associated with its edges. If this is true, it means that in order to call biconnected_components on a graph that truly must be const, I need to modify the definition of my graph. Is this truly intended? -greg
Greg Landrum wrote:
Janusz Piwowarski wrote:
Greg Landrum wrote:
[..] 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)?
If you want to use external property map for edges, you must use edge_index instead of edge_descriptor. But, you must provide edge_index property by yourself. See exterior_properties.cpp for example.
The example in exterior_properties.cpp seems to require that the graph have a boost::edge_index_t property map associated with its edges. If this is true, it means that in order to call biconnected_components on a graph that truly must be const, I need to modify the definition of my graph. Is this truly intended?
I guess you need only number of biconnected components, don't you? If so, use dummy_property_map(). -- Janusz
Janusz Piwowarski wrote:
Greg Landrum wrote:
The example in exterior_properties.cpp seems to require that the graph have a boost::edge_index_t property map associated with its edges. If this is true, it means that in order to call biconnected_components on a graph that truly must be const, I need to modify the definition of my graph. Is this truly intended?
I guess you need only number of biconnected components, don't you? If so, use dummy_property_map().
erm, no. I need the assignments of the graph edges to the components. -greg
Yes, it sounds like you need to modify the type definition for your graph. (at least, that will give you the best efficiency. You could also use a hash table of some sort provided you don't have parallel edges in your graph) BTW, in the BGL, a const graph parameter means that the algorithm will not add or remove vertices or edges, but it does not necessarily mean that the algorithm will not modify properties of the edges or vertices... that is determined by the kind of property map that the algorithm requires, in this case the ComponentMap must be a Writable Property Map. HTH, Jeremy On Aug 25, 2005, at 8:23 AM, Greg Landrum wrote:
Janusz Piwowarski wrote:
Greg Landrum wrote:
The example in exterior_properties.cpp seems to require that the graph have a boost::edge_index_t property map associated with its edges. If this is true, it means that in order to call biconnected_components on a graph that truly must be const, I need to modify the definition of my graph. Is this truly intended?
I guess you need only number of biconnected components, don't you? If so, use dummy_property_map().
erm, no. I need the assignments of the graph edges to the components.
-greg _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Jeremy Siek wrote:
Yes, it sounds like you need to modify the type definition for your graph. (at least, that will give you the best efficiency. You could also use a hash table of some sort provided you don't have parallel edges in your graph)
Ok, thanks. The solution I've been using to the problem of "biconnected_components ate my graph!" is to copy the graph before making the call and to work from the copy. This seemed a cleaner solution than adding additional data to the graph itself in order to be able to call one algorithm (at least in the short term).
BTW, in the BGL, a const graph parameter means that the algorithm will not add or remove vertices or edges, but it does not necessarily mean that the algorithm will not modify properties of the edges or vertices... that is determined by the kind of property map that the algorithm requires, in this case the ComponentMap must be a Writable Property Map.
Thanks for this clarification. I was quite surprised to see a const graph parameter changing in an algorithm call, but now I see why. -greg
On Aug 24, 2005, at 10:56 AM, Greg Landrum wrote:
Janusz Piwowarski wrote:
Greg Landrum wrote:
[..] 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)?
If you want to use external property map for edges, you must use edge_index instead of edge_descriptor. But, you must provide edge_index property by yourself. See exterior_properties.cpp for example.
The example in exterior_properties.cpp seems to require that the graph have a boost::edge_index_t property map associated with its edges. If this is true, it means that in order to call biconnected_components on a graph that truly must be const, I need to modify the definition of my graph. Is this truly intended?
Yes and no. It is intended because there is no way to efficiently access a property map on edges without having an edge_index property or storing it the property on the edges themselves. The unintended consequence is that you have to modify your graph to use edge properties or create a special kind of property map that isn't entirely efficient. I'm hoping we can make exterior property maps for edges easier to use in the future, but for now you have only a few choices. Add an edge_index property (be sure to renumber the edges when you change the graph!), add properties directly to the edges in the graph, or use an associative property map. The problem (and, thus, the answer to your original question) is that edges can't be compared using "<", so the std::map fails. We can define a not-quite-correct-but-still-works function object for std::map like this: struct order_edges { template<typename T> bool operator()(const T& x, const T& y) const { return x.get_property() < y.get_property(); } }; Pass this as the third argument to std::map and the associative_property_map would work fine: typedef std::map< graph_traits<graph_t>::edge_descriptor, int, order_edges> map_t; map_t base_map; associative_property_map< map_t > component(base_map); Using this code, I was able to get the biconnected_components example working with exterior property maps. Doug
participants (4)
-
Doug Gregor -
Greg Landrum -
Janusz Piwowarski -
Jeremy Siek