Geodesic Distance

Computes the mean shortest-path distance from a vertex to all other vertices. A low mean geodesic indicates a centrally located vertex.

Defined in: <boost/graph/geodesic_distance.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/exterior_property.hpp>
#include <boost/graph/floyd_warshall_shortest.hpp>
#include <boost/graph/geodesic_distance.hpp>
#include <iostream>

struct EdgeProps { int weight; };

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
    boost::no_property, EdgeProps>;
using DistProp = boost::exterior_vertex_property<Graph, int>;
using DistMatrix = DistProp::matrix_type;
using DistMatrixMap = DistProp::matrix_map_type;
using GeoProp = boost::exterior_vertex_property<Graph, double>;

int main() {
    Graph g{4};
    boost::add_edge(0, 1, EdgeProps{1}, g);
    boost::add_edge(1, 2, EdgeProps{2}, g);
    boost::add_edge(2, 3, EdgeProps{1}, g);
    boost::add_edge(0, 3, EdgeProps{5}, g);

    DistMatrix dist(num_vertices(g));
    DistMatrixMap dm(dist, g);
    boost::floyd_warshall_all_pairs_shortest_paths(g, dm,
        boost::weight_map(get(&EdgeProps::weight, g)));

    GeoProp::container_type geo_vec(num_vertices(g));
    GeoProp::map_type geo(geo_vec, g);
    double graph_mean = boost::all_mean_geodesics(g, dm, geo,
        boost::measure_mean_geodesic(g, GeoProp::map_type(geo_vec, g)));

    for (auto v : boost::make_iterator_range(vertices(g)))
        std::cout << "mean geodesic[" << v << "] = " << geo_vec[v] << "\n";
    std::cout << "Graph mean geodesic: " << graph_mean << "\n";
}

mean geodesic[0] = 2.66667
mean geodesic[1] = 2
mean geodesic[2] = 2
mean geodesic[3] = 2.66667
Graph mean geodesic: 2.33333

(1) mean_geodesic with explicit measure and combinator

template <typename Graph, typename DistanceMap,
          typename Measure, typename Combinator>
typename Measure::result_type
mean_geodesic(const Graph& g, DistanceMap dist,
              Measure measure, Combinator combine);

Reduces dist via combine (default behavior in (2) uses std::plus) and applies measure.

(2) mean_geodesic with measure

template <typename Graph, typename DistanceMap, typename Measure>
typename Measure::result_type
mean_geodesic(const Graph& g, DistanceMap dist, Measure measure);

Equivalent to (1) with combine = std::plus<distance_type>().

(3) mean_geodesic (default double result)

template <typename Graph, typename DistanceMap>
double mean_geodesic(const Graph& g, DistanceMap dist);

Uses measure_mean_geodesic(g, dist) as the measure — (sum of distances) / (num_vertices(g) - 1).

(4) mean_geodesic with explicit result type

template <typename T, typename Graph, typename DistanceMap>
T mean_geodesic(const Graph& g, DistanceMap dist);

Same as (3) but the result type is parametrized as T.

(5) all_mean_geodesics with measure

template <typename Graph, typename DistanceMatrixMap,
          typename GeodesicMap, typename Measure>
typename property_traits<GeodesicMap>::value_type
all_mean_geodesics(const Graph& g, DistanceMatrixMap dist,
                   GeodesicMap geo, Measure measure);

Writes the mean geodesic for every vertex into geo and returns the average of those values (the graph’s mean geodesic).

(6) all_mean_geodesics (default measure)

template <typename Graph, typename DistanceMatrixMap,
          typename GeodesicMap>
typename property_traits<GeodesicMap>::value_type
all_mean_geodesics(const Graph& g, DistanceMatrixMap dist,
                   GeodesicMap geo);

Equivalent to (5) with measure_mean_geodesic<Result>(g, DistanceMap()) where Result is the value type of GeodesicMap.

(7) small_world_distance with measure

template <typename Graph, typename GeodesicMap, typename Measure>
typename Measure::result_type
small_world_distance(const Graph& g, GeodesicMap geo, Measure measure);

(8) small_world_distance (default measure)

template <typename Graph, typename GeodesicMap>
typename property_traits<GeodesicMap>::value_type
small_world_distance(const Graph& g, GeodesicMap geo);

Sums the per-vertex mean geodesics in geo and applies measure_graph_mean_geodesic(g, geo) (sum divided by num_vertices(g)).

(9) Measure helpers and structs

template <typename Graph, typename DistanceType, typename ResultType,
          typename Divides = std::divides<ResultType>>
struct mean_geodesic_measure
    : public geodesic_measure<Graph, DistanceType, ResultType>;

template <typename Graph, typename DistanceType>
struct mean_graph_distance_measure
    : public geodesic_measure<Graph, DistanceType, DistanceType>;

template <typename Graph, typename DistanceMap>
mean_geodesic_measure</*...*/, double> measure_mean_geodesic(const Graph&, DistanceMap);

template <typename T, typename Graph, typename DistanceMap>
mean_geodesic_measure</*...*/, T>      measure_mean_geodesic(const Graph&, DistanceMap);

template <typename Graph, typename DistanceMap>
mean_graph_distance_measure</*...*/>   measure_graph_mean_geodesic(const Graph&, DistanceMap);

Functors and factory helpers. mean_geodesic_measure returns d / (num_vertices(g) - 1); mean_graph_distance_measure returns d / num_vertices(g). Both map the infinite-distance marker to an infinite result.

Parameters

Direction Parameter Description

Direction	Parameter	Description
IN	`const Graph& g`	Must model Vertex List Graph for overloads iterating vertices; the 2/3/4-arg `mean_geodesic` overloads only require Graph.
IN	`DistanceMap dist`	ReadablePropertyMap from vertex to distance. Populate via a shortest-paths algorithm before calling.
IN	`DistanceMatrixMap dist` (all_*)	ReadablePropertyMap from vertex to its distance map row.
IN	`Measure measure`	Model of `DistanceMeasureConcept` (see overload (9) for the built-in choices).
IN	`Combinator combine`	Binary reduction over distances. Default: `std::plus<distance_type>`.
OUT / IN	`GeodesicMap geo`	WritablePropertyMap for overload (5)/(6); ReadablePropertyMap for overload (7)/(8).

const Graph& g

Must model Vertex List Graph for overloads iterating vertices; the 2/3/4-arg mean_geodesic overloads only require Graph.

DistanceMap dist

ReadablePropertyMap from vertex to distance. Populate via a shortest-paths algorithm before calling.

DistanceMatrixMap dist (all_*)

ReadablePropertyMap from vertex to its distance map row.

Measure measure

Model of DistanceMeasureConcept (see overload (9) for the built-in choices).

Combinator combine

Binary reduction over distances. Default: std::plus<distance_type>.

OUT / IN

GeodesicMap geo

WritablePropertyMap for overload (5)/(6); ReadablePropertyMap for overload (7)/(8).

Requires pre-computed distance maps from an all-pairs shortest paths algorithm.

Edit this Page