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

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-11-29 11:11:51

On Nov 22, 2005, at 7:23 AM, Aaron Windsor wrote:

> On 11/21/05, Doug Gregor <dgregor_at_[hidden]> wrote:
>
> <snip>
>
>> 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.
>
> Do you mean that edge_less_than should be a stateful predicate,  
> creating
> an ordering as it goes along (first edge it sees is ranked 1,  
> second edge is
> ranked 2, etc.?) Because this scheme would make lookup in a map an
> log^2 n operation - at each node in the tree, a rank lookup costing  
> log n needs
> to be made in order to figure out where to go next. Maybe I'm  
> misunderstanding
> you?

I believe I was actually thinking of a requirement for operator<  on  
the key type of the auto-index property map. Users have been asking  
for the ability to compare vertex and edge descriptors with <for a  
long time, and I believe we can provide it for all of the graph types  
in the BGL. It would simplify the auto-index property maps a bit, and  
help users overall.

Granted, the problem remains that we essentially need to know whether  
the less-than operator for the key type is a total order (so we can  
use std::map) or only a partial order (we need to use std::multimap):  
perhaps assume it's a partial order, but have a trait  
is_totally_ordered<Key> that will be specialized to tell us when we  
can use the std::map.

> In the boost-users thread that I linked to in the original post, I
> suggested that
> get(vertex_index, g) return an auto index if there was no interior  
> index. You
> thought this was a bad idea at the time, too misleading for the  
> user, and I
> tend to agree with your earlier self. I came to like the idea of  
> saying
> "make_auto_vertex_index" and "make_auto_edge_index" as an  
> acknowledgement
> of the fact that you, as a user, realize that the algorithm needs  
> an index on
> the vertices or edges, and realize that you don't have one, but  
> still want the
> algorithm to work.

My earlier self hadn't received quite as many complaints about the  
usability of the BGL :(

My concern is that we lose people when they try an algorithm and get  
some big error message. If they ask on the list, we'll just tell them  
to us make_auto_vertex_index or make_auto_edge_index and everything  
will work perfectly; but if they don't ask, we'll probably have lost  
them completely. Granted, I think adjacency_list is a bigger initial  
problem: if we had an easy-to-use graph type (or two) that had built- 
in vertex and edge index property maps, users wouldn't see these  
problems. Then, when they decide to tweak a bit more, they could move  
to adjacency_list<> and use auto-index property maps where necessary.

In any case: as soon as we figure out whether we should use/require  
operator< on keys to the auto-index property map, please go ahead and  
integrate your code and documentation into CVS HEAD.

        Doug