| 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. |