Changes between Initial Version and Version 1 of soc/2007/UserFriendlyGraphs/Measures

Timestamp:

Jul 6, 2007, 1:28:02 PM (15 years ago)

Author:

Andrew Sutton

Comment:

--

soc/2007/UserFriendlyGraphs/Measures

@@ +1 @@
+= Secondary Measures =
+
+One of the interesting aspects of implementing some of these measures is that they can often be derived directly from the output (usually optional) of existing graph algorithms. This has both good and bad aspects to it. The good is that I don't really need to do alot of algorithmic work to implement many of these measures since I can simply take a property map and compute max's, min's or means without much effort at all. The bad is that the algorithms don't really fit into the algorithm set since they aren't really operating directly on graphs. This is why I'm calling them ''secondary'' measures - they're computed on the outputs of graph algorithms.
+
+Take the `geodesic_distance()` measure. This tells me the shortest distance between two vertices. The easiest (really trivial) way to compute this is to run a shortest paths algorithm and simply return the distance recorded into the output distance map. Note that this can also be done with a BFS for undirected graphs with unweighted or unilaterally equal edge weights via the distance recorder. Ideally, a call to `geodesic_distance()` should look like this:
+
+{{{
+#!cpp
+size_t d = geodesic_distance(g, u, v);
+}}}
+
+This would have to compute the distance map for `u` and return `dist[v]`. But what algorithm to use... Personally, I think that should be left to the programmer to decide - there are two many (three?) options and they can't all be statically decided at compile time. My approach is to simply require a valid distance map to be provided for the computation. Like so:
+
+{{{
+#!cpp
+xxx_shortest_paths(g, v, distance_map(dist)); // compute distances first
+size_t d = geodesic_distance(g, u, v, dist);
+}}}
+
+This implementation simply has to return `dist[v]`, which means that `v` is a dummy parameter. I think this is perfectly acceptable. Despite the fact that the target vertex of the computation plays no part in the computation, it provides a nice point of reference from the readability standpoint. I can immediately see that the user is computing the geodesic distance between vertices u and v.