Eccentricity

The eccentricity of a vertex is the maximum distance from it to any other vertex. From eccentricity values you can derive the graph’s radius (minimum eccentricity) and diameter (maximum eccentricity).

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

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/exterior_property.hpp>
#include <boost/graph/floyd_warshall_shortest.hpp>
#include <boost/graph/eccentricity.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 EccMap = boost::exterior_vertex_property<Graph, int>;

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)));

    EccMap::container_type ecc_vec(num_vertices(g));
    EccMap::map_type ecc(ecc_vec, g);
    auto rd = boost::all_eccentricities(g, dm, ecc);

    std::cout << "Radius: " << rd.first << ", Diameter: " << rd.second << "\n";
    for (auto v : boost::make_iterator_range(vertices(g)))
        std::cout << "eccentricity[" << v << "] = " << ecc_vec[v] << "\n";
}
Radius: 3, Diameter: 4
eccentricity[0] = 4
eccentricity[1] = 3
eccentricity[2] = 3
eccentricity[3] = 4

(1) eccentricity with explicit combinator

template <typename Graph, typename DistanceMap, typename Combinator>
typename property_traits<DistanceMap>::value_type
eccentricity(const Graph& g, DistanceMap dist, Combinator combine);

The combinator reduces the distances into a single value (by default max).

(2) eccentricity

template <typename Graph, typename DistanceMap>
typename property_traits<DistanceMap>::value_type
eccentricity(const Graph& g, DistanceMap dist);

Equivalent to (1) with a default combinator that returns the maximum finite distance.

(3) all_eccentricities

template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
std::pair<
    typename property_traits<EccentricityMap>::value_type,
    typename property_traits<EccentricityMap>::value_type>
all_eccentricities(const Graph& g, const DistanceMatrix& dist,
                   EccentricityMap ecc);

Writes the eccentricity of every vertex into ecc. Returns the pair (radius, diameter) (the minimum and maximum eccentricities) computed along the way.

(4) radius_and_diameter

template <typename Graph, typename EccentricityMap>
std::pair<
    typename property_traits<EccentricityMap>::value_type,
    typename property_traits<EccentricityMap>::value_type>
radius_and_diameter(const Graph& g, EccentricityMap ecc);

Given an already-populated ecc, returns (radius, diameter) without recomputing the eccentricities. EccentricityMap is ReadablePropertyMap in this overload.

(5) radius

template <typename Graph, typename EccentricityMap>
typename property_traits<EccentricityMap>::value_type
radius(const Graph& g, EccentricityMap ecc);

Returns only the radius (.first of radius_and_diameter).

(6) diameter

template <typename Graph, typename EccentricityMap>
typename property_traits<EccentricityMap>::value_type
diameter(const Graph& g, EccentricityMap ecc);

Returns only the diameter (.second of radius_and_diameter).

Parameters

Direction Parameter Description

IN

const Graph& g

Must model Vertex List Graph.

IN

DistanceMap dist

(single-vertex) ReadablePropertyMap from vertex to distance, pre-populated by a shortest-paths run.

IN

DistanceMatrix dist

(all_eccentricities) ReadablePropertyMap from vertex to another property map (that vertex’s row of the distance matrix).

IN

Combinator combine

Binary functor reducing distances to a scalar (default: max).

OUT / IN

EccentricityMap ecc

WritablePropertyMap for overload (3); ReadablePropertyMap for overloads (4)/(5)/(6). Vertex-to-eccentricity mapping.
These functions require pre-computed distance maps. Run an all-pairs shortest paths algorithm first (Johnson or Floyd-Warshall).
Edit this Page