# Coverage details for edu.uci.ics.jung.algorithms.importance.VoltageRanker

Line | Hits | Source
--- | --- | ---
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 |  | `/*`
11 |  | `* Created on Aug 11, 2004`
12 |  | `*`
13 |  | `*/`
14 |  | `package edu.uci.ics.jung.algorithms.importance;`
15 |  | ``
16 |  | `import java.util.HashMap;`
17 |  | `import java.util.HashSet;`
18 |  | `import java.util.Iterator;`
19 |  | `import java.util.Map;`
20 |  | `import java.util.Set;`
21 |  | ``
22 |  | ``
23 |  | `import edu.uci.ics.jung.graph.Edge;`
24 |  | `import edu.uci.ics.jung.graph.Graph;`
25 |  | `import edu.uci.ics.jung.graph.Vertex;`
26 |  | `import edu.uci.ics.jung.graph.decorators.ConstantEdgeValue;`
27 |  | `import edu.uci.ics.jung.graph.decorators.Indexer;`
28 |  | `import edu.uci.ics.jung.graph.decorators.NumberEdgeValue;`
29 |  | `import edu.uci.ics.jung.graph.decorators.NumberVertexValue;`
30 |  | ``
31 |  | ``
32 |  | `/**`
33 |  | `* Ranks vertices in a graph according to their 'voltage' in an approximate`
34 |  | `* solution to the Kirchoff equations. This is accomplished by tying "source"`
35 |  | `* vertices to specified positive voltages, "sink" vertices to 0 V, and`
36 |  | `* iteratively updating the voltage of each other vertex to the (weighted)`
37 |  | `* average of the voltages of its neighbors.`
38 |  | `*`
39 |  | `* <p>The resultant voltages will all be in the range <code>[0, max]</code>`
40 |  | `* where <code>max</code> is the largest voltage of any source vertex (in the`
41 |  | `* absence of negative source voltages; see below).`
42 |  | `*`
43 |  | `* <p>A few notes about this algorithm's interpretation of the graph data:`
44 |  | `* <ul>`
45 |  | `* <li/>Higher edge weights are interpreted as indicative of greater`
46 |  | `* influence/effect than lower edge weights.`
47 |  | `* <li/>Negative edge weights (and negative "source" voltages) invalidate`
48 |  | `* the interpretation of the resultant values as voltages. However, this`
49 |  | `* algorithm will not reject graphs with negative edge weights or source voltages.`
50 |  | `* <li/>Parallel edges are equivalent to a single edge whose weight is the`
51 |  | `* sum of the weights on the parallel edges.`
52 |  | `* <li/>Current flows along undirected edges in both directions,`
53 |  | `* but only flows along directed edges in the direction of the edge.`
54 |  | `* </ul>`
55 |  | `* </p>`
56 |  | `*`
57 |  | `* @author Joshua O'Madadhain`
58 |  | `*/`
59 |  | `public class VoltageRanker`
60 |  | `{`
61 |  | `protected NumberEdgeValue edge_weights;`
62 |  | `protected NumberVertexValue voltages;`
63 |  | `protected int max_iterations;`
64 |  | `protected double convergence_threshold;`
65 |  | ``
66 |  | `/**`
67 |  | `* Creates an instance of <code>VoltageRanker</code> which uses the`
68 |  | `* edge weights specified by <code>edge_weights</code>, and which stores`
69 |  | `* the voltages (ranks) as specified by <code>voltages</code>.`
70 |  | `*/`
71 |  | `public VoltageRanker(NumberEdgeValue edge_weights, NumberVertexValue voltages,`
72 |  | `int num_iterations, double convergence_threshold)`
73 | 2 | `{`
74 | 2 | `if (num_iterations < 1)`
75 | 0 | `throw new IllegalArgumentException("num_iterations must be >= 1");`
76 |  | ``
77 | 2 | `if (convergence_threshold < 0)`
78 | 0 | `throw new IllegalArgumentException("convergence_threshold must be >= 0");`
79 |  | ``
80 | 2 | `this.edge_weights = edge_weights;`
81 | 2 | `this.voltages = voltages;`
82 | 2 | `this.max_iterations = num_iterations;`
83 | 2 | `this.convergence_threshold = convergence_threshold;`
84 | 2 | `}`
85 |  | ``
86 |  | `/**`
87 |  | `* Creates an instance of <code>VoltageRanker</code> which treats the`
88 |  | `* edges as though they were unweighted, and which stores`
89 |  | `* the voltages (ranks) as specified by <code>voltages</code>.`
90 |  | `*/`
91 |  | `public VoltageRanker(NumberVertexValue voltages, int num_iterations,`
92 |  | `double threshold)`
93 |  | `{`
94 | 2 | `this(new ConstantEdgeValue(1), voltages, num_iterations, threshold);`
95 | 2 | `}`
96 |  | ``
97 |  | `/**`
98 |  | `* Calculates the voltages for <code>g</code> based on assigning each of the`
99 |  | `* vertices in <code>source</code> a voltage of 1 V.`
100 |  | `* @param sources vertices tied to 1 V`
101 |  | `* @param sinks vertices tied to 0 V`
102 |  | `* @see #calculateVoltages(Graph, Map, Set)`
103 |  | `*/`
104 |  | `public void calculateVoltages(Graph g, Set sources, Set sinks)`
105 |  | `{`
106 | 1 | `if (sources == null || sources.isEmpty() ||`
107 |  | `sinks == null || sinks.isEmpty())`
108 | 0 | `throw new IllegalArgumentException("at least one source and one " +`
109 |  | `"sink must exist");`
110 |  | ``
111 | 1 | `if (sources.size() + sinks.size() > g.numVertices())`
112 | 0 | `throw new IllegalArgumentException("either sources and sinks overlap " +`
113 |  | `"or sources and sinks contain vertices not in g");`
114 |  | ``
115 | 1 | `Map unit_sources = new HashMap();`
116 | 1 | `for (Iterator iter = sources.iterator(); iter.hasNext(); )`
117 | 1 | `unit_sources.put(iter.next(), new Double(1.0));`
118 |  | ``
119 | 1 | `calculateVoltages(g, unit_sources, sinks);`
120 | 1 | `}`
121 |  | ``
122 |  | `/**`
123 |  | `* Calculates the voltages for <code>g</code> based on the specified source`
124 |  | `* and sink vertex sets.`
125 |  | `*`
126 |  | `* @param g the graph for which voltages will be calculated`
127 |  | `* @param source_voltages a map from vertices to source voltage values`
128 |  | `* @param sinks a set of vertices to tie to 0 V`
129 |  | `*/`
130 |  | `public void calculateVoltages(Graph g, Map source_voltages, Set sinks)`
131 |  | `{`
132 | 2 | `if (source_voltages == null || source_voltages.isEmpty() ||`
133 |  | `sinks == null || sinks.isEmpty())`
134 | 0 | `throw new IllegalArgumentException("at least one source and one " +`
135 |  | `"sink must exist");`
136 |  | ``
137 | 2 | `if (source_voltages.size() + sinks.size() > g.numVertices())`
138 | 0 | `throw new IllegalArgumentException("either sources and sinks overlap " +`
139 |  | `"or sources and sinks contain vertices not in g");`
140 |  | ``
141 | 2 | `Set sources = source_voltages.keySet();`
142 |  | ``
143 |  | `// set up initial voltages`
144 | 2 | `Indexer id = Indexer.getIndexer(g);`
145 | 2 | `Set vertices = g.getVertices();`
146 | 2 | `double[] volt_array = new double[vertices.size()];`
147 | 16 | `for (int i = 0; i < volt_array.length; i++)`
148 |  | `{`
149 | 14 | `Vertex v = (Vertex)id.getVertex(i);`
150 | 14 | `if (sources.contains(v))`
151 |  | `{`
152 | 3 | `Number voltage = (Number)source_voltages.get(v);`
153 | 3 | `volt_array[i] = voltage.doubleValue();`
154 | 3 | `voltages.setNumber(v, voltage);`
155 |  | `}`
156 |  | `else`
157 |  | `{`
158 | 11 | `volt_array[i] = 0;`
159 | 11 | `voltages.setNumber(v, new Double(0));`
160 |  | `}`
161 |  | `}`
162 |  | ``
163 |  | `// update voltages of each vertex to the (weighted) average of its`
164 |  | `// neighbors, until either (a) the number of iterations exceeds the`
165 |  | `// maximum number of iterations specified, or (b) the largest change of`
166 |  | `// any voltage is no greater than the specified convergence threshold.`
167 | 2 | `int iteration = 0;`
168 | 2 | `double max_change = Double.POSITIVE_INFINITY;`
169 | 28 | `while (iteration++ < max_iterations && max_change > convergence_threshold)`
170 |  | `{`
171 | 26 | `max_change = 0;`
172 | 26 | `for (Iterator iter = vertices.iterator(); iter.hasNext(); )`
173 |  | `{`
174 | 182 | `Vertex v = (Vertex)iter.next();`
175 | 182 | `if (sources.contains(v) || sinks.contains(v))`
176 | 35 | `continue;`
177 | 112 | `Set edges = v.getInEdges();`
178 | 112 | `double voltage_sum = 0;`
179 | 112 | `double weight_sum = 0;`
180 | 112 | `for (Iterator e_iter = edges.iterator(); e_iter.hasNext(); )`
181 |  | `{`
182 | 276 | `Edge e = (Edge)e_iter.next();`
183 | 276 | `Vertex w = e.getOpposite(v);`
184 | 276 | `double weight = edge_weights.getNumber(e).doubleValue();`
185 | 276 | `voltage_sum += volt_array[id.getIndex(w)] * weight;`
186 | 276 | `weight_sum += weight;`
187 |  | `}`
188 |  | ``
189 |  | `double new_voltage;`
190 | 112 | `if (voltage_sum == 0 && weight_sum == 0)`
191 | 0 | `new_voltage = 0;`
192 |  | `else`
193 | 112 | `new_voltage = voltage_sum / weight_sum;`
194 | 112 | `max_change = Math.max(max_change,`
195 |  | `Math.abs(voltages.getNumber(v).doubleValue() - new_voltage));`
196 | 112 | `voltages.setNumber(v, new Double(new_voltage));`
197 |  | `}`
198 |  | ``
199 |  | `// set up volt_array for next iteration`
200 | 208 | `for (int i = 0; i < volt_array.length; i++)`
201 | 182 | `volt_array[i] = voltages.getNumber(id.getVertex(i)).doubleValue();`
202 |  | `}`
203 | 2 | `}`
204 |  | ``
205 |  | ``
206 |  | `/**`
207 |  | `* Calculates an approximation of the solution of the Kirchhoff equations`
208 |  | `* for voltage, given that <code>source</code> supplies 1 V and <code>target</code>`
209 |  | `* is tied to ground (O V). Each other vertex will be assigned a voltage (rank)`
210 |  | `* in the range [0,1].`
211 |  | `*`
212 |  | `* @param source the vertex whose voltage is tied to 1 V`
213 |  | `* @param target the vertex whose voltage is tied to 0 V`
214 |  | `*/`
215 |  | `public void calculateVoltages(Vertex source, Vertex target)`
216 |  | `{`
217 | 1 | `Set sources = new HashSet();`
218 | 1 | `Set sinks = new HashSet();`
219 | 1 | `sources.add(source);`
220 | 1 | `sinks.add(target);`
221 | 1 | `calculateVoltages((Graph)source.getGraph(), sources, sinks);`
222 | 1 | `}`
223 |  | `}`

this report was generated by version 1.0.5 of jcoverage. visit www.jcoverage.com for updates. | copyright © 2003, jcoverage ltd. all rights reserved. Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.