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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2005-12-01 07:12:19

On 11/29/05, Douglas Gregor <doug.gregor_at_[hidden]> wrote:
>
> 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.

Well, the code in the vault does provide a generic < operator for
edges (edge_less_than, in the file edge_to_index.hpp), which provides
a total order on edges for graphs without parallel edges and a partial
order otherwise. It requires a vertex index map, which I think is the
best way to do this. The way to tell whether the order is total or
partial is to check the edge_parallel_category tag in graph_traits.

As for a vertex descriptor ordering, I don't know of a way to provide
this generically without (1) using a vertex index map or (2) taking
O(n) time per call to <. (1) is ridiculous since we're trying to
provide a vertex index map, and (2) is unacceptably slow. All the
vertex descriptors used by the BGL standard graph types are comparable
with < anyway, since they're either pointers or of type std::size_t,
so I don't know what else to do besides assume that if a user has a
strange vertex descriptor type, they provide their own < for the
vertex descriptor. For now, I think I'll just add a form of
make_vertex_index that takes a < functor as an argument (although,
arguably, if you can write your own < functor for vertex descriptors,
you can probably figure out internal properties.)

> 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.

I agree that the best way to provide auto-indexing is internally -
even with existing graph types, we could provide optional
auto-indexing with little space overhead. For instance, giving each
vertex an index and a timestamp with timestamp intialized to 0. The
graph keeps a global_timestamp initialized to 1 and a next_index
initialized to 0. If you ask for a vertex's index, first check if
timestamp == global_timestamp. If not, set timestamp =
global_timestamp and index = next_index, and increment next_index. If
so, return index. Whenever you remove a vertex, increment
global_timestamp and set next_index to 0. Of course, the same scheme
works for edges, too.

So, I have a few misgivings about external auto index property maps,
but I think they're easy to use, which is a start. I'll put the code
into HEAD after I've thought about this a little more.

Aaron