2 * Created on Jul 15, 2007
4 * Copyright (c) 2007, the JUNG Project and the Regents of the University
8 * This software is open-source under the BSD license; see either
10 * http://jung.sourceforge.net/license.txt for a description.
12 package edu.uci.ics.jung.algorithms.scoring;
14 import java.util.Collection;
15 import java.util.Collections;
16 import java.util.HashMap;
19 import org.apache.commons.collections15.Transformer;
21 import edu.uci.ics.jung.algorithms.scoring.util.UniformDegreeWeight;
22 import edu.uci.ics.jung.graph.Hypergraph;
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.
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).
35 * <p>A few notes about this algorithm's interpretation of the graph data:
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.
49 public class VoltageScorer<V, E> extends AbstractIterativeScorer<V, E, Double>
50 implements VertexScorer<V, Double>
52 protected Map<V, ? extends Number> source_voltages;
53 protected Collection<V> sinks;
56 * Creates an instance with the specified graph, edge weights, source voltages,
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
63 public VoltageScorer(Hypergraph<V, E> g, Transformer<E, ? extends Number> edge_weights,
64 Map<V, ? extends Number> source_voltages, Collection<V> sinks)
66 super(g, edge_weights);
67 this.source_voltages = source_voltages;
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
80 public VoltageScorer(Hypergraph<V, E> g, Transformer<E, ? extends Number> edge_weights,
81 Collection<V> sources, Collection<V> sinks)
83 super(g, edge_weights);
85 Map<V, Double> unit_voltages = new HashMap<V, Double>();
87 unit_voltages.put(v, new Double(1.0));
88 this.source_voltages = unit_voltages;
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
102 public VoltageScorer(Hypergraph<V, E> g, Collection<V> sources, Collection<V> sinks)
106 Map<V, Double> unit_voltages = new HashMap<V, Double>();
108 unit_voltages.put(v, new Double(1.0));
109 this.source_voltages = unit_voltages;
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
122 public VoltageScorer(Hypergraph<V, E> g, Map<V, ? extends Number> source_voltages,
126 this.source_voltages = source_voltages;
128 this.edge_weights = new UniformDegreeWeight<V,E>(g);
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
140 public VoltageScorer(Hypergraph<V,E> g, Transformer<E, ? extends Number> edge_weights,
143 this(g, edge_weights, Collections.singletonMap(source, 1.0), Collections.singletonList(sink));
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
156 public VoltageScorer(Hypergraph<V,E> g, V source, V sink)
158 this(g, Collections.singletonMap(source, 1.0), Collections.singletonList(sink));
164 * Initializes the state of this instance.
167 public void initialize()
172 if (source_voltages.isEmpty() || sinks.isEmpty())
173 throw new IllegalArgumentException("Both sources and sinks (grounds) must be defined");
175 if (source_voltages.size() + sinks.size() > graph.getVertexCount())
176 throw new IllegalArgumentException("Source/sink sets overlap, or contain vertices not in graph");
178 for (Map.Entry<V, ? extends Number> entry : source_voltages.entrySet())
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();
185 throw new IllegalArgumentException("Source vertex " + v + " has negative voltage");
188 // set up initial voltages
189 for (V v : graph.getVertices())
191 if (source_voltages.containsKey(v))
192 setOutputValue(v, source_voltages.get(v).doubleValue());
194 setOutputValue(v, 0.0);
199 * @see edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer#update(Object)
202 public double update(V v)
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)
208 setOutputValue(v, source_volts.doubleValue());
211 if (sinks.contains(v))
213 setOutputValue(v, 0.0);
217 Collection<E> edges = graph.getInEdges(v);
218 double voltage_sum = 0;
219 double weight_sum = 0;
222 int incident_count = getAdjustedIncidentCount(e);
223 for (V w : graph.getIncidentVertices(e))
225 if (!w.equals(v) || hyperedges_are_self_loops)
227 double weight = getEdgeWeight(w,e).doubleValue() / incident_count;
228 voltage_sum += getCurrentValue(w).doubleValue() * weight;
229 weight_sum += weight;
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;
238 // if either is 0, new value is 0
239 if (voltage_sum == 0 || weight_sum == 0)
241 setOutputValue(v, 0.0);
242 return getCurrentValue(v).doubleValue();
245 setOutputValue(v, voltage_sum / weight_sum);
246 return Math.abs(getCurrentValue(v).doubleValue() - voltage_sum / weight_sum);