Package org.graph4j.metrics

Class GraphMetrics

java.lang.Object
org.graph4j.GraphAlgorithm
org.graph4j.metrics.GraphMetrics
Direct Known Subclasses:
TreeMetrics
public class GraphMetrics extends GraphAlgorithm
Various distances related to a graph.
Author:
Cristian Frăsinaru

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected VertexSet
    center
     
    protected Double
    diameter
     
    protected double[][]
    dist
     
    protected double[]
    ecc
     
    protected Integer
    girth
     
    protected VertexSet
    periphery
     
    protected Double
    pseudoDiameter
     
    protected Double
    radius
     

    Fields inherited from class org.graph4j.GraphAlgorithm

    directed, graph

  • Constructor Summary

    Constructors
    Constructor
    Description
    GraphMetrics(Graph graph)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    averagePathLength()
    The average path length is the average distance (number of edges along the shortest path) for all possible pairs of distinct vertices.
    VertexSet
    center()
    The center of a graph is the set of vertices having eccentricities equal to the graph radius (the set of central points).
    double
    diameter()
    The diameter of a graph is the length of the "longest shortest path", that is the greatest distance between any two vertices.
    double
    distance(int v, int u)
    The distance between two vertices v and u is the number of edges on the shortest path from v to u.
    double[][]
    distances()
    Computes and stores for later retrieval all the distances between graph vertices.
    double[]
    eccentricities()
    Computes and stores for later retrieval all the eccentricities of the graph.
    double
    eccentricity(int vertex)
    Computes the eccentricity of a vertex.
    double
    eccentricity(int vertex, boolean inConnectedComponent)
    The eccentricity of a graph vertex v is the maximum graph distance between v and any other vertex of the graph.
    int
    girth()
    The girth of a graph is the length of its shortest cycle.
    VertexSet
    periphery()
    The periphery of a graph is the set of vertices having eccentricities equal to the graph diameter.
    double
    pseudoDiameter()
    Computes an approximation of the graph diameter.
    VertexSet
    pseudoPeriphery()
    A pseudo-peripheral vertex v has the property that, for any vertex u, if u is as far away from v as possible, then v is as far away from u as possible.
    double
    radius()
    The radius of a graph is the minimum eccentricity of vertices.

    Methods inherited from class org.graph4j.GraphAlgorithm

    getGraph

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • dist

      protected double[][] dist

    • ecc

      protected double[] ecc

    • girth

      protected Integer girth

    • diameter

      protected Double diameter

    • pseudoDiameter

      protected Double pseudoDiameter

    • radius

      protected Double radius

    • center

      protected VertexSet center

    • periphery

      protected VertexSet periphery

  • Constructor Details

    • GraphMetrics

      public GraphMetrics(Graph graph)
      Parameters:
      graph - the input graph.

  • Method Details

    • girth

      public int girth()
      The girth of a graph is the length of its shortest cycle. Acyclic graphs are considered to have infinite girth.
      Returns:
      the girth of the graph, or Integer.MAX_VALUE if the graph is acyclic.

    • eccentricity

      public double eccentricity(int vertex)
      Computes the eccentricity of a vertex.
      Parameters:
      vertex - a vertex number
      Returns:
      the eccentricity of the vertex

    • eccentricity

      public double eccentricity(int vertex, boolean inConnectedComponent)
      The eccentricity of a graph vertex v is the maximum graph distance between v and any other vertex of the graph. For a disconnected graph, all vertices are defined to have infinite eccentricity. The maximum eccentricity is the graph diameter. The minimum eccentricity is the graph radius. If the eccentricities are not computed or inConnectedComponent = true, it computes them, otherwise returns the already computed eccentricity.
      Parameters:
      vertex - a vertex number
      inConnectedComponent - specifies to compute the eccentricity in the connected component of the vertex
      Returns:
      the eccentricity of the vertex.

    • distance

      public double distance(int v, int u)
      The distance between two vertices v and u is the number of edges on the shortest path from v to u. If there is no path that connects v and u, the distance is infinite.
      Parameters:
      v - a vertex number
      u - a vertex number
      Returns:
      the distance between v and u, or Double.POSITIVE_INFINITY if there is no path from v to u.

    • eccentricities

      public double[] eccentricities()
      Computes and stores for later retrieval all the eccentricities of the graph. If the eccentricities are already computed, it simply returns them. Note that some methods of this class might trigger this computation, in order to create their response.
      Returns:
      the eccentricities of the graph vertices.

    • distances

      public double[][] distances()
      Computes and stores for later retrieval all the distances between graph vertices. If the distances are already computed, it simply returns them. Note that some methods of this class might trigger this computation, in order to create their response.
      Returns:
      the distances matrix

    • diameter

      public double diameter()
      The diameter of a graph is the length of the "longest shortest path", that is the greatest distance between any two vertices. A disconnected graph has infinite diameter. If the graph is weighted, the algorithm will take into consideration the weight of the edges, in order to compute the diameter.
      Returns:
      the diameter of the graph

    • pseudoDiameter

      public double pseudoDiameter()
      Computes an approximation of the graph diameter. It works by starting from a vertex u, and finds a vertex v that is farthest away from u. This process is repeated by treating v as the new starting vertex, and ends when the graph distance no longer increases. If either the diameter or eccentricities have been computetd, it returns the diameter of the graph.
      Returns:
      the psueudo-diameter of a graph.

    • radius

      public double radius()
      The radius of a graph is the minimum eccentricity of vertices. A disconnected graph has infinite radius. If the graph is weighted, the algorithm will take into consideration the weight of the edges, in order to compute the radius.
      Returns:
      the radius of the graph, or Double.POSITIVE_INFINITY if the graph is disconnected.

    • center

      public VertexSet center()
      The center of a graph is the set of vertices having eccentricities equal to the graph radius (the set of central points). If the graph is weighted, the algorithm will take into consideration the weight of the edges, in order to compute the center.
      Returns:
      the graph center.

    • periphery

      public VertexSet periphery()
      The periphery of a graph is the set of vertices having eccentricities equal to the graph diameter. If the graph is weighted, the algorithm will take into consideration the weight of the edges, in order to compute the periphery.
      Returns:
      the graph periphery.

    • pseudoPeriphery

      public VertexSet pseudoPeriphery()
      A pseudo-peripheral vertex v has the property that, for any vertex u, if u is as far away from v as possible, then v is as far away from u as possible. Computes the distances and the eccentricities.
      Returns:
      the graph pseudo periphery.

    • averagePathLength

      public double averagePathLength()
      The average path length is the average distance (number of edges along the shortest path) for all possible pairs of distinct vertices. It is computed as the sum of distances d(v,u) between all pairs of distinct vertices (assuming d(v,u) = 0 if v and u are not connected) normalized by the total number of paths n*(n-1), where n is the number of vertices in G.
      Returns:
      the average path length.