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. |
copyright © 2003, jcoverage ltd. all rights reserved. |