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:

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:

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.

Problems

Despite the improved readability of this approach, there is one drawback. It is possible to pass a vertex as the target that is not the vertex that the property is computed for. It may be possible to generalize and state that dist[v] == 0 where v is the vertex for which the distance map was computed, but this doesn't hold for all graphs (e.g., probabalistic state transitions).

My suggestion would be to simple excercise care when passing vertices to such computations, making sure that they actually refer to the vertex for which the distance maps are computed.