Distance Measures

Distance Measures are all turning out to be kind of interesting - mainly because they're all secondary measures of the distance_map parameter for shortest_paths algorithms. So far, I'm providing the following vertex measures:

geodesic_distance(g, u, v, dist)

This returns the distance of the shortest path between the vertices u and v.

mean_geodesic_distance(g, v, dist)

Returns the (arithmatic) mean of shortest paths between v and all other vertices in g.

closeness(g, v, dist)

eccentricity(g, v, dist)

We can also define the following graph measures:

radius(g, dist)

diameter(g, dist)

Problems with Matrices

One of the problems with inclusive graph measure computations is that they usually need a matrix of all pairs of shortest paths. The output matrix of this type for the all-pairs functions is described as a DistanceMatrix. This varies considerably from property maps since we're essentially talking about a 2D version of it. In fact, the documentation doesn't even mention property maps here - just that the type has to satisfy the expression D[u][v] where u and v are vertices and the result of the expression is the value type of weight_map.

The problem comes from satisfying the return type in a generic function. If the matrix is given as vector<vector<X>>, then the return type is vector<vector<>::value_type>::value_type. Unfortunately, if its a unordered_map<Vertex, unordered_map<Vertex, X>>, then the return type is even more complicated.

One (easy) solution is to simply require the use of a weight map parameter.