Changes between Version 1 and Version 2 of soc/2007/UserFriendlyGraphs/Distance


Ignore:
Timestamp:
Jul 6, 2007, 4:30:53 PM (15 years ago)
Author:
Andrew Sutton
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • soc/2007/UserFriendlyGraphs/Distance

    v1 v2  
    99  Returns the (arithmatic) mean of shortest paths between `v` and all other vertices in `g`.
    1010
    11 `closeness`
     11`closeness(g, v, dist)`
    1212
    13 `eccentricity`
     13`eccentricity(g, v, dist)`
    1414
    1515We can also define the following graph measures:
    1616
    17 `radius`
     17`radius(g, dist)`
    1818
    19 `diameter`
     19`diameter(g, dist)`
     20
     21== Problems with Matrices ==
     22One 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`.
     23
     24The 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.
     25
     26One (easy) solution is to simply require the use of a weight map parameter.