edu.uci.ics.jung.algorithms.importance
Class VoltageRanker

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.importance.VoltageRanker

public class VoltageRanker
extends Object

Ranks vertices in a graph according to their 'voltage' in an approximate solution to the Kirchoff equations. This is accomplished by tying "source" vertices to specified positive voltages, "sink" vertices to 0 V, and iteratively updating the voltage of each other vertex to the (weighted) average of the voltages of its neighbors.

The resultant voltages will all be in the range [0, max] where max is the largest voltage of any source vertex (in the absence of negative source voltages; see below).

A few notes about this algorithm's interpretation of the graph data:

Author:
Joshua O'Madadhain

Field Summary
protected  double convergence_threshold
           
protected  NumberEdgeValue edge_weights
           
protected  int max_iterations
           
protected  NumberVertexValue voltages
           
 
Constructor Summary
VoltageRanker(NumberEdgeValue edge_weights, NumberVertexValue voltages, int num_iterations, double convergence_threshold)
          Creates an instance of VoltageRanker which uses the edge weights specified by edge_weights, and which stores the voltages (ranks) as specified by voltages.
VoltageRanker(NumberVertexValue voltages, int num_iterations, double threshold)
          Creates an instance of VoltageRanker which treats the edges as though they were unweighted, and which stores the voltages (ranks) as specified by voltages.
 
Method Summary
 void calculateVoltages(Graph g, Map source_voltages, Set sinks)
          Calculates the voltages for g based on the specified source and sink vertex sets.
 void calculateVoltages(Graph g, Set sources, Set sinks)
          Calculates the voltages for g based on assigning each of the vertices in source a voltage of 1 V.
 void calculateVoltages(Vertex source, Vertex target)
          Calculates an approximation of the solution of the Kirchhoff equations for voltage, given that source supplies 1 V and target is tied to ground (O V).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

edge_weights

protected NumberEdgeValue edge_weights

voltages

protected NumberVertexValue voltages

max_iterations

protected int max_iterations

convergence_threshold

protected double convergence_threshold
Constructor Detail

VoltageRanker

public VoltageRanker(NumberEdgeValue edge_weights,
                     NumberVertexValue voltages,
                     int num_iterations,
                     double convergence_threshold)
Creates an instance of VoltageRanker which uses the edge weights specified by edge_weights, and which stores the voltages (ranks) as specified by voltages.


VoltageRanker

public VoltageRanker(NumberVertexValue voltages,
                     int num_iterations,
                     double threshold)
Creates an instance of VoltageRanker which treats the edges as though they were unweighted, and which stores the voltages (ranks) as specified by voltages.

Method Detail

calculateVoltages

public void calculateVoltages(Graph g,
                              Set sources,
                              Set sinks)
Calculates the voltages for g based on assigning each of the vertices in source a voltage of 1 V.

Parameters:
sources - vertices tied to 1 V
sinks - vertices tied to 0 V
See Also:
calculateVoltages(Graph, Map, Set)

calculateVoltages

public void calculateVoltages(Graph g,
                              Map source_voltages,
                              Set sinks)
Calculates the voltages for g based on the specified source and sink vertex sets.

Parameters:
g - the graph for which voltages will be calculated
source_voltages - a map from vertices to source voltage values
sinks - a set of vertices to tie to 0 V

calculateVoltages

public void calculateVoltages(Vertex source,
                              Vertex target)
Calculates an approximation of the solution of the Kirchhoff equations for voltage, given that source supplies 1 V and target is tied to ground (O V). Each other vertex will be assigned a voltage (rank) in the range [0,1].

Parameters:
source - the vertex whose voltage is tied to 1 V
target - the vertex whose voltage is tied to 0 V