third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/DistanceStatistics.java

   1 /*
   2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
   3 * of California
   4 * All rights reserved.
   5 *
   6 * This software is open-source under the BSD license; see either
   7 * "license.txt" or
   8 * http://jung.sourceforge.net/license.txt for a description.
   9 */
  10 package edu.uci.ics.jung.algorithms.shortestpath;
  11 import java.util.Collection;
  12
  13 import org.apache.commons.collections15.Transformer;
  14
  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;
  18
  19 /**
  20  * Statistics relating to vertex-vertex distances in a graph.
  21  *
  22  * <p>Formerly known as <code>GraphStatistics</code> in JUNG 1.x.</p>
  23  *
  24  * @author Scott White
  25  * @author Joshua O'Madadhain
  26  */
  27 public class DistanceStatistics
  28 {
  29     /**
  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>&lt;u,v&gt;</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>).
  39      *
  40      * <p>Does not include self-distances (path lengths from <code>v</code>
  41      * to <code>v</code>).
  42      *
  43      * <p>To calculate the average distances, ignoring edge weights if any:
  44      * <pre>
  45      * Map distances = DistanceStatistics.averageDistances(g, new UnweightedShortestPath(g));
  46      * </pre>
  47      * To calculate the average distances respecting edge weights:
  48      * <pre>
  49      * DijkstraShortestPath dsp = new DijkstraShortestPath(g, nev);
  50      * Map distances = DistanceStatistics.averageDistances(g, dsp);
  51      * </pre>
  52      * where <code>nev</code> is an instance of <code>Transformer</code> that
  53      * is used to fetch the weight for each edge.
  54      *
  55      * @see edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath
  56      * @see edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance
  57      */
  58     public static <V,E> Transformer<V,Double> averageDistances(Hypergraph<V,E> graph, Distance<V> d)
  59     {
  60         final ClosenessCentrality<V,E> cc = new ClosenessCentrality<V,E>(graph, d);
  61         return new VertexScoreTransformer<V, Double>(cc);
  62     }
  63
  64     /**
  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
  70      */
  71     public static <V,E> Transformer<V, Double> averageDistances(Hypergraph<V,E> g)
  72     {
  73         final ClosenessCentrality<V,E> cc = new ClosenessCentrality<V,E>(g,
  74                         new UnweightedShortestPath<V,E>(g));
  75         return new VertexScoreTransformer<V, Double>(cc);
  76     }
  77
  78     /**
  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>.
  89      */
  90     public static <V, E> double diameter(Hypergraph<V,E> g, Distance<V> d, boolean use_max)
  91     {
  92         double diameter = 0;
  93         Collection<V> vertices = g.getVertices();
  94         for(V v : vertices) {
  95             for(V w : vertices) {
  96
  97                 if (v.equals(w) == false) // don't include self-distances
  98                 {
  99                     Number dist = d.getDistance(v, w);
 100                     if (dist == null)
 101                     {
 102                         if (!use_max)
 103                             return Double.POSITIVE_INFINITY;
 104                     }
 105                     else
 106                         diameter = Math.max(diameter, dist.doubleValue());
 107                 }
 108             }
 109         }
 110         return diameter;
 111     }
 112
 113     /**
 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)
 121      */
 122     public static <V, E> double diameter(Hypergraph<V,E> g, Distance<V> d)
 123     {
 124         return diameter(g, d, false);
 125     }
 126
 127     /**
 128      * Returns the diameter of <code>g</code>, ignoring edge weights.
 129      * @see #diameter(Hypergraph, Distance, boolean)
 130      */
 131     public static <V, E> double diameter(Hypergraph<V,E> g)
 132     {
 133         return diameter(g, new UnweightedShortestPath<V,E>(g));
 134     }
 135
 136 }