Class AbstractIterativeScorer<V,E,T>

java.lang.Object
edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer<V,E,T>
All Implemented Interfaces:
VertexScorer<V,T>, IterativeContext
Direct Known Subclasses:
AbstractIterativeScorerWithPriors, VoltageScorer
public abstract class AbstractIterativeScorer<V,E,T> extends Object implements IterativeContext, VertexScorer<V,T>
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).

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private boolean
    accept_disconnected_graph
    A flag representing whether this instance tolerates disconnected graphs.
    private Map<V,T>
    current_values
    The map in which the current values are stored.
    protected com.google.common.base.Function<VEPair<V,E>, ? extends Number>
    edge_weights
    The edge weights used by this algorithm.
    protected Hypergraph<V,E>
    graph
    The graph on which the calculations are to be made.
    protected boolean
    hyperedges_are_self_loops
     
    protected double
    max_delta
    The largest change seen so far among all vertex scores.
    protected int
    max_iterations
    Maximum number of iterations to use before terminating.
    private Map<V,T>
    output
    The map in which the output values are stored.
    protected boolean
    output_reversed
    Indicates whether the output and current values are in a 'swapped' state.
    protected double
    tolerance
    Minimum change from one step to the next; if all changes are ≤ tolerance, no further updates will occur.
    protected int
    total_iterations
    The total number of iterations used so far.

  • Constructor Summary

    Constructors
    Constructor
    Description
    AbstractIterativeScorer(Hypergraph<V,E> g)
    Creates an instance for the specified graph g.
    AbstractIterativeScorer(Hypergraph<V,E> g, com.google.common.base.Function<? super E, ? extends Number> edge_weights)
    Creates an instance for the specified graph and edge weights.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    acceptDisconnectedGraph(boolean accept)
    Specifies whether this instance should accept vertices with no outgoing edges.
    protected void
    afterStep()
     
    protected void
    collectDisappearingPotential(V v)
    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.
    boolean
    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.
    void
    evaluate()
    Steps through this scoring algorithm until a termination condition is reached.
    protected int
    getAdjustedIncidentCount(E e)
    Returns the effective number of vertices incident to this edge.
    protected T
    getCurrentValue(V v)
    Gets the current value for this vertex
    protected Number
    getEdgeWeight(V v, E e)
    Gets the edge weight for e in the context of its (incident) vertex v.
    com.google.common.base.Function<VEPair<V,E>, ? extends Number>
    getEdgeWeights()
    Returns the Function that this instance uses to associate edge weights with each edge.
    int
    getIterations()
    Returns the number of iterations that this instance has used so far.
    int
    getMaxIterations()
    Returns the maximum number of iterations that this instance will use.
    protected T
    getOutputValue(V v)
    Gets the output value for this vertex.
    double
    getTolerance()
    Gets the size of the largest change (difference between the current and previous values) for any vertex that can be tolerated.
    T
    getVertexScore(V v)
     
    protected void
    initialize()
    Initializes the internal state for this instance.
    boolean
    isDisconnectedGraphOK()
    Returns true if this instance accepts vertices with no outgoing edges, and false otherwise.
    protected void
    setCurrentValue(V v, T value)
    Sets the current value for this vertex.
    void
    setEdgeWeights(com.google.common.base.Function<? super E, ? extends Number> edge_weights)
    Sets the Function that this instance uses to associate edge weights with each edge
    void
    setHyperedgesAreSelfLoops(boolean arg)
    Specifies whether hyperedges are to be treated as self-loops.
    void
    setMaxIterations(int max_iterations)
    Sets the maximum number of times that evaluate will call step.
    protected void
    setOutputValue(V v, T value)
    Sets the output value for this vertex.
    void
    setTolerance(double tolerance)
    Sets the size of the largest change (difference between the current and previous values) for any vertex that can be tolerated.
    void
    step()
    Performs one step of this algorithm; updates the state (value) for each vertex.
    protected void
    swapOutputForCurrent()
     
    protected abstract double
    update(V v)
    Updates the value for v.
    protected void
    updateMaxDelta(V v, double diff)
     

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • max_iterations

      protected int max_iterations
      Maximum number of iterations to use before terminating. Defaults to 100.

    • tolerance

      protected double tolerance
      Minimum change from one step to the next; if all changes are ≤ tolerance, no further updates will occur. Defaults to 0.001.

    • graph

      protected Hypergraph<V,E> graph
      The graph on which the calculations are to be made.

    • total_iterations

      protected int total_iterations
      The total number of iterations used so far.

    • edge_weights

      protected com.google.common.base.Function<VEPair<V,E>, ? extends Number> edge_weights
      The edge weights used by this algorithm.

    • output_reversed

      protected boolean output_reversed
      Indicates whether the output and current values are in a 'swapped' state. Intended for internal use only.

    • output

      private Map<V,T> output
      The map in which the output values are stored.

    • current_values

      private Map<V,T> current_values
      The map in which the current values are stored.

    • accept_disconnected_graph

      private boolean accept_disconnected_graph
      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.

    • hyperedges_are_self_loops

      protected boolean hyperedges_are_self_loops

    • max_delta

      protected double max_delta
      The largest change seen so far among all vertex scores.

  • Constructor Details

    • AbstractIterativeScorer

      public AbstractIterativeScorer(Hypergraph<V,E> g, com.google.common.base.Function<? super E, ? extends Number> edge_weights)
      Creates an instance for the specified graph and edge weights.
      Parameters:
      g - the graph for which the instance is to be created
      edge_weights - the edge weights for this instance

    • AbstractIterativeScorer

      public AbstractIterativeScorer(Hypergraph<V,E> g)
      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.
      Parameters:
      g - the graph for which the instance is to be created

  • Method Details

    • setOutputValue

      protected void setOutputValue(V v, T value)
      Sets the output value for this vertex.
      Parameters:
      v - the vertex whose output value is to be set
      value - the value to set

    • getOutputValue

      protected T getOutputValue(V v)
      Gets the output value for this vertex.
      Parameters:
      v - the vertex whose output value is to be retrieved
      Returns:
      the output value for this vertex

    • getCurrentValue

      protected T getCurrentValue(V v)
      Gets the current value for this vertex
      Parameters:
      v - the vertex whose current value is to be retrieved
      Returns:
      the current value for this vertex

    • setCurrentValue

      protected void setCurrentValue(V v, T value)
      Sets the current value for this vertex.
      Parameters:
      v - the vertex whose current value is to be set
      value - the current value to set

    • initialize

      protected void initialize()
      Initializes the internal state for this instance.

    • evaluate

      public void evaluate()
      Steps through this scoring algorithm until a termination condition is reached.

    • done

      public boolean 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.
      Specified by:
      done in interface IterativeContext
      Returns:
      true if this iterative process is finished, and false otherwise.

    • step

      public void step()
      Performs one step of this algorithm; updates the state (value) for each vertex.
      Specified by:
      step in interface IterativeContext

    • swapOutputForCurrent

      protected void swapOutputForCurrent()

    • update

      protected abstract double update(V v)
      Updates the value for v.
      Parameters:
      v - the vertex whose value is to be updated
      Returns:
      the updated value

    • updateMaxDelta

      protected void updateMaxDelta(V v, double diff)

    • afterStep

      protected void afterStep()

    • getVertexScore

      public T getVertexScore(V v)
      Specified by:
      getVertexScore in interface VertexScorer<V,E>
      Parameters:
      v - the vertex whose score is requested
      Returns:
      the algorithm's score for this vertex

    • getMaxIterations

      public int getMaxIterations()
      Returns the maximum number of iterations that this instance will use.
      Returns:
      the maximum number of iterations that evaluate will use prior to terminating

    • getIterations

      public int getIterations()
      Returns the number of iterations that this instance has used so far.
      Returns:
      the number of iterations that this instance has used so far

    • setMaxIterations

      public void setMaxIterations(int max_iterations)
      Sets the maximum number of times that evaluate will call step.
      Parameters:
      max_iterations - the maximum

    • getTolerance

      public double getTolerance()
      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.
      Returns:
      the size of the largest change that evaluate() will permit

    • setTolerance

      public void setTolerance(double tolerance)
      Sets the size of the largest change (difference between the current and previous values) for any vertex that can be tolerated.
      Parameters:
      tolerance - the size of the largest change that evaluate() will permit

    • getEdgeWeights

      public com.google.common.base.Function<VEPair<V,E>, ? extends Number> getEdgeWeights()
      Returns the Function that this instance uses to associate edge weights with each edge.
      Returns:
      the Function that associates an edge weight with each edge

    • setEdgeWeights

      public void setEdgeWeights(com.google.common.base.Function<? super E, ? extends Number> edge_weights)
      Sets the Function that this instance uses to associate edge weights with each edge
      Parameters:
      edge_weights - the Function to use to associate an edge weight with each edge
      See Also:

    • getEdgeWeight

      protected Number getEdgeWeight(V v, E e)
      Gets the edge weight for e in the context of its (incident) vertex v.
      Parameters:
      v - the vertex incident to e as a context in which the edge weight is to be calculated
      e - the edge whose weight is to be returned
      Returns:
      the edge weight for e in the context of its (incident) vertex v

    • collectDisappearingPotential

      protected void collectDisappearingPotential(V v)
      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.
      Parameters:
      v - the vertex whose potential is being collected

    • acceptDisconnectedGraph

      public void acceptDisconnectedGraph(boolean accept)
      Specifies whether this instance should accept vertices with no outgoing edges.
      Parameters:
      accept - true if this instance should accept vertices with no outgoing edges, false otherwise

    • isDisconnectedGraphOK

      public boolean isDisconnectedGraphOK()
      Returns true if this instance accepts vertices with no outgoing edges, and false otherwise.
      Returns:
      true if this instance accepts vertices with no outgoing edges, otherwise false

    • setHyperedgesAreSelfLoops

      public void setHyperedgesAreSelfLoops(boolean arg)
      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.
      Parameters:
      arg - if true, hyperedges are treated as self-loops

    • getAdjustedIncidentCount

      protected int getAdjustedIncidentCount(E e)
      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 graph.getIncidentCount(e); otherwise it is graph.getIncidentCount(e) - 1.
      Parameters:
      e - the edge whose incident edge count is requested
      Returns:
      the edge count, adjusted based on how hyperedges are treated