Re: [Boost-users] Could the BGL graph algorithms be improved to automatically work with VertexList = listS graphs?

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2005-09-15 11:55:34

On 9/15/05, Jeremy Siek <jeremy.siek_at_[hidden]> wrote:
> Hi Doug,
> 
> On Sep 14, 2005, at 9:01 PM, Douglas Gregor wrote:

<snip>

> > I've been thinking of a few ways to try to help users with creating
> > and using property maps. It's possible that "all of them" is the
> > right answer:
> >
> >      1) Make edge descriptors ordered (via <), so that users can make
> > associative property maps more easily
> >      2) Create templates vertex_property_map<T, Graph> and
> > edge_property_map<T, Graph> that create external property maps
> > without much effort from the user; in particular, that'll use an
> > associative property map or an iterator property map depending on
> > whether a vertex_index property is available.
> >
> >      3) As Tony mentions, make the algorithms a bit more lenient
> > about the input graphs. They could use something like the class
> > templates in #2, so long as we can still get maximal efficiency out
> > of them when index maps are available.
> >
> >      4) Create new graph types (say, directed_graph<Vertex, Edge> and
> > undirected_graph<Vertex, Edge>) that maintain vertex and edge index
> > maps internally (as does the Python graph type).
> 
> All of those options sound reasonable.

All of Doug's options sound good to me, too, and I'd like to add one more 
idea. Most of the BGL algorithms operate on the assumption that if you 
don't pass in a vertex or edge index map explicitly, that index map should 
be accessible as an internal property, for instance, something like:

template<typename Graph, typename VertexIndexMap>
void foo(const Graph& g, VertexIndexMap vim = get(vertex_index,g));

In the above code, if g doesn't have a vertex_index property, no_property
is returned from the get. What I'm thinking about is returning something
other than no_property: consider another type of property map, which I'll 
call auto_index_property_map. It's got two data members: a shared_ptr 
to an associative container and an integer index called next_available_index. 
Its default constructor creates a new associative container, while the
copy constructor and assignment operator just copy over the shared_ptr.
When you call "get" on an auto_index_property_map for an element x, it 
checks to see if x is a key in the associative container. If it is, return the 
index x is associated with. If not, put the pair (x,next_available_index) in 
the container and return next_available_index and post-increment it.

The main problem I can see with this solution is that if you call
get(vertex_index,g) twice you get distinct instances of an 
auto_index_property_map, containing different associative containers. This 
could cause some pretty spectacular failures and might be a tough bug
to catch within an algorithm. But from what I've seen, getting the 
vertex_index or edge_index property is usually done once by the algorithm, 
as in foo's signature above, so that all we would need to do is change the 
behavior of get(vertex_index,g) and get(edge_index,g) to return an
auto_index_property_map. I'd be willing to code up an 
auto_index_property_map if anyone likes this idea, otherwise I vote for 
Doug's #4 above.

Aaron