Changes between Version 2 and Version 3 of soc/2007/UserFriendlyGraphs/PropertyMaps

Timestamp:

Jul 6, 2007, 3:36:33 PM (15 years ago)

Author:

Andrew Sutton

Comment:

--

soc/2007/UserFriendlyGraphs/PropertyMaps

@@ -55 +55 @@
 Or something like that... At least its a little more explicit. Also, it's kind of hard to see what type these maps are - which is why they're almost always passed as functions and typedef'd.
 
+The "most" precise way to actually implement these is as follows. First, we need a type that actually performs the mapping - more or less. Essentially, this is a container that overloads the `operator[]` operator and the index is either an edge or vertex descriptor and the value is... well, dependant upon the mapping. This is the primary mapping object for the vertex/edge-to-value object. The important thing about this type is that it can add overhead to algorithms if the mapping is poorly chosen. For example, `std::map` is probably a poor choice because its lookup (mapping) is logarithmic (not constant).
+
+If we're talking about the typical vector-based vertex storage, then this is what we might do (for a distance map, per-se).
+
+{{{
+#!cpp
+typedef std::vector<int> DistanceMapping;
+}}}
+
+Here, the `int` refers to the distance type and not the key type (descriptor). Because it's a vector, the key type has to be an integer type (probably unsigned). This works out great for vector-based vertex storage since descriptors magically happen to be unsigned integers. Its even better since the value of those descriptors magically align to the range [0, `num_vertices(g)`) so the mapping is trivial, and very, very fast (probably the fastest you can get).
+
+The second thing we ''really'' need is an adaptor between the mapping type and the Boost.PropertyMap library. Fortunately, there are already a bunch of these - for this application, we're looking at an `iterator_property_map`. This is an iterator property map because the indices of vector can also act as iterators to the container (as pinters). The only thing we have to do is define the types responsible for the actual mapping and adapt that to the library. This is done with:
+
+{{{
+#!cpp
+typedef iterator_property_map<DistanceMapping::iterator,
+                              property_map<Graph, vertex_index_t>::type> DistanceMap;
+}}}
+
+That's plenty ugly, but it's actually correct. The first parameter says that the adapted property map uses the mapping objects iterator type for indexing values. Remember that this iterator type is just an unsigned integer - the same as the vertex_descriptor type. The second parameter actually tells the adapter how to translate from a `vertex_descriptor` type to a the distance iterator. This parameter is actually defined in terms of the graph for which the map is being defined. Although we don't really see it here, this entire declaration is basically defining a set of functions that does this:
+
+{{{
+#!cpp
+int                            // the distance type (value)
+get(const DistanceMaping& map, // the underlying mapping object (the vector)
+    unsigned v)                // the vertex descriptor of vector-based vertex storage
+{
+   return map[v];
+}
+}}}
+
+This is fundamentally what happens. The actual series of type transformations and function instantiation is a lot more complicated, but at the heart of the operation is a constant-time vector access. Unfortunately, if your descriptor isn't an unsigned integer in the range [0, num_vertices(g)), you'll have to read the next section.
+
+It might also be worth pointing out that when you see code that looks like this:
+
+{{{
+#!cpp
+dijkstra_shortest_paths(g, v, distance_map(&dist[0]));
+}}} 
+
+that `distance_map(&dists[0])` is actually building an `iterator_property_map` just like before. It just so happens that `&dists[0]` is a valid iterator type for a vector so the construction of the property map is completely hidden.
+
 == Truly Associative Property Maps ==
 Generally speaking property maps require vertex and edge descriptors as keys for lookup. In order to get past some of these problems, we just need to figure out how to abstract the lookup of values based on edge and vertex descriptors. In short, we need to have our property maps act as associative maps. We could probably use a standard map, but unfortunately, that has log-time lookup, which while good, is too slow for algorithms that require accesses to lots of different properties. Non-constant property access is not a ''Good Thing''. An alternative is to use the `unordered_map` from the TR1 spec - which unfortunately, Boost doesn't currently implement.
@@ -110 +152 @@
 
 Obviously, there would need to be some adjustments since we can build the hash for either a native tr1 implementation or for Boost.Hash. Also, we might need to duplicate this code to handle non-list-based vector storage. I think this just means changing the `void*` to `unsigned` or `int` for vectors. The hash function works by returning the hash value of the property pointer on the edge. This is actually typedef'd to be `void*` so this should work fine. Note that we can't build the hash value from the source and target vertices of the edge because there can be multiple edges for those vertices.
+
+== Helper Functions ==
+It would be nice if there were a suite of functions and types that would help programmers declare exterior property maps. I think that these would essentially default to either vectors or unordered maps depending on how the graph is defined. It might be helpful to have something like:
+
+{{{
+#!cpp
+typedef exterior_vertex_property<Graph, float>::property_type DistanceValues;
+typedef exterior_vertrex_property<Graph, float>::mapping_type DistanceMap;
+
+DistanceValues dists(num_vertices(g));
+DistanceMap dist_map(dists);
+}}}
+
+Essentially this template is specialized for vector- and non-vector-based storage such that the proeprty type is vectors for vector-based and unordered_maps for non-vector based. The mapping type is either an associative property map or an iterator property map.
+
+An alternative approach migth be to build a single type that exposes references to the values and the mapping as inline functions:
+
+{{{
+#!cpp
+typedef exterior_vertex_property<Graph, float> DistanceProperty;
+
+DistanceProperty dists(num_vertices(g));
+dijkstra_shortest_paths(g, v, distance_map(dists.map()));
+}}}
+
+Again... maybe.