[Boost-users] [BGL] using biconnected_components with an exterior property map

From: Greg Landrum (greg.landrum_at_[hidden])
Date: 2005-08-22 19:52:17

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_-_Graph_Library
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