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

LineHitsSource
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)
732    {
742        if (num_iterations < 1)
750            throw new IllegalArgumentException("num_iterations must be >= 1");
76         
772        if (convergence_threshold < 0)
780            throw new IllegalArgumentException("convergence_threshold must be >= 0");
79  
802        this.edge_weights = edge_weights;
812        this.voltages = voltages;
822        this.max_iterations = num_iterations;
832        this.convergence_threshold = convergence_threshold;
842    }
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     {
942        this(new ConstantEdgeValue(1), voltages, num_iterations, threshold);
952    }
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     {
1061        if (sources == null || sources.isEmpty() ||
107             sinks == null || sinks.isEmpty())
1080            throw new IllegalArgumentException("at least one source and one " +
109                     "sink must exist");
110  
1111        if (sources.size() + sinks.size() > g.numVertices())
1120            throw new IllegalArgumentException("either sources and sinks overlap " +
113                 "or sources and sinks contain vertices not in g");
114         
1151        Map unit_sources = new HashMap();
1161        for (Iterator iter = sources.iterator(); iter.hasNext(); )
1171            unit_sources.put(iter.next(), new Double(1.0));
118         
1191        calculateVoltages(g, unit_sources, sinks);
1201    }
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     {
1322        if (source_voltages == null || source_voltages.isEmpty() ||
133             sinks == null || sinks.isEmpty())
1340            throw new IllegalArgumentException("at least one source and one " +
135                 "sink must exist");
136         
1372        if (source_voltages.size() + sinks.size() > g.numVertices())
1380            throw new IllegalArgumentException("either sources and sinks overlap " +
139                 "or sources and sinks contain vertices not in g");
140  
1412        Set sources = source_voltages.keySet();
142         
143         // set up initial voltages
1442        Indexer id = Indexer.getIndexer(g);
1452        Set vertices = g.getVertices();
1462        double[] volt_array = new double[vertices.size()];
14716        for (int i = 0; i < volt_array.length; i++)
148         {
14914            Vertex v = (Vertex)id.getVertex(i);
15014            if (sources.contains(v))
151             {
1523                Number voltage = (Number)source_voltages.get(v);
1533                volt_array[i] = voltage.doubleValue();
1543                voltages.setNumber(v, voltage);
155             }
156             else
157             {
15811                volt_array[i] = 0;
15911                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.
1672        int iteration = 0;
1682        double max_change = Double.POSITIVE_INFINITY;
16928        while (iteration++ < max_iterations && max_change > convergence_threshold)
170         {
17126            max_change = 0;
17226            for (Iterator iter = vertices.iterator(); iter.hasNext(); )
173             {
174182                Vertex v = (Vertex)iter.next();
175182                if (sources.contains(v) || sinks.contains(v))
17635                    continue;
177112                Set edges = v.getInEdges();
178112                double voltage_sum = 0;
179112                double weight_sum = 0;
180112                for (Iterator e_iter = edges.iterator(); e_iter.hasNext(); )
181                 {
182276                    Edge e = (Edge)e_iter.next();
183276                    Vertex w = e.getOpposite(v);
184276                    double weight = edge_weights.getNumber(e).doubleValue();
185276                    voltage_sum += volt_array[id.getIndex(w)] * weight;
186276                    weight_sum += weight;
187                 }
188                 
189                 double new_voltage;
190112                if (voltage_sum == 0 && weight_sum == 0)
1910                    new_voltage = 0;
192                 else
193112                    new_voltage = voltage_sum / weight_sum;
194112                max_change = Math.max(max_change,
195                     Math.abs(voltages.getNumber(v).doubleValue() - new_voltage));
196112                voltages.setNumber(v, new Double(new_voltage));
197             }
198             
199             // set up volt_array for next iteration
200208            for (int i = 0; i < volt_array.length; i++)
201182                volt_array[i] = voltages.getNumber(id.getVertex(i)).doubleValue();
202         }
2032    }
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     {
2171        Set sources = new HashSet();
2181        Set sinks = new HashSet();
2191        sources.add(source);
2201        sinks.add(target);
2211        calculateVoltages((Graph)source.getGraph(), sources, sinks);
2221    }
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.