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