On Dec 1, 2005, at 7:12 AM, Aaron Windsor wrote:
On 11/29/05, Douglas Gregor <doug.gregor@gmail.com> 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