Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk