Boost logo

Boost Users :

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-09-06 15:24:55


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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net