2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
10 package edu.uci.ics.jung.algorithms.shortestpath;
11 import java.util.Collection;
13 import org.apache.commons.collections15.Transformer;
15 import edu.uci.ics.jung.algorithms.scoring.ClosenessCentrality;
16 import edu.uci.ics.jung.algorithms.scoring.util.VertexScoreTransformer;
17 import edu.uci.ics.jung.graph.Hypergraph;
20 * Statistics relating to vertex-vertex distances in a graph.
22 * <p>Formerly known as <code>GraphStatistics</code> in JUNG 1.x.</p>
25 * @author Joshua O'Madadhain
27 public class DistanceStatistics
30 * For each vertex <code>v</code> in <code>graph</code>,
31 * calculates the average shortest path length from <code>v</code>
32 * to all other vertices in <code>graph</code> using the metric
33 * specified by <code>d</code>, and returns the results in a
34 * <code>Map</code> from vertices to <code>Double</code> values.
35 * If there exists an ordered pair <code><u,v></code>
36 * for which <code>d.getDistance(u,v)</code> returns <code>null</code>,
37 * then the average distance value for <code>u</code> will be stored
38 * as <code>Double.POSITIVE_INFINITY</code>).
40 * <p>Does not include self-distances (path lengths from <code>v</code>
43 * <p>To calculate the average distances, ignoring edge weights if any:
45 * Map distances = DistanceStatistics.averageDistances(g, new UnweightedShortestPath(g));
47 * To calculate the average distances respecting edge weights:
49 * DijkstraShortestPath dsp = new DijkstraShortestPath(g, nev);
50 * Map distances = DistanceStatistics.averageDistances(g, dsp);
52 * where <code>nev</code> is an instance of <code>Transformer</code> that
53 * is used to fetch the weight for each edge.
55 * @see edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath
56 * @see edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
58 public static <V,E> Transformer<V,Double> averageDistances(Hypergraph<V,E> graph, Distance<V> d)
60 final ClosenessCentrality<V,E> cc = new ClosenessCentrality<V,E>(graph, d);
61 return new VertexScoreTransformer<V, Double>(cc);
65 * For each vertex <code>v</code> in <code>g</code>,
66 * calculates the average shortest path length from <code>v</code>
67 * to all other vertices in <code>g</code>, ignoring edge weights.
68 * @see #diameter(Hypergraph)
69 * @see edu.uci.ics.jung.algorithms.scoring.ClosenessCentrality
71 public static <V,E> Transformer<V, Double> averageDistances(Hypergraph<V,E> g)
73 final ClosenessCentrality<V,E> cc = new ClosenessCentrality<V,E>(g,
74 new UnweightedShortestPath<V,E>(g));
75 return new VertexScoreTransformer<V, Double>(cc);
79 * Returns the diameter of <code>g</code> using the metric
80 * specified by <code>d</code>. The diameter is defined to be
81 * the maximum, over all pairs of vertices <code>u,v</code>,
82 * of the length of the shortest path from <code>u</code> to
83 * <code>v</code>. If the graph is disconnected (that is, not
84 * all pairs of vertices are reachable from one another), the
85 * value returned will depend on <code>use_max</code>:
86 * if <code>use_max == true</code>, the value returned
87 * will be the the maximum shortest path length over all pairs of <b>connected</b>
88 * vertices; otherwise it will be <code>Double.POSITIVE_INFINITY</code>.
90 public static <V, E> double diameter(Hypergraph<V,E> g, Distance<V> d, boolean use_max)
93 Collection<V> vertices = g.getVertices();
97 if (v.equals(w) == false) // don't include self-distances
99 Number dist = d.getDistance(v, w);
103 return Double.POSITIVE_INFINITY;
106 diameter = Math.max(diameter, dist.doubleValue());
114 * Returns the diameter of <code>g</code> using the metric
115 * specified by <code>d</code>. The diameter is defined to be
116 * the maximum, over all pairs of vertices <code>u,v</code>,
117 * of the length of the shortest path from <code>u</code> to
118 * <code>v</code>, or <code>Double.POSITIVE_INFINITY</code>
119 * if any of these distances do not exist.
120 * @see #diameter(Hypergraph, Distance, boolean)
122 public static <V, E> double diameter(Hypergraph<V,E> g, Distance<V> d)
124 return diameter(g, d, false);
128 * Returns the diameter of <code>g</code>, ignoring edge weights.
129 * @see #diameter(Hypergraph, Distance, boolean)
131 public static <V, E> double diameter(Hypergraph<V,E> g)
133 return diameter(g, new UnweightedShortestPath<V,E>(g));