third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/AbstractIterativeScorer.java

   1 /*
   2  * Created on Jul 6, 2007
   3  *
   4  * Copyright (c) 2007, the JUNG Project and the Regents of the University
   5  * of California
   6  * All rights reserved.
   7  *
   8  * This software is open-source under the BSD license; see either
   9  * "license.txt" or
  10  * http://jung.sourceforge.net/license.txt for a description.
  11  */
  12 package edu.uci.ics.jung.algorithms.scoring;
  13
  14 import java.util.HashMap;
  15 import java.util.Map;
  16
  17 import org.apache.commons.collections15.Transformer;
  18
  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;
  23
  24 /**
  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).
  29  */
  30 public abstract class AbstractIterativeScorer<V,E,T> implements IterativeContext, VertexScorer<V,T>
  31 {
  32     /**
  33      * Maximum number of iterations to use before terminating.  Defaults to 100.
  34      */
  35     protected int max_iterations;
  36
  37     /**
  38      * Minimum change from one step to the next; if all changes are <= tolerance,
  39      * no further updates will occur.
  40      * Defaults to 0.001.
  41      */
  42     protected double tolerance;
  43
  44     /**
  45      * The graph on which the calculations are to be made.
  46      */
  47     protected Hypergraph<V,E> graph;
  48
  49     /**
  50      * The total number of iterations used so far.
  51      */
  52     protected int total_iterations;
  53
  54     /**
  55      * The edge weights used by this algorithm.
  56      */
  57     protected Transformer<VEPair<V,E>, ? extends Number> edge_weights;
  58
  59     /**
  60      * Indicates whether the output and current values are in a 'swapped' state.
  61      * Intended for internal use only.
  62      */
  63     protected boolean output_reversed;
  64
  65     /**
  66      * The map in which the output values are stored.
  67      */
  68     private Map<V, T> output;
  69
  70     /**
  71      * The map in which the current values are stored.
  72      */
  73     private Map<V, T> current_values;
  74
  75     /**
  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.
  79      * Defaults to true.
  80      */
  81     private boolean accept_disconnected_graph;
  82
  83
  84     protected boolean hyperedges_are_self_loops = false;
  85
  86     /**
  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
  90      */
  91     protected void setOutputValue(V v, T value)
  92     {
  93         output.put(v, value);
  94     }
  95
  96     /**
  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
 100      */
 101     protected T getOutputValue(V v)
 102     {
 103         return output.get(v);
 104     }
 105
 106     /**
 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
 110      */
 111     protected T getCurrentValue(V v)
 112     {
 113         return current_values.get(v);
 114     }
 115
 116     /**
 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
 120      */
 121     protected void setCurrentValue(V v, T value)
 122     {
 123         current_values.put(v, value);
 124     }
 125
 126     /**
 127      * The largest change seen so far among all vertex scores.
 128      */
 129     protected double max_delta;
 130
 131     /**
 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
 135      */
 136     public AbstractIterativeScorer(Hypergraph<V,E> g, Transformer<E, ? extends Number> edge_weights)
 137     {
 138         this.graph = g;
 139         this.max_iterations = 100;
 140         this.tolerance = 0.001;
 141         this.accept_disconnected_graph = true;
 142         setEdgeWeights(edge_weights);
 143     }
 144
 145     /**
 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
 150      * by that subclass.
 151      * @param g the graph for which the instance is to be created
 152      */
 153     public AbstractIterativeScorer(Hypergraph<V,E> g)
 154     {
 155         this.graph = g;
 156         this.max_iterations = 100;
 157         this.tolerance = 0.001;
 158         this.accept_disconnected_graph = true;
 159     }
 160
 161     /**
 162      * Initializes the internal state for this instance.
 163      */
 164     protected void initialize()
 165     {
 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>();
 171     }
 172
 173     /**
 174      * Steps through this scoring algorithm until a termination condition is reached.
 175      */
 176     public void evaluate()
 177     {
 178         do
 179             step();
 180         while (!done());
 181     }
 182
 183     /**
 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>.
 187      */
 188     public boolean done()
 189     {
 190         return total_iterations >= max_iterations || max_delta < tolerance;
 191     }
 192
 193     /**
 194      * Performs one step of this algorithm; updates the state (value) for each vertex.
 195      */
 196     public void step()
 197     {
 198         swapOutputForCurrent();
 199
 200         for (V v : graph.getVertices())
 201         {
 202             double diff = update(v);
 203             updateMaxDelta(v, diff);
 204         }
 205         total_iterations++;
 206         afterStep();
 207     }
 208
 209     /**
 210      *
 211      */
 212     protected void swapOutputForCurrent()
 213     {
 214         Map<V, T> tmp = output;
 215         output = current_values;
 216         current_values = tmp;
 217         output_reversed = !output_reversed;
 218     }
 219
 220     /**
 221      * Updates the value for <code>v</code>.
 222      * This is the key
 223      * @param v the vertex whose value is to be updated
 224      * @return
 225      */
 226     protected abstract double update(V v);
 227
 228     protected void updateMaxDelta(V v, double diff)
 229     {
 230         max_delta = Math.max(max_delta, diff);
 231     }
 232
 233     protected void afterStep() {}
 234
 235     public T getVertexScore(V v)
 236     {
 237         if (!graph.containsVertex(v))
 238             throw new IllegalArgumentException("Vertex " + v + " not an element of this graph");
 239
 240         return output.get(v);
 241     }
 242
 243     /**
 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
 247      */
 248     public int getMaxIterations()
 249     {
 250         return max_iterations;
 251     }
 252
 253     /**
 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
 256      */
 257     public int getIterations()
 258     {
 259         return total_iterations;
 260     }
 261
 262     /**
 263      * Sets the maximum number of times that <code>evaluate</code> will call <code>step</code>.
 264      * @param max_iterations the maximum
 265      */
 266     public void setMaxIterations(int max_iterations)
 267     {
 268         this.max_iterations = max_iterations;
 269     }
 270
 271     /**
 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
 276      */
 277     public double getTolerance()
 278     {
 279         return tolerance;
 280     }
 281
 282     /**
 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
 286      */
 287     public void setTolerance(double tolerance)
 288     {
 289         this.tolerance = tolerance;
 290     }
 291
 292     /**
 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
 295      */
 296     public Transformer<VEPair<V,E>, ? extends Number> getEdgeWeights()
 297     {
 298         return edge_weights;
 299     }
 300
 301     /**
 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
 305      */
 306     public void setEdgeWeights(Transformer<E, ? extends Number> edge_weights)
 307     {
 308         this.edge_weights = new DelegateToEdgeTransformer<V,E>(edge_weights);
 309     }
 310
 311     /**
 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>
 316      */
 317     protected Number getEdgeWeight(V v, E e)
 318     {
 319         return edge_weights.transform(new VEPair<V,E>(v,e));
 320     }
 321
 322     /**
 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.
 325      * @param v
 326      */
 327     protected void collectDisappearingPotential(V v) {}
 328
 329     /**
 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
 332      */
 333     public void acceptDisconnectedGraph(boolean accept)
 334     {
 335         this.accept_disconnected_graph = accept;
 336     }
 337
 338     /**
 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
 341      */
 342     public boolean isDisconnectedGraphOK()
 343     {
 344         return this.accept_disconnected_graph;
 345     }
 346
 347     /**
 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
 352      */
 353     public void setHyperedgesAreSelfLoops(boolean arg)
 354     {
 355         this.hyperedges_are_self_loops = arg;
 356     }
 357
 358     /**
 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}.
 363      */
 364     protected int getAdjustedIncidentCount(E e)
 365     {
 366         return graph.getIncidentCount(e) - (hyperedges_are_self_loops ? 0 : 1);
 367     }
 368 }