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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2005-11-22 07:23:33

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?

> 2) For the auto_index_property_map that allows duplicate keys, was
> there any particular reason to use a map of vectors instead of a
> multimap?

No, you're right - multimap is better here. I'll change this and put a
new version
in the vault.

> I also have some higher-level, non-code comments. The primary concern I
> have is that we're adding more functionality to the BGL to make it
> easier. It's the same thing we did with bundled properties: add a new,
> easier-to-use mechanism on top of what we already have. Unfortunately,
> features interact and I'm not entirely sure that we've managed to make
> life easier overall.
>
> Auto-indexing maps are a great feature, but overall will they make it
> easier to learn and use the BGL? They will make some things easier:
> when users ask "why can't I call this algorithm with my
> adjacency_list?" we'll have the simple answer of "add
> edge_index(auto_edge_index_map(g))", followed by the obligatory "if you
> find that it's too slow, do this other thing" comment.
>
> It seems that the way to make the BGL easier to use would be to make
> auto-indexing property maps automatic. When a BGL algorithm tries to
> pull out a vertex_index map, it checks the parameter list, then the
> graph itself, then falls back to generating an auto-indexing map. This
> would be convenient, but it also means that there are hidden
> performance penalties, which we've tried to avoid in the BGL.
>
> What to do?

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.

>
> It's becoming more and more important to make the BGL easier to use
> out-of-the-box. I even think that most users will understand if at a
> later point in time they need to do a little work to get their code to
> give maximum performance, but we need to give them the tools to do so.
> For instance, I can imagine a macro BOOST_GRAPH_PERFORMANCE_WARNINGS
> that produces run-time warnings when the library is secretly building
> an auto-indexing map behind-the-scenes and a macro
> BOOST_GRAPH_PERFORMANCE_WARNINGS_ARE_ERRORS that causes compile-time
> errors instead.

Interesting. I'll think some more about this...

> But for now, I think once I understand (1) and (2), the auto-indexing
> property maps should go into CVS HEAD and we can discuss just how
> automatic we want to make them.

Thanks for taking the time to look at this and give some feedback, Doug. I'll
update with the multimap fix, probably after the holidays.

Aaron