--- /dev/null
+/*
+ * 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
+ * <code>evaluate</code> (if the user wants to iterate until the algorithms is 'done') or
+ * repeatedly call <code>step</code> (if the user wants to observe the values at each step).
+ */
+public abstract class AbstractIterativeScorer<V,E,T> implements IterativeContext, VertexScorer<V,T>
+{
+ /**
+ * 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<V,E> graph;
+
+ /**
+ * The total number of iterations used so far.
+ */
+ protected int total_iterations;
+
+ /**
+ * The edge weights used by this algorithm.
+ */
+ protected Transformer<VEPair<V,E>, ? 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<V, T> output;
+
+ /**
+ * The map in which the current values are stored.
+ */
+ private Map<V, T> 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<V,E> g, Transformer<E, ? extends Number> 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 <code>g</code>.
+ * NOTE: This constructor does not set the internal
+ * <code>edge_weights</code> 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<V,E> 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<V, T>();
+ this.output = new HashMap<V, T>();
+ }
+
+ /**
+ * 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
+ * <code>max_iterations</code>
+ * or if the maximum value change observed is less than <code>tolerance</code>.
+ */
+ 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<V, T> tmp = output;
+ output = current_values;
+ current_values = tmp;
+ output_reversed = !output_reversed;
+ }
+
+ /**
+ * Updates the value for <code>v</code>.
+ * 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 <code>evaluate</code> 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 <code>evaluate</code> will call <code>step</code>.
+ * @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,
+ * <code>evaluate</code> 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<VEPair<V,E>, ? 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<E, ? extends Number> edge_weights)
+ {
+ this.edge_weights = new DelegateToEdgeTransformer<V,E>(edge_weights);
+ }
+
+ /**
+ * Gets the edge weight for <code>e</code> in the context of its (incident) vertex <code>v</code>.
+ * @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 <code>e</code> in the context of its (incident) vertex <code>v</code>
+ */
+ protected Number getEdgeWeight(V v, E e)
+ {
+ return edge_weights.transform(new VEPair<V,E>(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);
+ }
+}
Code Review / controller.git / blobdiff