2 * Created on Jul 6, 2007
4 * Copyright (c) 2007, the JUNG Project and the Regents of the University
8 * This software is open-source under the BSD license; see either
10 * http://jung.sourceforge.net/license.txt for a description.
12 package edu.uci.ics.jung.algorithms.scoring;
14 import java.util.HashMap;
17 import org.apache.commons.collections15.Transformer;
19 import edu.uci.ics.jung.algorithms.scoring.util.DelegateToEdgeTransformer;
20 import edu.uci.ics.jung.algorithms.scoring.util.VEPair;
21 import edu.uci.ics.jung.algorithms.util.IterativeContext;
22 import edu.uci.ics.jung.graph.Hypergraph;
25 * An abstract class for algorithms that assign scores to vertices based on iterative methods.
26 * Generally, any (concrete) subclass will function by creating an instance, and then either calling
27 * <code>evaluate</code> (if the user wants to iterate until the algorithms is 'done') or
28 * repeatedly call <code>step</code> (if the user wants to observe the values at each step).
30 public abstract class AbstractIterativeScorer<V,E,T> implements IterativeContext, VertexScorer<V,T>
33 * Maximum number of iterations to use before terminating. Defaults to 100.
35 protected int max_iterations;
38 * Minimum change from one step to the next; if all changes are <= tolerance,
39 * no further updates will occur.
42 protected double tolerance;
45 * The graph on which the calculations are to be made.
47 protected Hypergraph<V,E> graph;
50 * The total number of iterations used so far.
52 protected int total_iterations;
55 * The edge weights used by this algorithm.
57 protected Transformer<VEPair<V,E>, ? extends Number> edge_weights;
60 * Indicates whether the output and current values are in a 'swapped' state.
61 * Intended for internal use only.
63 protected boolean output_reversed;
66 * The map in which the output values are stored.
68 private Map<V, T> output;
71 * The map in which the current values are stored.
73 private Map<V, T> current_values;
76 * A flag representing whether this instance tolerates disconnected graphs.
77 * Instances that do not accept disconnected graphs may have unexpected behavior
78 * on disconnected graphs; they are not guaranteed to do an explicit check.
81 private boolean accept_disconnected_graph;
84 protected boolean hyperedges_are_self_loops = false;
87 * Sets the output value for this vertex.
88 * @param v the vertex whose output value is to be set
89 * @param value the value to set
91 protected void setOutputValue(V v, T value)
97 * Gets the output value for this vertex.
98 * @param v the vertex whose output value is to be retrieved
99 * @return the output value for this vertex
101 protected T getOutputValue(V v)
103 return output.get(v);
107 * Gets the current value for this vertex
108 * @param v the vertex whose current value is to be retrieved
109 * @return the current value for this vertex
111 protected T getCurrentValue(V v)
113 return current_values.get(v);
117 * Sets the current value for this vertex.
118 * @param v the vertex whose current value is to be set
119 * @param value the current value to set
121 protected void setCurrentValue(V v, T value)
123 current_values.put(v, value);
127 * The largest change seen so far among all vertex scores.
129 protected double max_delta;
132 * Creates an instance for the specified graph and edge weights.
133 * @param g the graph for which the instance is to be created
134 * @param edge_weights the edge weights for this instance
136 public AbstractIterativeScorer(Hypergraph<V,E> g, Transformer<E, ? extends Number> edge_weights)
139 this.max_iterations = 100;
140 this.tolerance = 0.001;
141 this.accept_disconnected_graph = true;
142 setEdgeWeights(edge_weights);
146 * Creates an instance for the specified graph <code>g</code>.
147 * NOTE: This constructor does not set the internal
148 * <code>edge_weights</code> variable. If this variable is used by
149 * the subclass which invoked this constructor, it must be initialized
151 * @param g the graph for which the instance is to be created
153 public AbstractIterativeScorer(Hypergraph<V,E> g)
156 this.max_iterations = 100;
157 this.tolerance = 0.001;
158 this.accept_disconnected_graph = true;
162 * Initializes the internal state for this instance.
164 protected void initialize()
166 this.total_iterations = 0;
167 this.max_delta = Double.MIN_VALUE;
168 this.output_reversed = true;
169 this.current_values = new HashMap<V, T>();
170 this.output = new HashMap<V, T>();
174 * Steps through this scoring algorithm until a termination condition is reached.
176 public void evaluate()
184 * Returns true if the total number of iterations is greater than or equal to
185 * <code>max_iterations</code>
186 * or if the maximum value change observed is less than <code>tolerance</code>.
188 public boolean done()
190 return total_iterations >= max_iterations || max_delta < tolerance;
194 * Performs one step of this algorithm; updates the state (value) for each vertex.
198 swapOutputForCurrent();
200 for (V v : graph.getVertices())
202 double diff = update(v);
203 updateMaxDelta(v, diff);
212 protected void swapOutputForCurrent()
214 Map<V, T> tmp = output;
215 output = current_values;
216 current_values = tmp;
217 output_reversed = !output_reversed;
221 * Updates the value for <code>v</code>.
223 * @param v the vertex whose value is to be updated
226 protected abstract double update(V v);
228 protected void updateMaxDelta(V v, double diff)
230 max_delta = Math.max(max_delta, diff);
233 protected void afterStep() {}
235 public T getVertexScore(V v)
237 if (!graph.containsVertex(v))
238 throw new IllegalArgumentException("Vertex " + v + " not an element of this graph");
240 return output.get(v);
244 * Returns the maximum number of iterations that this instance will use.
245 * @return the maximum number of iterations that <code>evaluate</code> will use
246 * prior to terminating
248 public int getMaxIterations()
250 return max_iterations;
254 * Returns the number of iterations that this instance has used so far.
255 * @return the number of iterations that this instance has used so far
257 public int getIterations()
259 return total_iterations;
263 * Sets the maximum number of times that <code>evaluate</code> will call <code>step</code>.
264 * @param max_iterations the maximum
266 public void setMaxIterations(int max_iterations)
268 this.max_iterations = max_iterations;
272 * Gets the size of the largest change (difference between the current and previous values)
273 * for any vertex that can be tolerated. Once all changes are less than this value,
274 * <code>evaluate</code> will terminate.
275 * @return the size of the largest change that evaluate() will permit
277 public double getTolerance()
283 * Sets the size of the largest change (difference between the current and previous values)
284 * for any vertex that can be tolerated.
285 * @param tolerance the size of the largest change that evaluate() will permit
287 public void setTolerance(double tolerance)
289 this.tolerance = tolerance;
293 * Returns the Transformer that this instance uses to associate edge weights with each edge.
294 * @return the Transformer that associates an edge weight with each edge
296 public Transformer<VEPair<V,E>, ? extends Number> getEdgeWeights()
302 * Sets the Transformer that this instance uses to associate edge weights with each edge
303 * @param edge_weights the Transformer to use to associate an edge weight with each edge
304 * @see edu.uci.ics.jung.algorithms.scoring.util.UniformDegreeWeight
306 public void setEdgeWeights(Transformer<E, ? extends Number> edge_weights)
308 this.edge_weights = new DelegateToEdgeTransformer<V,E>(edge_weights);
312 * Gets the edge weight for <code>e</code> in the context of its (incident) vertex <code>v</code>.
313 * @param v the vertex incident to e as a context in which the edge weight is to be calculated
314 * @param e the edge whose weight is to be returned
315 * @return the edge weight for <code>e</code> in the context of its (incident) vertex <code>v</code>
317 protected Number getEdgeWeight(V v, E e)
319 return edge_weights.transform(new VEPair<V,E>(v,e));
323 * Collects the 'potential' from v (its current value) if it has no outgoing edges; this
324 * can then be redistributed among the other vertices as a means of normalization.
327 protected void collectDisappearingPotential(V v) {}
330 * Specifies whether this instance should accept vertices with no outgoing edges.
331 * @param accept true if this instance should accept vertices with no outgoing edges, false otherwise
333 public void acceptDisconnectedGraph(boolean accept)
335 this.accept_disconnected_graph = accept;
339 * Returns true if this instance accepts vertices with no outgoing edges, and false otherwise.
340 * @return true if this instance accepts vertices with no outgoing edges, otherwise false
342 public boolean isDisconnectedGraphOK()
344 return this.accept_disconnected_graph;
348 * Specifies whether hyperedges are to be treated as self-loops. If they
349 * are, then potential will flow along a hyperedge a vertex to itself,
350 * just as it does to all other vertices incident to that hyperedge.
351 * @param arg if {@code true}, hyperedges are treated as self-loops
353 public void setHyperedgesAreSelfLoops(boolean arg)
355 this.hyperedges_are_self_loops = arg;
359 * Returns the effective number of vertices incident to this edge. If
360 * the graph is a binary relation or if hyperedges are treated as self-loops,
361 * the value returned is {@code graph.getIncidentCount(e)}; otherwise it is
362 * {@code graph.getIncidentCount(e) - 1}.
364 protected int getAdjustedIncidentCount(E e)
366 return graph.getIncidentCount(e) - (hyperedges_are_self_loops ? 0 : 1);