On 11/29/05, Douglas Gregor <doug.gregor@gmail.com> wrote:
On Nov 22, 2005, at 7:23 AM, Aaron Windsor wrote:
On 11/21/05, Doug Gregor <dgregor@cs.indiana.edu> 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