edu.uci.ics.jung.algorithms.importance

Class VoltageRanker

java.lang.Object

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

public class VoltageRanker
extends java.lang.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:

• Higher edge weights are interpreted as indicative of greater influence/effect than lower edge weights.
• Negative edge weights (and negative "source" voltages) invalidate the interpretation of the resultant values as voltages. However, this algorithm will not reject graphs with negative edge weights or source voltages.
• Parallel edges are equivalent to a single edge whose weight is the sum of the weights on the parallel edges.
• Current flows along undirected edges in both directions, but only flows along directed edges in the direction of the edge.

Author:

Joshua O'Madadhain

Field Summary

Fields

Modifier and Type	Field and Description
protected double	convergence_threshold
protected NumberEdgeValue	edge_weights
protected int	max_iterations
protected NumberVertexValue	voltages

Constructor Summary

Constructors

Constructor and Description
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

Methods

Modifier and Type	Method and Description
void	calculateVoltages(Graph g, java.util.Map source_voltages, java.util.Set sinks) Calculates the voltages for g based on the specified source and sink vertex sets.
void	calculateVoltages(Graph g, java.util.Set sources, java.util.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,
                     java.util.Set sources,
                     java.util.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,
                     java.util.Map source_voltages,
                     java.util.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