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

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-12-12 10:55:05

On Dec 1, 2005, at 7:12 AM, Aaron Windsor wrote:

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

Yep. For all of the edge descriptor types in the BGL that can have a  
<, we should provide it just for convenience. It still won't be a  
requirement on edge descriptors, but it's a good convenience.

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

Yep, that seems reasonable.

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

Yep, that would work perfectly well. At one point I was imagining  
magic "vertex_autoindex_t" and "edge_autoindex_t" properties that one  
could put into the list of properties, e.g.,

typedef	adjacency_list<listS, listS, directedS,
                                property<vertex_autoindex_t, std::size_t>,
                                property<edge_autoindex_t, std::size_t> > Graph;

Your suggestion would be a very reasonable implementation of that.  
We'd need to make it so that property_map<Graph, vertex_index_t> and  
get(vertex_index, g) did the right thing by grabbing the auto-index  
property map.

Granted, I don't want to make the user do anything with property<...>  
ever again. We'd be better off with a schedule based on bundled  
properties, either by providing an "auto_indexed" base class for  
bundled properties or a wrapper. *Sigh*; so many tricky interface  
decisions.

        Doug