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 and Description
DistanceStatistics()

Method Summary

Modifier and Type	Method and 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 Detail

DistanceStatistics

public DistanceStatistics()

Method Detail

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:

UnweightedShortestPath, DijkstraDistance

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(Hypergraph), ClosenessCentrality

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(Hypergraph, Distance, boolean)

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:

diameter(Hypergraph, Distance, boolean)