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

java.lang.Object
  edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer<V,E,T>

All Implemented Interfaces:

VertexScorer<V,T>, IterativeContext

Direct Known Subclasses:

AbstractIterativeScorerWithPriors, VoltageScorer

public abstract class AbstractIterativeScorer<V,E,T>
extends Object
implements IterativeContext, VertexScorer<V,T>

An abstract class for algorithms that assign scores to vertices based on iterative methods. Generally, any (concrete) subclass will function by creating an instance, and then either calling evaluate (if the user wants to iterate until the algorithms is 'done') or repeatedly call step (if the user wants to observe the values at each step).

Field Summary

protected org.apache.commons.collections15.Transformer<VEPair<V,E>,? extends Number>	edge_weights The edge weights used by this algorithm.
protected Hypergraph<V,E>	graph The graph on which the calculations are to be made.
protected boolean	hyperedges_are_self_loops
protected double	max_delta The largest change seen so far among all vertex scores.
protected int	max_iterations Maximum number of iterations to use before terminating.
protected boolean	output_reversed Indicates whether the output and current values are in a 'swapped' state.
protected double	tolerance Minimum change from one step to the next; if all changes are <= tolerance, no further updates will occur.
protected int	total_iterations The total number of iterations used so far.

Constructor Summary

AbstractIterativeScorer(Hypergraph<V,E> g)
Creates an instance for the specified graph g.

AbstractIterativeScorer(Hypergraph<V,E> g, org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights)
Creates an instance for the specified graph and edge weights.

Method Summary

void	acceptDisconnectedGraph(boolean accept) Specifies whether this instance should accept vertices with no outgoing edges.
protected void	afterStep()
protected void	collectDisappearingPotential(V v) Collects the 'potential' from v (its current value) if it has no outgoing edges; this can then be redistributed among the other vertices as a means of normalization.
boolean	done() Returns true if the total number of iterations is greater than or equal to max_iterations or if the maximum value change observed is less than tolerance.
void	evaluate() Steps through this scoring algorithm until a termination condition is reached.
protected int	getAdjustedIncidentCount(E e) Returns the effective number of vertices incident to this edge.
protected T	getCurrentValue(V v) Gets the current value for this vertex
protected Number	getEdgeWeight(V v, E e) Gets the edge weight for e in the context of its (incident) vertex v.
org.apache.commons.collections15.Transformer<VEPair<V,E>,? extends Number>	getEdgeWeights() Returns the Transformer that this instance uses to associate edge weights with each edge.
int	getIterations() Returns the number of iterations that this instance has used so far.
int	getMaxIterations() Returns the maximum number of iterations that this instance will use.
protected T	getOutputValue(V v) Gets the output value for this vertex.
double	getTolerance() Gets the size of the largest change (difference between the current and previous values) for any vertex that can be tolerated.
T	getVertexScore(V v) Returns the algorithm's score for this vertex.
protected void	initialize() Initializes the internal state for this instance.
boolean	isDisconnectedGraphOK() Returns true if this instance accepts vertices with no outgoing edges, and false otherwise.
protected void	setCurrentValue(V v, T value) Sets the current value for this vertex.
void	setEdgeWeights(org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights) Sets the Transformer that this instance uses to associate edge weights with each edge
void	setHyperedgesAreSelfLoops(boolean arg) Specifies whether hyperedges are to be treated as self-loops.
void	setMaxIterations(int max_iterations) Sets the maximum number of times that evaluate will call step.
protected void	setOutputValue(V v, T value) Sets the output value for this vertex.
void	setTolerance(double tolerance) Sets the size of the largest change (difference between the current and previous values) for any vertex that can be tolerated.
void	step() Performs one step of this algorithm; updates the state (value) for each vertex.
protected void	swapOutputForCurrent()
protected abstract double	update(V v) Updates the value for v.
protected void	updateMaxDelta(V v, double diff)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

max_iterations

protected int max_iterations

Maximum number of iterations to use before terminating. Defaults to 100.

tolerance

protected double tolerance

Minimum change from one step to the next; if all changes are <= tolerance, no further updates will occur. Defaults to 0.001.

graph

protected Hypergraph<V,E> graph

The graph on which the calculations are to be made.

total_iterations

protected int total_iterations

The total number of iterations used so far.

edge_weights

protected org.apache.commons.collections15.Transformer<VEPair<V,E>,? extends Number> edge_weights

The edge weights used by this algorithm.

output_reversed

protected boolean output_reversed

Indicates whether the output and current values are in a 'swapped' state. Intended for internal use only.

hyperedges_are_self_loops

protected boolean hyperedges_are_self_loops

max_delta

protected double max_delta

The largest change seen so far among all vertex scores.

Constructor Detail

AbstractIterativeScorer

public AbstractIterativeScorer(Hypergraph<V,E> g,
                               org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights)

Creates an instance for the specified graph and edge weights.

Parameters:

g - the graph for which the instance is to be created

edge_weights - the edge weights for this instance

AbstractIterativeScorer

public AbstractIterativeScorer(Hypergraph<V,E> g)

Creates an instance for the specified graph g. NOTE: This constructor does not set the internal edge_weights variable. If this variable is used by the subclass which invoked this constructor, it must be initialized by that subclass.

Parameters:

g - the graph for which the instance is to be created

Method Detail

setOutputValue

protected void setOutputValue(V v,
                              T value)

Sets the output value for this vertex.

Parameters:

v - the vertex whose output value is to be set

value - the value to set

getOutputValue

protected T getOutputValue(V v)

Gets the output value for this vertex.

Parameters:

v - the vertex whose output value is to be retrieved

Returns:

the output value for this vertex

getCurrentValue

protected T getCurrentValue(V v)

Gets the current value for this vertex

Parameters:

v - the vertex whose current value is to be retrieved

Returns:

the current value for this vertex

setCurrentValue

protected void setCurrentValue(V v,
                               T value)

Sets the current value for this vertex.

Parameters:

v - the vertex whose current value is to be set

value - the current value to set

initialize

protected void initialize()

Initializes the internal state for this instance.

evaluate

public void evaluate()

Steps through this scoring algorithm until a termination condition is reached.

done

public boolean done()

Returns true if the total number of iterations is greater than or equal to max_iterations or if the maximum value change observed is less than tolerance.

Specified by:

done in interface IterativeContext

step

public void step()

Performs one step of this algorithm; updates the state (value) for each vertex.

Specified by:

step in interface IterativeContext

swapOutputForCurrent

protected void swapOutputForCurrent()

update

protected abstract double update(V v)

Updates the value for v. This is the key

Parameters:

v - the vertex whose value is to be updated

Returns:

updateMaxDelta

protected void updateMaxDelta(V v,
                              double diff)

afterStep

protected void afterStep()

getVertexScore

public T getVertexScore(V v)

Description copied from interface: VertexScorer

Returns the algorithm's score for this vertex.

Specified by:

getVertexScore in interface VertexScorer<V,T>

Returns:

the algorithm's score for this vertex

getMaxIterations

public int getMaxIterations()

Returns the maximum number of iterations that this instance will use.

Returns:

the maximum number of iterations that evaluate will use prior to terminating

getIterations

public int getIterations()

Returns the number of iterations that this instance has used so far.

Returns:

the number of iterations that this instance has used so far

setMaxIterations

public void setMaxIterations(int max_iterations)

Sets the maximum number of times that evaluate will call step.

Parameters:

max_iterations - the maximum

getTolerance

public double getTolerance()

Gets the size of the largest change (difference between the current and previous values) for any vertex that can be tolerated. Once all changes are less than this value, evaluate will terminate.

Returns:

the size of the largest change that evaluate() will permit

setTolerance

public void setTolerance(double tolerance)

Sets the size of the largest change (difference between the current and previous values) for any vertex that can be tolerated.

Parameters:

tolerance - the size of the largest change that evaluate() will permit

getEdgeWeights

public org.apache.commons.collections15.Transformer<VEPair<V,E>,? extends Number> getEdgeWeights()

Returns the Transformer that this instance uses to associate edge weights with each edge.

Returns:

the Transformer that associates an edge weight with each edge

setEdgeWeights

public void setEdgeWeights(org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights)

Sets the Transformer that this instance uses to associate edge weights with each edge

Parameters:

edge_weights - the Transformer to use to associate an edge weight with each edge

See Also:

UniformDegreeWeight

getEdgeWeight

protected Number getEdgeWeight(V v,
                               E e)

Gets the edge weight for e in the context of its (incident) vertex v.

Parameters:

v - the vertex incident to e as a context in which the edge weight is to be calculated

e - the edge whose weight is to be returned

Returns:

the edge weight for e in the context of its (incident) vertex v

collectDisappearingPotential

protected void collectDisappearingPotential(V v)

Collects the 'potential' from v (its current value) if it has no outgoing edges; this can then be redistributed among the other vertices as a means of normalization.

Parameters:

v -

acceptDisconnectedGraph

public void acceptDisconnectedGraph(boolean accept)

Specifies whether this instance should accept vertices with no outgoing edges.

Parameters:

accept - true if this instance should accept vertices with no outgoing edges, false otherwise

isDisconnectedGraphOK

public boolean isDisconnectedGraphOK()

Returns true if this instance accepts vertices with no outgoing edges, and false otherwise.

Returns:

true if this instance accepts vertices with no outgoing edges, otherwise false

setHyperedgesAreSelfLoops

public void setHyperedgesAreSelfLoops(boolean arg)

Specifies whether hyperedges are to be treated as self-loops. If they are, then potential will flow along a hyperedge a vertex to itself, just as it does to all other vertices incident to that hyperedge.

Parameters:

arg - if true, hyperedges are treated as self-loops

getAdjustedIncidentCount

protected int getAdjustedIncidentCount(E e)

Returns the effective number of vertices incident to this edge. If the graph is a binary relation or if hyperedges are treated as self-loops, the value returned is graph.getIncidentCount(e); otherwise it is graph.getIncidentCount(e) - 1.