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

   1 /*
   2  * Created on Jul 10, 2007
   3  *
   4  * Copyright (c) 2007, the JUNG Project and the Regents of the University
   5  * of California
   6  * All rights reserved.
   7  *
   8  * This software is open-source under the BSD license; see either
   9  * "license.txt" or
  10  * http://jung.sourceforge.net/license.txt for a description.
  11  */
  12 package edu.uci.ics.jung.algorithms.scoring;
  13
  14 import java.util.HashMap;
  15 import java.util.Map;
  16
  17 import org.apache.commons.collections15.Transformer;
  18
  19 import edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance;
  20 import edu.uci.ics.jung.algorithms.shortestpath.Distance;
  21 import edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath;
  22 import edu.uci.ics.jung.graph.Hypergraph;
  23
  24 /**
  25  * Assigns scores to vertices based on their distances to each other vertex
  26  * in the graph.
  27  *
  28  * This class optionally normalizes its results based on the value of its
  29  * 'averaging' constructor parameter.  If it is <code>true</code>,
  30  * then the value returned for vertex v is 1 / (_average_ distance from v to all other vertices);
  31  * this is sometimes called <i>closeness centrality</i>.
  32  * If it is <code>false</code>, then the value returned is 1 / (_total_ distance from
  33  * v to all other vertices); this is sometimes referred to as <i>barycenter centrality</i>.
  34  * (If the average/total distance is 0, the value returned is {@code Double.POSITIVE_INFINITY}.)
  35  *
  36  * @see BarycenterScorer
  37  * @see ClosenessCentrality
  38  */
  39 public class DistanceCentralityScorer<V,E> implements VertexScorer<V, Double>
  40 {
  41     /**
  42      * The graph on which the vertex scores are to be calculated.
  43      */
  44     protected Hypergraph<V, E> graph;
  45
  46     /**
  47      * The metric to use for specifying the distance between pairs of vertices.
  48      */
  49     protected Distance<V> distance;
  50
  51     /**
  52      * The cache for the output results.  Null encodes "not yet calculated",
  53      * < 0 encodes "no such distance exists".
  54      */
  55     protected Map<V, Double> output;
  56
  57     /**
  58      * Specifies whether the values returned are the sum of the v-distances
  59      * or the mean v-distance.
  60      */
  61     protected boolean averaging;
  62
  63     /**
  64      * Specifies whether, for a vertex <code>v</code> with missing (null) distances,
  65      * <code>v</code>'s score should ignore the missing values or be set to 'null'.
  66      * Defaults to 'true'.
  67      */
  68     protected boolean ignore_missing;
  69
  70     /**
  71      * Specifies whether the values returned should ignore self-distances
  72      * (distances from <code>v</code> to itself).
  73      * Defaults to 'true'.
  74      */
  75     protected boolean ignore_self_distances;
  76
  77     /**
  78      * Creates an instance with the specified graph, distance metric, and
  79      * averaging behavior.
  80      *
  81      * @param graph     The graph on which the vertex scores are to be calculated.
  82      * @param distance  The metric to use for specifying the distance between
  83      * pairs of vertices.
  84      * @param averaging Specifies whether the values returned is the sum of all
  85      * v-distances or the mean v-distance.
  86      * @param ignore_missing    Specifies whether scores for missing distances
  87      * are to ignore missing distances or be set to null.
  88      * @param ignore_self_distances     Specifies whether distances from a vertex
  89      * to itself should be included in its score.
  90      */
  91     public DistanceCentralityScorer(Hypergraph<V,E> graph, Distance<V> distance,
  92                 boolean averaging, boolean ignore_missing,
  93                 boolean ignore_self_distances)
  94     {
  95         this.graph = graph;
  96         this.distance = distance;
  97         this.averaging = averaging;
  98         this.ignore_missing = ignore_missing;
  99         this.ignore_self_distances = ignore_self_distances;
 100         this.output = new HashMap<V, Double>();
 101     }
 102
 103     /**
 104      * Equivalent to <code>this(graph, distance, averaging, true, true)</code>.
 105      *
 106      * @param graph     The graph on which the vertex scores are to be calculated.
 107      * @param distance  The metric to use for specifying the distance between
 108      * pairs of vertices.
 109      * @param averaging Specifies whether the values returned is the sum of all
 110      * v-distances or the mean v-distance.
 111      */
 112     public DistanceCentralityScorer(Hypergraph<V,E> graph, Distance<V> distance,
 113                 boolean averaging)
 114     {
 115         this(graph, distance, averaging, true, true);
 116     }
 117
 118     /**
 119      * Creates an instance with the specified graph and averaging behavior
 120      * whose vertex distances are calculated based on the specified edge
 121      * weights.
 122      *
 123      * @param graph         The graph on which the vertex scores are to be
 124      * calculated.
 125      * @param edge_weights  The edge weights to use for specifying the distance
 126      * between pairs of vertices.
 127      * @param averaging     Specifies whether the values returned is the sum of
 128      * all v-distances or the mean v-distance.
 129      * @param ignore_missing    Specifies whether scores for missing distances
 130      * are to ignore missing distances or be set to null.
 131      * @param ignore_self_distances     Specifies whether distances from a vertex
 132      * to itself should be included in its score.
 133      */
 134     public DistanceCentralityScorer(Hypergraph<V,E> graph,
 135             Transformer<E, ? extends Number> edge_weights, boolean averaging,
 136             boolean ignore_missing, boolean ignore_self_distances)
 137     {
 138         this(graph, new DijkstraDistance<V,E>(graph, edge_weights), averaging,
 139                 ignore_missing, ignore_self_distances);
 140     }
 141
 142     /**
 143      * Equivalent to <code>this(graph, edge_weights, averaging, true, true)</code>.
 144      * @param graph         The graph on which the vertex scores are to be
 145      * calculated.
 146      * @param edge_weights  The edge weights to use for specifying the distance
 147      * between pairs of vertices.
 148      * @param averaging     Specifies whether the values returned is the sum of
 149      * all v-distances or the mean v-distance.
 150      */
 151     public DistanceCentralityScorer(Hypergraph<V,E> graph,
 152             Transformer<E, ? extends Number> edge_weights, boolean averaging)
 153     {
 154         this(graph, new DijkstraDistance<V,E>(graph, edge_weights), averaging,
 155                 true, true);
 156     }
 157
 158     /**
 159      * Creates an instance with the specified graph and averaging behavior
 160      * whose vertex distances are calculated on the unweighted graph.
 161      *
 162      * @param graph         The graph on which the vertex scores are to be
 163      * calculated.
 164      * @param averaging     Specifies whether the values returned is the sum of
 165      * all v-distances or the mean v-distance.
 166      * @param ignore_missing    Specifies whether scores for missing distances
 167      * are to ignore missing distances or be set to null.
 168      * @param ignore_self_distances     Specifies whether distances from a vertex
 169      * to itself should be included in its score.
 170      */
 171     public DistanceCentralityScorer(Hypergraph<V,E> graph, boolean averaging,
 172             boolean ignore_missing, boolean ignore_self_distances)
 173     {
 174         this(graph, new UnweightedShortestPath<V,E>(graph), averaging,
 175                 ignore_missing, ignore_self_distances);
 176     }
 177
 178     /**
 179      * Equivalent to <code>this(graph, averaging, true, true)</code>.
 180      * @param graph         The graph on which the vertex scores are to be
 181      * calculated.
 182      * @param averaging     Specifies whether the values returned is the sum of
 183      * all v-distances or the mean v-distance.
 184      */
 185     public DistanceCentralityScorer(Hypergraph<V,E> graph, boolean averaging)
 186     {
 187         this(graph, new UnweightedShortestPath<V,E>(graph), averaging, true, true);
 188     }
 189
 190         /**
 191          * Calculates the score for the specified vertex.  Returns {@code null} if
 192          * there are missing distances and such are not ignored by this instance.
 193          */
 194         public Double getVertexScore(V v)
 195         {
 196             Double value = output.get(v);
 197             if (value != null)
 198             {
 199                 if (value < 0)
 200                     return null;
 201                 return value;
 202             }
 203
 204             Map<V, Number> v_distances = new HashMap<V, Number>(distance.getDistanceMap(v));
 205             if (ignore_self_distances)
 206                 v_distances.remove(v);
 207
 208                 // if we don't ignore missing distances and there aren't enough
 209                 // distances, output null (shortcut)
 210                 if (!ignore_missing)
 211                 {
 212                         int num_dests = graph.getVertexCount() -
 213                             (ignore_self_distances ? 1 : 0);
 214                         if (v_distances.size() != num_dests)
 215                         {
 216                                 output.put(v, -1.0);
 217                                 return null;
 218                         }
 219                 }
 220
 221                 Double sum = 0.0;
 222                 for (V w : graph.getVertices())
 223                 {
 224                         if (w.equals(v) && ignore_self_distances)
 225                                 continue;
 226                         Number w_distance = v_distances.get(w);
 227                         if (w_distance == null)
 228                                 if (ignore_missing)
 229                                         continue;
 230                                 else
 231                                 {
 232                                         output.put(v, -1.0);
 233                                         return null;
 234                                 }
 235                         else
 236                                 sum += w_distance.doubleValue();
 237                 }
 238                 value = sum;
 239                 if (averaging)
 240                     value /= v_distances.size();
 241
 242                 double score = value == 0 ?
 243                         Double.POSITIVE_INFINITY :
 244                         1.0 / value;
 245             output.put(v, score);
 246
 247                 return score;
 248         }
 249 }