/*
* Created on Jul 6, 2007
*
* Copyright (c) 2007, the JUNG Project and the Regents of the University
* of California
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* http://jung.sourceforge.net/license.txt for a description.
*/
package edu.uci.ics.jung.algorithms.scoring;
import java.util.HashMap;
import java.util.Map;
import org.apache.commons.collections15.Transformer;
import edu.uci.ics.jung.algorithms.scoring.util.DelegateToEdgeTransformer;
import edu.uci.ics.jung.algorithms.scoring.util.VEPair;
import edu.uci.ics.jung.algorithms.util.IterativeContext;
import edu.uci.ics.jung.graph.Hypergraph;
/**
* 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).
*/
public abstract class AbstractIterativeScorer implements IterativeContext, VertexScorer
{
/**
* Maximum number of iterations to use before terminating. Defaults to 100.
*/
protected int max_iterations;
/**
* Minimum change from one step to the next; if all changes are <= tolerance,
* no further updates will occur.
* Defaults to 0.001.
*/
protected double tolerance;
/**
* The graph on which the calculations are to be made.
*/
protected Hypergraph graph;
/**
* The total number of iterations used so far.
*/
protected int total_iterations;
/**
* The edge weights used by this algorithm.
*/
protected Transformer, ? extends Number> edge_weights;
/**
* Indicates whether the output and current values are in a 'swapped' state.
* Intended for internal use only.
*/
protected boolean output_reversed;
/**
* The map in which the output values are stored.
*/
private Map output;
/**
* The map in which the current values are stored.
*/
private Map current_values;
/**
* A flag representing whether this instance tolerates disconnected graphs.
* Instances that do not accept disconnected graphs may have unexpected behavior
* on disconnected graphs; they are not guaranteed to do an explicit check.
* Defaults to true.
*/
private boolean accept_disconnected_graph;
protected boolean hyperedges_are_self_loops = false;
/**
* Sets the output value for this vertex.
* @param v the vertex whose output value is to be set
* @param value the value to set
*/
protected void setOutputValue(V v, T value)
{
output.put(v, value);
}
/**
* Gets the output value for this vertex.
* @param v the vertex whose output value is to be retrieved
* @return the output value for this vertex
*/
protected T getOutputValue(V v)
{
return output.get(v);
}
/**
* Gets the current value for this vertex
* @param v the vertex whose current value is to be retrieved
* @return the current value for this vertex
*/
protected T getCurrentValue(V v)
{
return current_values.get(v);
}
/**
* Sets the current value for this vertex.
* @param v the vertex whose current value is to be set
* @param value the current value to set
*/
protected void setCurrentValue(V v, T value)
{
current_values.put(v, value);
}
/**
* The largest change seen so far among all vertex scores.
*/
protected double max_delta;
/**
* Creates an instance for the specified graph and edge weights.
* @param g the graph for which the instance is to be created
* @param edge_weights the edge weights for this instance
*/
public AbstractIterativeScorer(Hypergraph g, Transformer edge_weights)
{
this.graph = g;
this.max_iterations = 100;
this.tolerance = 0.001;
this.accept_disconnected_graph = true;
setEdgeWeights(edge_weights);
}
/**
* 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.
* @param g the graph for which the instance is to be created
*/
public AbstractIterativeScorer(Hypergraph g)
{
this.graph = g;
this.max_iterations = 100;
this.tolerance = 0.001;
this.accept_disconnected_graph = true;
}
/**
* Initializes the internal state for this instance.
*/
protected void initialize()
{
this.total_iterations = 0;
this.max_delta = Double.MIN_VALUE;
this.output_reversed = true;
this.current_values = new HashMap();
this.output = new HashMap();
}
/**
* Steps through this scoring algorithm until a termination condition is reached.
*/
public void evaluate()
{
do
step();
while (!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
.
*/
public boolean done()
{
return total_iterations >= max_iterations || max_delta < tolerance;
}
/**
* Performs one step of this algorithm; updates the state (value) for each vertex.
*/
public void step()
{
swapOutputForCurrent();
for (V v : graph.getVertices())
{
double diff = update(v);
updateMaxDelta(v, diff);
}
total_iterations++;
afterStep();
}
/**
*
*/
protected void swapOutputForCurrent()
{
Map tmp = output;
output = current_values;
current_values = tmp;
output_reversed = !output_reversed;
}
/**
* Updates the value for v
.
* This is the key
* @param v the vertex whose value is to be updated
* @return
*/
protected abstract double update(V v);
protected void updateMaxDelta(V v, double diff)
{
max_delta = Math.max(max_delta, diff);
}
protected void afterStep() {}
public T getVertexScore(V v)
{
if (!graph.containsVertex(v))
throw new IllegalArgumentException("Vertex " + v + " not an element of this graph");
return output.get(v);
}
/**
* Returns the maximum number of iterations that this instance will use.
* @return the maximum number of iterations that evaluate
will use
* prior to terminating
*/
public int getMaxIterations()
{
return max_iterations;
}
/**
* Returns the number of iterations that this instance has used so far.
* @return the number of iterations that this instance has used so far
*/
public int getIterations()
{
return total_iterations;
}
/**
* Sets the maximum number of times that evaluate
will call step
.
* @param max_iterations the maximum
*/
public void setMaxIterations(int max_iterations)
{
this.max_iterations = max_iterations;
}
/**
* 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.
* @return the size of the largest change that evaluate() will permit
*/
public double getTolerance()
{
return tolerance;
}
/**
* Sets the size of the largest change (difference between the current and previous values)
* for any vertex that can be tolerated.
* @param tolerance the size of the largest change that evaluate() will permit
*/
public void setTolerance(double tolerance)
{
this.tolerance = tolerance;
}
/**
* Returns the Transformer that this instance uses to associate edge weights with each edge.
* @return the Transformer that associates an edge weight with each edge
*/
public Transformer, ? extends Number> getEdgeWeights()
{
return edge_weights;
}
/**
* Sets the Transformer that this instance uses to associate edge weights with each edge
* @param edge_weights the Transformer to use to associate an edge weight with each edge
* @see edu.uci.ics.jung.algorithms.scoring.util.UniformDegreeWeight
*/
public void setEdgeWeights(Transformer edge_weights)
{
this.edge_weights = new DelegateToEdgeTransformer(edge_weights);
}
/**
* Gets the edge weight for e
in the context of its (incident) vertex v
.
* @param v the vertex incident to e as a context in which the edge weight is to be calculated
* @param e the edge whose weight is to be returned
* @return the edge weight for e
in the context of its (incident) vertex v
*/
protected Number getEdgeWeight(V v, E e)
{
return edge_weights.transform(new VEPair(v,e));
}
/**
* 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.
* @param v
*/
protected void collectDisappearingPotential(V v) {}
/**
* Specifies whether this instance should accept vertices with no outgoing edges.
* @param accept true if this instance should accept vertices with no outgoing edges, false otherwise
*/
public void acceptDisconnectedGraph(boolean accept)
{
this.accept_disconnected_graph = accept;
}
/**
* Returns true if this instance accepts vertices with no outgoing edges, and false otherwise.
* @return true if this instance accepts vertices with no outgoing edges, otherwise false
*/
public boolean isDisconnectedGraphOK()
{
return this.accept_disconnected_graph;
}
/**
* 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.
* @param arg if {@code true}, hyperedges are treated as self-loops
*/
public void setHyperedgesAreSelfLoops(boolean arg)
{
this.hyperedges_are_self_loops = arg;
}
/**
* 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 {@code graph.getIncidentCount(e)}; otherwise it is
* {@code graph.getIncidentCount(e) - 1}.
*/
protected int getAdjustedIncidentCount(E e)
{
return graph.getIncidentCount(e) - (hyperedges_are_self_loops ? 0 : 1);
}
}