Package com.jgalgo.alg.distancemeasures

Interface DistanceMeasures<V,E>

Type Parameters:
V - the vertices type
E - the edges type
All Known Subinterfaces:
IDistanceMeasures
public interface DistanceMeasures<V,E>
A set of graph distance measures.

Given a graph \(G=(V,E)\), and an edge weight function \(w:E \rightarrow \mathbb{R}\), the eccentricity of a vertex \(v \in V\) is the maximum distance from \(v\) to any other vertex in the graph. Multiple measures can be derived from the eccentricity of the vertices, such as radius, diameter, center, and periphery. A DistanceMeasures object can be created for a graph using of(Graph, WeightFunction), and all these measures will be computed (possible lazily).

Author:
Barak Ugav

  • Method Summary

    Modifier and Type
    Method
    Description
    Set<V>
    center()
    Get the center of the graph.
    double
    diameter()
    Get the diameter of the graph.
    double
    eccentricity(V v)
    Get the eccentricity of a vertex.
    static <V, E> DistanceMeasures<V,E>
    of(Graph<V,E> g, WeightFunction<E> w)
    Get a distance measures object of a graph.
    Set<V>
    periphery()
    Get the periphery of the graph.
    double
    radius()
    Get the radius of the graph.

  • Method Details

    • radius

      double radius()
      Get the radius of the graph.

      Given a graph \(G=(V,E)\), and an edge weight function \(w:E \rightarrow \mathbb{R}\), the eccentricity of a vertex \(v \in V\) is the maximum distance from \(v\) to any other vertex in the graph. The raidus of the graph is the minimum eccentricity of all vertices in the graph. If the graph is directed, the eccentricity of a vertex \(v \in V\) is the maximum directed distance from \(v\) to any other vertex in the graph.

      If the graph is not (strongly) connected, the radius is Double.POSITIVE_INFINITY.

      Returns:
      the radius of the graph

    • diameter

      double diameter()
      Get the diameter of the graph.

      Given a graph \(G=(V,E)\), and an edge weight function \(w:E \rightarrow \mathbb{R}\), the eccentricity of a vertex \(v \in V\) is the maximum distance from \(v\) to any other vertex in the graph. The diameter of the graph is the maximum eccentricity of all vertices in the graph. In other words, it is the maximum distance between two vertices. If the graph is directed, the eccentricity of a vertex \(v \in V\) is the maximum directed distance from \(v\) to any other vertex in the graph.

      If the graph is not (strongly) connected, the diameter is Double.POSITIVE_INFINITY.

      Returns:
      the diameter of the graph

    • eccentricity

      double eccentricity(V v)
      Get the eccentricity of a vertex.

      Given a graph \(G=(V,E)\), and an edge weight function \(w:E \rightarrow \mathbb{R}\), the eccentricity of a vertex \(v \in V\) is the maximum distance from \(v\) to any other vertex in the graph. If the graph is directed, the eccentricity of a vertex \(v \in V\) is the maximum directed distance from \(v\) to any other vertex in the graph.

      If there is a vertex \(u \in V\) that is not reachable from \(v\), the eccentricity of \(v\) is Double.POSITIVE_INFINITY.

      Parameters:
      v - a vertex
      Returns:
      the eccentricity of the vertex
      Throws:
      NoSuchVertexException - if v is not a valid vertex identifier in the graph

    • center

      Set<V> center()
      Get the center of the graph.

      Given a graph \(G=(V,E)\), and an edge weight function \(w:E \rightarrow \mathbb{R}\), the eccentricity of a vertex \(v \in V\) is the maximum distance from \(v\) to any other vertex in the graph. The raidus of the graph is the minimum eccentricity of all vertices in the graph. The center of the graph is the set of vertices with eccentricity equal to the radius.

      Returns:
      the set of vertices forming the center of the graph

    • periphery

      Set<V> periphery()
      Get the periphery of the graph.

      Given a graph \(G=(V,E)\), and an edge weight function \(w:E \rightarrow \mathbb{R}\), the eccentricity of a vertex \(v \in V\) is the maximum distance from \(v\) to any other vertex in the graph. The diameter of the graph is the maximum eccentricity of all vertices in the graph. The periphery of the graph is the set of vertices with eccentricity equal to the diameter.

      If the graph is not (strongly) connected, the periphery is the set of all the vertices as all the vertices eccentricity and the diameter are Double.POSITIVE_INFINITY.

      Returns:
      the set of vertices forming the periphery of the graph

    • of

      static <V, E> DistanceMeasures<V,E> of(Graph<V,E> g, WeightFunction<E> w)
      Get a distance measures object of a graph.

      If g is and IntGraph, the return object is of type IDistanceMeasures.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph
      w - the edge weight function
      Returns:
      a distance measures object of the graph