Re: [Boost-users] Could the BGL graph algorithms be improved to automatically work with VertexList = listS graphs?

From: Jeremy Siek (jeremy.siek_at_[hidden])
Date: 2005-09-15 08:35:37

Hi Doug,

On Sep 14, 2005, at 9:01 PM, Douglas Gregor wrote:
> It's definitely slower, but I think we need to give the usability
> issue more weight. I only recall ever having seen two cases where
> someone complained about the BGL being to slow: one was with
> betweenness_centrality, until we learned that the person had compiled
> without any optimizations; the other was with bundled properties
> slowing things down (due to the extra level of dispatch).  On the

And is the reason they don't complain because they don't care
about speed, or because the BGL is fast? :)

Don't get me wrong, I care about usability and I think something
should be done about this.

> other hand, we get questions every week about how to create property
> maps, especially edge property maps (because there's no way to avoid
> managing your own edge_index_t). We should get users hooked on the
> BGL first, then we can worry about getting maximal performance for
> them later.
>
> I've been thinking of a few ways to try to help users with creating
> and using property maps. It's possible that "all of them" is the
> right answer:
>
>      1) Make edge descriptors ordered (via <), so that users can make
> associative property maps more easily
>      2) Create templates vertex_property_map<T, Graph> and
> edge_property_map<T, Graph> that create external property maps
> without much effort from the user; in particular, that'll use an
> associative property map or an iterator property map depending on
> whether a vertex_index property is available.
>
>      3) As Tony mentions, make the algorithms a bit more lenient
> about the input graphs. They could use something like the class
> templates in #2, so long as we can still get maximal efficiency out
> of them when index maps are available.
>
>      4) Create new graph types (say, directed_graph<Vertex, Edge> and
> undirected_graph<Vertex, Edge>) that maintain vertex and edge index
> maps internally (as does the Python graph type).

All of those options sound reasonable.

Cheers,
Jeremy