Package edu.uci.ics.jung.algorithms.shortestpath

Class DistanceStatistics

java.lang.Object
edu.uci.ics.jung.algorithms.shortestpath.DistanceStatistics
public class DistanceStatistics extends Object
Statistics relating to vertex-vertex distances in a graph.

Formerly known as GraphStatistics in JUNG 1.x.

Author:
Scott White, Joshua O'Madadhain

  • Constructor Summary

    Constructors
    Constructor
    Description
    DistanceStatistics()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    static <V, E> com.google.common.base.Function<V,Double>
    averageDistances(Hypergraph<V,E> g)
    For each vertex v in g, calculates the average shortest path length from v to all other vertices in g, ignoring edge weights.
    static <V, E> com.google.common.base.Function<V,Double>
    averageDistances(Hypergraph<V,E> graph, Distance<V> d)
    For each vertex v in graph, calculates the average shortest path length from v to all other vertices in graph using the metric specified by d, and returns the results in a Map from vertices to Double values.
    static <V, E> double
    diameter(Hypergraph<V,E> g)
    Returns the diameter of g, ignoring edge weights.
    static <V, E> double
    diameter(Hypergraph<V,E> g, Distance<V> d)
    Returns the diameter of g using the metric specified by d.
    static <V, E> double
    diameter(Hypergraph<V,E> g, Distance<V> d, boolean use_max)
    Returns the diameter of g using the metric specified by d.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • DistanceStatistics

      public DistanceStatistics()

  • Method Details

    • averageDistances

      public static <V, E> com.google.common.base.Function<V,Double> averageDistances(Hypergraph<V,E> graph, Distance<V> d)
      For each vertex v in graph, calculates the average shortest path length from v to all other vertices in graph using the metric specified by d, and returns the results in a Map from vertices to Double values. If there exists an ordered pair <u,v> for which d.getDistance(u,v) returns null, then the average distance value for u will be stored as Double.POSITIVE_INFINITY).

      Does not include self-distances (path lengths from v to v).

      To calculate the average distances, ignoring edge weights if any: 

       Map distances = DistanceStatistics.averageDistances(g, new UnweightedShortestPath(g));
      To calculate the average distances respecting edge weights: 
       DijkstraShortestPath dsp = new DijkstraShortestPath(g, nev);
 Map distances = DistanceStatistics.averageDistances(g, dsp);
      where nev is an instance of Transformer that is used to fetch the weight for each edge.
      Type Parameters:
      V - the vertex type
      E - the edge type
      Parameters:
      graph - the graph for which distances are to be calculated
      d - the distance metric to use for the calculation
      Returns:
      a map from each vertex to the mean distance to each other (reachable) vertex
      See Also:

    • averageDistances

      public static <V, E> com.google.common.base.Function<V,Double> averageDistances(Hypergraph<V,E> g)
      For each vertex v in g, calculates the average shortest path length from v to all other vertices in g, ignoring edge weights.
      Type Parameters:
      V - the vertex type
      E - the edge type
      Parameters:
      g - the graph for which distances are to be calculated
      Returns:
      a map from each vertex to the mean distance to each other (reachable) vertex
      See Also:

    • diameter

      public static <V, E> double diameter(Hypergraph<V,E> g, Distance<V> d, boolean use_max)
      Returns the diameter of g using the metric specified by d. The diameter is defined to be the maximum, over all pairs of vertices u,v, of the length of the shortest path from u to v. If the graph is disconnected (that is, not all pairs of vertices are reachable from one another), the value returned will depend on use_max: if use_max == true, the value returned will be the the maximum shortest path length over all pairs of connected vertices; otherwise it will be Double.POSITIVE_INFINITY.
      Type Parameters:
      V - the vertex type
      E - the edge type
      Parameters:
      g - the graph for which distances are to be calculated
      d - the distance metric to use for the calculation
      use_max - if true, return the maximum shortest path length for all graphs; otherwise, return Double.POSITIVE_INFINITY for disconnected graphs
      Returns:
      the longest distance from any vertex to any other

    • diameter

      public static <V, E> double diameter(Hypergraph<V,E> g, Distance<V> d)
      Returns the diameter of g using the metric specified by d. The diameter is defined to be the maximum, over all pairs of vertices u,v, of the length of the shortest path from u to v, or Double.POSITIVE_INFINITY if any of these distances do not exist.
      Type Parameters:
      V - the vertex type
      E - the edge type
      Parameters:
      g - the graph for which distances are to be calculated
      d - the distance metric to use for the calculation
      Returns:
      the longest distance from any vertex to any other
      See Also:

    • diameter

      public static <V, E> double diameter(Hypergraph<V,E> g)
      Returns the diameter of g, ignoring edge weights.
      Type Parameters:
      V - the vertex type
      E - the edge type
      Parameters:
      g - the graph for which distances are to be calculated
      Returns:
      the longest distance from any vertex to any other
      See Also: