[/
 / Copyright (c) 2007 Andrew Sutton
 /
 / Distributed under the Boost Software License, Version 1.0. (See accompanying
 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 /]

[section Eccentricity]
[template ex_eccentricity[] [link
    boost_graph.reference.algorithms.measures.eccentricity.examples.eccentricity__radius__and_diameter
    Eccentricity Example]]

[heading Overview]
The /eccentricity/ of a vertex is the maximum geodesic distance (shortest path) from
that vertex to any other vertex in the graph. Intuitively, vertices with low
eccentricity can reach all other vertices in the graph more "quickly" than vertices
with high eccentricity. Eccentricity values are used to help compute the /radius/ and
/diameter/.

Note that if vertex /u/ is disconnected from any other vertex /v/ the distance from
/u/ to /v/ is infinite. This implies the eccentricity of /v/ is infinite as well.
If any vertex in a graph has infinite eccentricity, the graph also has an infinite
diameter.

Consider the following social network represented by an undirected, unweighted
graph.

[figure
    images/reference/social_network.png
    *Figure 1.* A network of friends
]

Because the graph is small and relatively well, connected the eccentricies are
exaclty 2 or 3 for all vertices. The radius (the smaller of these numbers)
is 2, and the diameter is 3. See the [ex_eccentricity] for details on computing
eccentricity and related measures.

[section [^eccentricity()]]
    #include <boost/graph/eccentricity.hpp>

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

The `eccentricity()` function computes the eccentricty of a single vertex
given the shortest paths to every other vertex in the graph. The distance map can
be computed using a shortest paths algorithms (e.g., [dijkstra_shortest_paths] or a
[breadth_first_search]. The output of this function is returned to the caller.

[heading Parameters]
[table
    [[Type] [Parameter] [Description]]
    [
        [required, in] [`const Graph& g`]
        [
            The graph for which the eccentricity measures are being comptued.

            *Requirements:* The `Graph` type must be a model of the
            [VertexListGraph] concepts.
        ]
    ]
    [
        [required, in] [`DistanceMap dm`]
        [
            Given a vertex `v`, the `dm` parameter provides the length of the
            shortest path between a vertex `u` and `v`. The vertex `u` is the
            vertex for which the distance map was initially computed.

            *Requirements:* `DistanceMap` must be a model of [ReadablePropertyMap].
            The `key_type` of the distance map must be the same as the `vertex_descriptor`
            of the `Graph` parameter. The `value_type` is required to be a model of
            [NumericValue].
        ]
    ]
]

[heading Return Value]
The `eccentricity()` function returns the eccentricity of the vertex. If the graph
is unconnected, this returns the infinite value of the distance map's `value_type`.

[heading Complexity]
The `eccentricity()` returns in linear with respect to the number of vertices
in the graph.
[endsect]

[section [^eccentricities()]]
    #include <boost/graph/eccentricity.hpp>

    template <typename Graph, typename DistanceMatrixMap, typename EccentricityMap>
    std::pair<typename property_traits<EccentricityMap>::value_type,
              typename property_traits<EccentricityMap>::value_type>
    eccentricity(const Graph& g, DistanceMatrixMap dm, EccentricityMap em)

The `eccentricities()` function computes the eccentricity of each vertix in the graph,
given a matrix that provides the shortest paths between all pairs of vertices. This
matrix can be computed as the output of an all-pairs shortest paths algorithm (e.g., [floyd_warshall_all_pairs_shortest_paths]) or repeated application of a
[breadth_first_search] (if the graph is unweighted). Theoutput of this function is
stored in the eccentricity property map.

This function also computes the radius and diameter of the graph, returning those
values in a pair.

[heading Parameters]
[table
    [[Type] [Parameter] [Description]]
    [
        [required, in] [`const Graph& g`]
        [
            The graph for which the eccentricity measures are being comptued.

            *Requirements:* The `Graph` type must be a model of the
            [VertexListGraph] concepts.
        ]
    ]
    [
        [required, in] [`DistanceMatrixMap dm`]
        [
            Given vertices /u/ and /v/, the `dm` parameter provides the length
            of the shortest path between the two vertices. Note that the
            distance between a vertex and itself should be 0 (i.e., `dm[u][u] == 0`).

            *Requirements:* `DistanceMatrixMap` must be a model of [ReadablePropertyMap].
            The `key_type` of the distance matrixc must be the same as the `vertex_descriptor`
            of the `Graph` parameter. The `value_type` must be a [ReadWritePropertyMap]
            whose `key_type` is also the `vertex_descriptor` of the `Graph` and
            whose `value_type` is a model of [NumericValue].
        ]
    ]
    [
        [required, out] [`EccentricityMap em`]
        [
            The eccentricity map `em` stores the computed eccentricity values for
            each vertex in the graph.

            *Requirements:* The `EccentricityMap` type must model the [WritablePropertyMap]
            concept. The `key_type` of the property map must be the `vertex_descriptor`
            of the `Graph` parameter. The `value_type` must be the same type as the
            `value_type` of the `DistanceMatrixMap` parameter.
        ]
    ]
]

[heading Return]
The `eccentricities()` function returns a pair containing the radius and diameter
as the `first` and `second` elements respectively.

[heading Complexity]
The `eccentricities()` function returns in ['O(n[sup 2])] where /n/ is the number
of vertices in the graph.
[endsect]

[section [^radius()]]
    #include <boost/graph/eccentricity.hpp>

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

The `radius()` function returns the radius of the graph, which is defined as the
minimum eccentricity of any vertex in the graph. The radius is computed from the
eccentricities that have been previously computed using the [eccentricity] function.

[heading Parameters]
[table
    [[Type] [Parameter] [Description]]
    [
        [required, in] [`const Graph& g`]
        [
            The graph for which the eccentricity measures are being comptued.

            *Requirements:* The `Graph` type must be a model of the
            [VertexListGraph] concepts.
        ]
    ]
    [
        [required, out] [`EccentricityMap em`]
        [
            The eccentricity map `em` provides access to the previously computed
            eccentricities of all vertices in the graph.

            *Requirements:* The `EccentricityMap` type must model the [ReadablePropertyMap]
            concept. The `key_type` of the property map must be the `vertex_descriptor`
            of the `Graph` parameter. The `value_type` must model the [NumericValue]
            concept.
        ]
    ]
]

[heading Return Value]
The `radius()` function return the radius of the graph. The return type of
this function is the same as the `value_type` of the `EccentricityMap` parameter.

[heading Complexity]
The `radius()` function returns in linear time with respect to the number
of vertices in the graph.
[endsect]

[section [^diameter()]]
    #include <boost/graph/eccentricity.hpp>

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

The `diameter()` function returns the diameter of the graph, which is defined as the
maximum eccentricity of any vertex in the graph. The diameter is computed from the
eccentricities that have been previously computed using the [eccentricity] function.

[heading Parameters]
[table
    [[Type] [Parameter] [Description]]
    [
        [required, in] [`const Graph& g`]
        [
            The graph for which the eccentricity measures are being comptued.

            *Requirements:* The `Graph` type must be a model of the
            [VertexListGraph] concepts.
        ]
    ]
    [
        [required, out] [`EccentricityMap em`]
        [
            The eccentricity map `em` provides access to the previously computed
            eccentricities of all vertices in the graph.

            *Requirements:* The `EccentricityMap` type must model the [ReadablePropertyMap]
            concept. The `key_type` of the property map must be the `vertex_descriptor`
            of the `Graph` parameter. The `value_type` must model the [NumericValue]
            concept.
        ]
    ]
]

[heading Return Value]
The `diameter()` function return the diameter of the graph. If any vertices
are disconnected from the graph, the diameter will be infinite. The return type of
this function is the same as the `value_type` of the `EccentricityMap` parameter.

[heading Complexity]
The `diameter()` function returns in  linear time with respect to the number
of vertices in the graph.
[endsect]

[section [^radius_and_diameter()]]
    #include <boost/graph/eccentricity.hpp>

    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)

The `radius_and_diameter()` function returns both the radius and diameter of the
graph as a pair such that the `first` element of the pair is the radius and the
`second` element is the diameter. These values are  computed from the eccentricities
that have been previously computed using the [eccentricity] function.

[heading Parameters]
[table
    [[Type] [Parameter] [Description]]
    [
        [required, in] [`const Graph& g`]
        [
            The graph for which the eccentricity measures are being comptued.

            *Requirements:* The `Graph` type must be a model of the
            [VertexListGraph] concepts.
        ]
    ]
    [
        [required, out] [`EccentricityMap em`]
        [
            The eccentricity map `em` provides access to the previously computed
            eccentricities of all vertices in the graph.

            *Requirements:* The `EccentricityMap` type must model the [ReadablePropertyMap]
            concept. The `key_type` of the property map must be the `vertex_descriptor`
            of the `Graph` parameter. The `value_type` must model the [NumericValue]
            concept.
        ]
    ]
]

[heading Return Value]
The `radius_and_diameter()` funtion returns a pair containing both the radius (`first`)
and diameter (`second`) of the graph. The types of these values are the same as the
`value_type` of the `EccentricityMap`.

[heading Complexity]
The `radius_radius_diameter()` returns in linear time with respect to the number of vertices
in the graph.
[endsect]

[section Examples]
[heading Eccentricity, Radius, and Diameter]
This example computes the eccentricities for all vertices in a graph, and the radius
and diameter of the graph itself. This example includes the following files:

* [^examples/eccentricity.cpp]
* [^examples/helper.hpp]

[eccentricity_example]

Note that we can also compute the radius and diameter separatel. For exmaple:

    // Compute the radius and diameter after computing eccentricites,
    // but separately.
    int r = radius(g, em);
    int d = diameter(g, em);

    // Compute the radius and diameter after computing eccentricities,
    // but in one step.
    int r, d;
    tie(r, d) = radius_diameter(g, em);

For small graphs, choosing one method over the other makes little difference. For
large graphs, however, multiple iterations over the vertex set may result in lower
performance.

If given the `social_network.graph` file as input, the output will be:

[pre
Scott       2
Jill        3
Mary        3
Bill        3
Josh        3
Frank       2
Laurie      3
Anne        3
Howard      3
radius: 2
diamter: 3
]
[endsect]

[endsect]