Re: [boost] [BGL] auto index property maps in the boost vault

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-11-21 15:27:24

On Nov 19, 2005, at 12:12 PM, Aaron Windsor wrote:
> Auto index property maps are external property maps that were created
> with ease of use in mind. In short, whenever a vertex index map is
> expected for the graph g, you can substitute the expression
> "make_auto_vertex_index(g)" and everything will work as expected.
> Similarly, if an edge index property map is expected, you can use the
> expression "make_auto_edge_index(g)" instead.

Cool!

>  It's my hope that the
> auto index property maps will provide a quick solution to those
> looking to get started with the BGL who aren't yet worried about
> delving into the details of working with internal properties, which
> seems to be a difficult issue for a lot of beginners. Auto index
> property maps can be used while prototyping and replaced later with
> interior properties if efficiency is an issue.

This will definitely be very helpful.

I've only had a few minutes to look over this, so I only have two 
questions on the code itself:

1) edge_less_than seems more complicated than it needs to be. Instead 
of creating an integer inside edge_to_index_dispatch, then comparing 
the integers for two edges to order them, why not just have 
edge_less_than produce an ordering itself? That would avoid having to 
store the number of vertices in the edge_less_than predicate.

2) For the auto_index_property_map that allows duplicate keys, was 
there any particular reason to use a map of vectors instead of a 
multimap?

I also have some higher-level, non-code comments. The primary concern I 
have is that we're adding more functionality to the BGL to make it 
easier. It's the same thing we did with bundled properties: add a new, 
easier-to-use mechanism on top of what we already have. Unfortunately, 
features interact and I'm not entirely sure that we've managed to make 
life easier overall.

Auto-indexing maps are a great feature, but overall will they make it 
easier to learn and use the BGL? They will make some things easier: 
when users ask "why can't I call this algorithm with my 
adjacency_list?" we'll have the simple answer of "add 
edge_index(auto_edge_index_map(g))", followed by the obligatory "if you 
find that it's too slow, do this other thing" comment.

It seems that the way to make the BGL easier to use would be to make 
auto-indexing property maps automatic. When a BGL algorithm tries to 
pull out a vertex_index map, it checks the parameter list, then the 
graph itself, then falls back to generating an auto-indexing map. This 
would be convenient, but it also means that there are hidden 
performance penalties, which we've tried to avoid in the BGL.

What to do?

It's becoming more and more important to make the BGL easier to use 
out-of-the-box. I even think that most users will understand if at a 
later point in time they need to do a little work to get their code to 
give maximum performance, but we need to give them the tools to do so. 
For instance, I can imagine a macro BOOST_GRAPH_PERFORMANCE_WARNINGS 
that produces run-time warnings when the library is secretly building 
an auto-indexing map behind-the-scenes and a macro 
BOOST_GRAPH_PERFORMANCE_WARNINGS_ARE_ERRORS that causes compile-time 
errors instead.

But for now, I think once I understand (1) and (2), the auto-indexing 
property maps should go into CVS HEAD and we can discuss just how 
automatic we want to make them.

        Doug