edu.uci.ics.jung.algorithms.scoring
Class VoltageScorer<V,E>

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer<V,E,Double>
      extended by edu.uci.ics.jung.algorithms.scoring.VoltageScorer<V,E>
All Implemented Interfaces:
VertexScorer<V,Double>, IterativeContext

public class VoltageScorer<V,E>
extends AbstractIterativeScorer<V,E,Double>
implements VertexScorer<V,Double>

Assigns scores to vertices 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:


Field Summary
protected  Collection<V> sinks
           
protected  Map<V,? extends Number> source_voltages
           
 
Fields inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer
edge_weights, graph, hyperedges_are_self_loops, max_delta, max_iterations, output_reversed, tolerance, total_iterations
 
Constructor Summary
VoltageScorer(Hypergraph<V,E> g, Collection<V> sources, Collection<V> sinks)
          Creates an instance with the specified graph, source vertices (each of whose 'voltages' are tied to 1), and sinks.
VoltageScorer(Hypergraph<V,E> g, Map<V,? extends Number> source_voltages, Collection<V> sinks)
          Creates an instance with the specified graph, source voltages, and sinks.
VoltageScorer(Hypergraph<V,E> g, org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights, Collection<V> sources, Collection<V> sinks)
          Creates an instance with the specified graph, edge weights, source vertices (each of whose 'voltages' are tied to 1), and sinks.
VoltageScorer(Hypergraph<V,E> g, org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights, Map<V,? extends Number> source_voltages, Collection<V> sinks)
          Creates an instance with the specified graph, edge weights, source voltages, and sinks.
VoltageScorer(Hypergraph<V,E> g, org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights, V source, V sink)
          Creates an instance with the specified graph, edge weights, source, and sink.
VoltageScorer(Hypergraph<V,E> g, V source, V sink)
          Creates an instance with the specified graph, edge weights, source, and sink.
 
Method Summary
 void initialize()
          Initializes the state of this instance.
 double update(V v)
          Updates the value for v.
 
Methods inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer
acceptDisconnectedGraph, afterStep, collectDisappearingPotential, done, evaluate, getAdjustedIncidentCount, getCurrentValue, getEdgeWeight, getEdgeWeights, getIterations, getMaxIterations, getOutputValue, getTolerance, getVertexScore, isDisconnectedGraphOK, setCurrentValue, setEdgeWeights, setHyperedgesAreSelfLoops, setMaxIterations, setOutputValue, setTolerance, step, swapOutputForCurrent, updateMaxDelta
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface edu.uci.ics.jung.algorithms.scoring.VertexScorer
getVertexScore
 

Field Detail

source_voltages

protected Map<V,? extends Number> source_voltages

sinks

protected Collection<V> sinks
Constructor Detail

VoltageScorer

public VoltageScorer(Hypergraph<V,E> g,
                     org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights,
                     Map<V,? extends Number> source_voltages,
                     Collection<V> sinks)
Creates an instance with the specified graph, edge weights, source voltages, and sinks.

Parameters:
g - the input graph
edge_weights - the edge weights, representing conductivity
source_voltages - the (fixed) voltage for each source
sinks - the vertices whose voltages are tied to 0

VoltageScorer

public VoltageScorer(Hypergraph<V,E> g,
                     org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights,
                     Collection<V> sources,
                     Collection<V> sinks)
Creates an instance with the specified graph, edge weights, source vertices (each of whose 'voltages' are tied to 1), and sinks.

Parameters:
g - the input graph
edge_weights - the edge weights, representing conductivity
sources - the vertices whose voltages are tied to 1
sinks - the vertices whose voltages are tied to 0

VoltageScorer

public VoltageScorer(Hypergraph<V,E> g,
                     Collection<V> sources,
                     Collection<V> sinks)
Creates an instance with the specified graph, source vertices (each of whose 'voltages' are tied to 1), and sinks. The outgoing edges for each vertex are assigned weights that sum to 1.

Parameters:
g - the input graph
sources - the vertices whose voltages are tied to 1
sinks - the vertices whose voltages are tied to 0

VoltageScorer

public VoltageScorer(Hypergraph<V,E> g,
                     Map<V,? extends Number> source_voltages,
                     Collection<V> sinks)
Creates an instance with the specified graph, source voltages, and sinks. The outgoing edges for each vertex are assigned weights that sum to 1.

Parameters:
g - the input graph
source_voltages - the (fixed) voltage for each source
sinks - the vertices whose voltages are tied to 0

VoltageScorer

public VoltageScorer(Hypergraph<V,E> g,
                     org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights,
                     V source,
                     V sink)
Creates an instance with the specified graph, edge weights, source, and sink. The source vertex voltage is tied to 1.

Parameters:
g - the input graph
edge_weights - the edge weights, representing conductivity
source - the vertex whose voltage is tied to 1
sink - the vertex whose voltage is tied to 0

VoltageScorer

public VoltageScorer(Hypergraph<V,E> g,
                     V source,
                     V sink)
Creates an instance with the specified graph, edge weights, source, and sink. The source vertex voltage is tied to 1. The outgoing edges for each vertex are assigned weights that sum to 1.

Parameters:
g - the input graph
source - the vertex whose voltage is tied to 1
sink - the vertex whose voltage is tied to 0
Method Detail

initialize

public void initialize()
Initializes the state of this instance.

Overrides:
initialize in class AbstractIterativeScorer<V,E,Double>

update

public double update(V v)
Description copied from class: AbstractIterativeScorer
Updates the value for v. This is the key

Specified by:
update in class AbstractIterativeScorer<V,E,Double>
Parameters:
v - the vertex whose value is to be updated
Returns:
See Also:
AbstractIterativeScorer.update(Object)


Copyright © 2009. All Rights Reserved.