On 9/15/05, Jeremy Siek <jeremy.siek@gmail.com> wrote:
Hi Doug,
On Sep 14, 2005, at 9:01 PM, Douglas Gregor wrote:
<snip>
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.
All of Doug's options sound good to me, too, and I'd like to add one more idea. Most of the BGL algorithms operate on the assumption that if you don't pass in a vertex or edge index map explicitly, that index map should be accessible as an internal property, for instance, something like: template<typename Graph, typename VertexIndexMap> void foo(const Graph& g, VertexIndexMap vim = get(vertex_index,g)); In the above code, if g doesn't have a vertex_index property, no_property is returned from the get. What I'm thinking about is returning something other than no_property: consider another type of property map, which I'll call auto_index_property_map. It's got two data members: a shared_ptr to an associative container and an integer index called next_available_index. Its default constructor creates a new associative container, while the copy constructor and assignment operator just copy over the shared_ptr. When you call "get" on an auto_index_property_map for an element x, it checks to see if x is a key in the associative container. If it is, return the index x is associated with. If not, put the pair (x,next_available_index) in the container and return next_available_index and post-increment it. The main problem I can see with this solution is that if you call get(vertex_index,g) twice you get distinct instances of an auto_index_property_map, containing different associative containers. This could cause some pretty spectacular failures and might be a tough bug to catch within an algorithm. But from what I've seen, getting the vertex_index or edge_index property is usually done once by the algorithm, as in foo's signature above, so that all we would need to do is change the behavior of get(vertex_index,g) and get(edge_index,g) to return an auto_index_property_map. I'd be willing to code up an auto_index_property_map if anyone likes this idea, otherwise I vote for Doug's #4 above. Aaron