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