/*
 * Created on Jul 6, 2007
 *
 * Copyright (c) 2007, The JUNG Authors 
 *
 * All rights reserved.
 *
 * This software is open-source under the BSD license; see either
 * "license.txt" or
 * https://github.com/jrtom/jung/blob/master/LICENSE for a description.
 */
package edu.uci.ics.jung.algorithms.scoring;

import java.util.HashMap;
import java.util.Map;

import com.google.common.base.Function;

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 Function, ? 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, 
    		Function 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.
     * @param v the vertex whose value is to be updated
     * @return the updated value
     */
    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 Function that this instance uses to associate edge weights with each edge.
     * @return the Function that associates an edge weight with each edge
     */
    public Function, ? extends Number> getEdgeWeights()
    {
        return edge_weights;
    }

    /**
     * Sets the Function that this instance uses to associate edge weights with each edge
     * @param edge_weights the Function to use to associate an edge weight with each edge
     * @see edu.uci.ics.jung.algorithms.scoring.util.UniformDegreeWeight
     */
    public void setEdgeWeights(Function 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.apply(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 the vertex whose potential is being collected
     */
    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}.
     * @param e the edge whose incident edge count is requested
     * @return the edge count, adjusted based on how hyperedges are treated
     */
    protected int getAdjustedIncidentCount(E e) 
    {
        return graph.getIncidentCount(e) - (hyperedges_are_self_loops ? 0 : 1);
    }
}

 

Ads help maintain this website.