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

   1 /*
   2  * Created on Jul 15, 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.Collection;
  15 import java.util.Collections;
  16 import java.util.HashMap;
  17 import java.util.Map;
  18
  19 import org.apache.commons.collections15.Transformer;
  20
  21 import edu.uci.ics.jung.algorithms.scoring.util.UniformDegreeWeight;
  22 import edu.uci.ics.jung.graph.Hypergraph;
  23
  24 /**
  25  * Assigns scores to vertices according to their 'voltage' in an approximate
  26  * solution to the Kirchoff equations.  This is accomplished by tying "source"
  27  * vertices to specified positive voltages, "sink" vertices to 0 V, and
  28  * iteratively updating the voltage of each other vertex to the (weighted)
  29  * average of the voltages of its neighbors.
  30  *
  31  * <p>The resultant voltages will all be in the range <code>[0, max]</code>
  32  * where <code>max</code> is the largest voltage of any source vertex (in the
  33  * absence of negative source voltages; see below).
  34  *
  35  * <p>A few notes about this algorithm's interpretation of the graph data:
  36  * <ul>
  37  * <li/>Higher edge weights are interpreted as indicative of greater
  38  * influence/effect than lower edge weights.
  39  * <li/>Negative edge weights (and negative "source" voltages) invalidate
  40  * the interpretation of the resultant values as voltages.  However, this
  41  * algorithm will not reject graphs with negative edge weights or source voltages.
  42  * <li/>Parallel edges are equivalent to a single edge whose weight is the
  43  * sum of the weights on the parallel edges.
  44  * <li/>Current flows along undirected edges in both directions,
  45  * but only flows along directed edges in the direction of the edge.
  46  * </ul>
  47  * </p>
  48  */
  49 public class VoltageScorer<V, E> extends AbstractIterativeScorer<V, E, Double>
  50         implements VertexScorer<V, Double>
  51 {
  52     protected Map<V, ? extends Number> source_voltages;
  53     protected Collection<V> sinks;
  54
  55     /**
  56      * Creates an instance with the specified graph, edge weights, source voltages,
  57      * and sinks.
  58      * @param g the input graph
  59      * @param edge_weights the edge weights, representing conductivity
  60      * @param source_voltages the (fixed) voltage for each source
  61      * @param sinks the vertices whose voltages are tied to 0
  62      */
  63     public VoltageScorer(Hypergraph<V, E> g, Transformer<E, ? extends Number> edge_weights,
  64             Map<V, ? extends Number> source_voltages, Collection<V> sinks)
  65     {
  66         super(g, edge_weights);
  67         this.source_voltages = source_voltages;
  68         this.sinks = sinks;
  69         initialize();
  70     }
  71
  72     /**
  73      * Creates an instance with the specified graph, edge weights, source vertices
  74      * (each of whose 'voltages' are tied to 1), and sinks.
  75      * @param g the input graph
  76      * @param edge_weights the edge weights, representing conductivity
  77      * @param sources the vertices whose voltages are tied to 1
  78      * @param sinks the vertices whose voltages are tied to 0
  79      */
  80     public VoltageScorer(Hypergraph<V, E> g, Transformer<E, ? extends Number> edge_weights,
  81             Collection<V> sources, Collection<V> sinks)
  82     {
  83         super(g, edge_weights);
  84
  85         Map<V, Double> unit_voltages = new HashMap<V, Double>();
  86         for(V v : sources)
  87             unit_voltages.put(v, new Double(1.0));
  88         this.source_voltages = unit_voltages;
  89         this.sinks = sinks;
  90         initialize();
  91     }
  92
  93     /**
  94      * Creates an instance with the specified graph, source vertices
  95      * (each of whose 'voltages' are tied to 1), and sinks.
  96      * The outgoing edges for each vertex are assigned
  97      * weights that sum to 1.
  98      * @param g the input graph
  99      * @param sources the vertices whose voltages are tied to 1
 100      * @param sinks the vertices whose voltages are tied to 0
 101      */
 102     public VoltageScorer(Hypergraph<V, E> g, Collection<V> sources, Collection<V> sinks)
 103     {
 104         super(g);
 105
 106         Map<V, Double> unit_voltages = new HashMap<V, Double>();
 107         for(V v : sources)
 108             unit_voltages.put(v, new Double(1.0));
 109         this.source_voltages = unit_voltages;
 110         this.sinks = sinks;
 111         initialize();
 112     }
 113
 114     /**
 115      * Creates an instance with the specified graph, source voltages,
 116      * and sinks.  The outgoing edges for each vertex are assigned
 117      * weights that sum to 1.
 118      * @param g the input graph
 119      * @param source_voltages the (fixed) voltage for each source
 120      * @param sinks the vertices whose voltages are tied to 0
 121      */
 122     public VoltageScorer(Hypergraph<V, E> g, Map<V, ? extends Number> source_voltages,
 123                 Collection<V> sinks)
 124     {
 125         super(g);
 126         this.source_voltages = source_voltages;
 127         this.sinks = sinks;
 128         this.edge_weights = new UniformDegreeWeight<V,E>(g);
 129         initialize();
 130     }
 131
 132     /**
 133      * Creates an instance with the specified graph, edge weights, source, and
 134      * sink.  The source vertex voltage is tied to 1.
 135      * @param g the input graph
 136      * @param edge_weights the edge weights, representing conductivity
 137      * @param source the vertex whose voltage is tied to 1
 138      * @param sink the vertex whose voltage is tied to 0
 139      */
 140     public VoltageScorer(Hypergraph<V,E> g, Transformer<E, ? extends Number> edge_weights,
 141                 V source, V sink)
 142     {
 143         this(g, edge_weights, Collections.singletonMap(source, 1.0), Collections.singletonList(sink));
 144         initialize();
 145     }
 146
 147     /**
 148      * Creates an instance with the specified graph, edge weights, source, and
 149      * sink.  The source vertex voltage is tied to 1.
 150      * The outgoing edges for each vertex are assigned
 151      * weights that sum to 1.
 152      * @param g the input graph
 153      * @param source the vertex whose voltage is tied to 1
 154      * @param sink the vertex whose voltage is tied to 0
 155      */
 156     public VoltageScorer(Hypergraph<V,E> g, V source, V sink)
 157     {
 158         this(g, Collections.singletonMap(source, 1.0), Collections.singletonList(sink));
 159         initialize();
 160     }
 161
 162
 163     /**
 164      * Initializes the state of this instance.
 165      */
 166     @Override
 167     public void initialize()
 168     {
 169         super.initialize();
 170
 171         // sanity check
 172         if (source_voltages.isEmpty() || sinks.isEmpty())
 173             throw new IllegalArgumentException("Both sources and sinks (grounds) must be defined");
 174
 175         if (source_voltages.size() + sinks.size() > graph.getVertexCount())
 176             throw new IllegalArgumentException("Source/sink sets overlap, or contain vertices not in graph");
 177
 178         for (Map.Entry<V, ? extends Number> entry : source_voltages.entrySet())
 179         {
 180             V v = entry.getKey();
 181             if (sinks.contains(v))
 182                 throw new IllegalArgumentException("Vertex " + v + " is incorrectly specified as both source and sink");
 183             double value = entry.getValue().doubleValue();
 184             if (value <= 0)
 185                 throw new IllegalArgumentException("Source vertex " + v + " has negative voltage");
 186         }
 187
 188         // set up initial voltages
 189         for (V v : graph.getVertices())
 190         {
 191             if (source_voltages.containsKey(v))
 192                 setOutputValue(v, source_voltages.get(v).doubleValue());
 193             else
 194                 setOutputValue(v, 0.0);
 195         }
 196     }
 197
 198     /**
 199      * @see edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer#update(Object)
 200      */
 201     @Override
 202     public double update(V v)
 203     {
 204         // if it's a voltage source or sink, we're done
 205         Number source_volts = source_voltages.get(v);
 206         if (source_volts != null)
 207         {
 208             setOutputValue(v, source_volts.doubleValue());
 209             return 0.0;
 210         }
 211         if (sinks.contains(v))
 212         {
 213             setOutputValue(v, 0.0);
 214             return 0.0;
 215         }
 216
 217         Collection<E> edges = graph.getInEdges(v);
 218         double voltage_sum = 0;
 219         double weight_sum = 0;
 220         for (E e: edges)
 221         {
 222                 int incident_count = getAdjustedIncidentCount(e);
 223                 for (V w : graph.getIncidentVertices(e))
 224                 {
 225                         if (!w.equals(v) || hyperedges_are_self_loops)
 226                         {
 227                                 double weight = getEdgeWeight(w,e).doubleValue() / incident_count;
 228                                 voltage_sum += getCurrentValue(w).doubleValue() * weight;
 229                                 weight_sum += weight;
 230                         }
 231                 }
 232 //            V w = graph.getOpposite(v, e);
 233 //            double weight = getEdgeWeight(w,e).doubleValue();
 234 //            voltage_sum += getCurrentValue(w).doubleValue() * weight;
 235 //            weight_sum += weight;
 236         }
 237
 238         // if either is 0, new value is 0
 239         if (voltage_sum == 0 || weight_sum == 0)
 240         {
 241             setOutputValue(v, 0.0);
 242             return getCurrentValue(v).doubleValue();
 243         }
 244
 245         setOutputValue(v, voltage_sum / weight_sum);
 246         return Math.abs(getCurrentValue(v).doubleValue() - voltage_sum / weight_sum);
 247     }
 248
 249 }
 250