edu.uci.ics.jung.algorithms.shortestpath

Class DistanceStatistics

java.lang.Object

edu.uci.ics.jung.algorithms.shortestpath.DistanceStatistics

public class DistanceStatistics
extends java.lang.Object

Statistics relating to vertex-vertex distances in a graph.

Formerly known as GraphStatistics in JUNG 1.x.

Constructor Summary

Constructors

Constructor and Description
DistanceStatistics()

Method Summary

Modifier and Type	Method and Description
static <V,E> com.google.common.base.Function<V,java.lang.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,java.lang.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

equals, 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,java.lang.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,java.lang.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)