+++ /dev/null
-/*
- * Created on Jul 15, 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.Collection;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.Map;
-
-import org.apache.commons.collections15.Transformer;
-
-import edu.uci.ics.jung.algorithms.scoring.util.UniformDegreeWeight;
-import edu.uci.ics.jung.graph.Hypergraph;
-
-/**
- * Assigns scores to vertices according to their 'voltage' in an approximate
- * solution to the Kirchoff equations. This is accomplished by tying "source"
- * vertices to specified positive voltages, "sink" vertices to 0 V, and
- * iteratively updating the voltage of each other vertex to the (weighted)
- * average of the voltages of its neighbors.
- *
- * <p>The resultant voltages will all be in the range <code>[0, max]</code>
- * where <code>max</code> is the largest voltage of any source vertex (in the
- * absence of negative source voltages; see below).
- *
- * <p>A few notes about this algorithm's interpretation of the graph data:
- * <ul>
- * <li/>Higher edge weights are interpreted as indicative of greater
- * influence/effect than lower edge weights.
- * <li/>Negative edge weights (and negative "source" voltages) invalidate
- * the interpretation of the resultant values as voltages. However, this
- * algorithm will not reject graphs with negative edge weights or source voltages.
- * <li/>Parallel edges are equivalent to a single edge whose weight is the
- * sum of the weights on the parallel edges.
- * <li/>Current flows along undirected edges in both directions,
- * but only flows along directed edges in the direction of the edge.
- * </ul>
- * </p>
- */
-public class VoltageScorer<V, E> extends AbstractIterativeScorer<V, E, Double>
- implements VertexScorer<V, Double>
-{
- protected Map<V, ? extends Number> source_voltages;
- protected Collection<V> sinks;
-
- /**
- * Creates an instance with the specified graph, edge weights, source voltages,
- * and sinks.
- * @param g the input graph
- * @param edge_weights the edge weights, representing conductivity
- * @param source_voltages the (fixed) voltage for each source
- * @param sinks the vertices whose voltages are tied to 0
- */
- public VoltageScorer(Hypergraph<V, E> g, Transformer<E, ? extends Number> edge_weights,
- Map<V, ? extends Number> source_voltages, Collection<V> sinks)
- {
- super(g, edge_weights);
- this.source_voltages = source_voltages;
- this.sinks = sinks;
- initialize();
- }
-
- /**
- * Creates an instance with the specified graph, edge weights, source vertices
- * (each of whose 'voltages' are tied to 1), and sinks.
- * @param g the input graph
- * @param edge_weights the edge weights, representing conductivity
- * @param sources the vertices whose voltages are tied to 1
- * @param sinks the vertices whose voltages are tied to 0
- */
- public VoltageScorer(Hypergraph<V, E> g, Transformer<E, ? extends Number> edge_weights,
- Collection<V> sources, Collection<V> sinks)
- {
- super(g, edge_weights);
-
- Map<V, Double> unit_voltages = new HashMap<V, Double>();
- for(V v : sources)
- unit_voltages.put(v, new Double(1.0));
- this.source_voltages = unit_voltages;
- this.sinks = sinks;
- initialize();
- }
-
- /**
- * Creates an instance with the specified graph, source vertices
- * (each of whose 'voltages' are tied to 1), and sinks.
- * The outgoing edges for each vertex are assigned
- * weights that sum to 1.
- * @param g the input graph
- * @param sources the vertices whose voltages are tied to 1
- * @param sinks the vertices whose voltages are tied to 0
- */
- public VoltageScorer(Hypergraph<V, E> g, Collection<V> sources, Collection<V> sinks)
- {
- super(g);
-
- Map<V, Double> unit_voltages = new HashMap<V, Double>();
- for(V v : sources)
- unit_voltages.put(v, new Double(1.0));
- this.source_voltages = unit_voltages;
- this.sinks = sinks;
- initialize();
- }
-
- /**
- * Creates an instance with the specified graph, source voltages,
- * and sinks. The outgoing edges for each vertex are assigned
- * weights that sum to 1.
- * @param g the input graph
- * @param source_voltages the (fixed) voltage for each source
- * @param sinks the vertices whose voltages are tied to 0
- */
- public VoltageScorer(Hypergraph<V, E> g, Map<V, ? extends Number> source_voltages,
- Collection<V> sinks)
- {
- super(g);
- this.source_voltages = source_voltages;
- this.sinks = sinks;
- this.edge_weights = new UniformDegreeWeight<V,E>(g);
- initialize();
- }
-
- /**
- * Creates an instance with the specified graph, edge weights, source, and
- * sink. The source vertex voltage is tied to 1.
- * @param g the input graph
- * @param edge_weights the edge weights, representing conductivity
- * @param source the vertex whose voltage is tied to 1
- * @param sink the vertex whose voltage is tied to 0
- */
- public VoltageScorer(Hypergraph<V,E> g, Transformer<E, ? extends Number> edge_weights,
- V source, V sink)
- {
- this(g, edge_weights, Collections.singletonMap(source, 1.0), Collections.singletonList(sink));
- initialize();
- }
-
- /**
- * Creates an instance with the specified graph, edge weights, source, and
- * sink. The source vertex voltage is tied to 1.
- * The outgoing edges for each vertex are assigned
- * weights that sum to 1.
- * @param g the input graph
- * @param source the vertex whose voltage is tied to 1
- * @param sink the vertex whose voltage is tied to 0
- */
- public VoltageScorer(Hypergraph<V,E> g, V source, V sink)
- {
- this(g, Collections.singletonMap(source, 1.0), Collections.singletonList(sink));
- initialize();
- }
-
-
- /**
- * Initializes the state of this instance.
- */
- @Override
- public void initialize()
- {
- super.initialize();
-
- // sanity check
- if (source_voltages.isEmpty() || sinks.isEmpty())
- throw new IllegalArgumentException("Both sources and sinks (grounds) must be defined");
-
- if (source_voltages.size() + sinks.size() > graph.getVertexCount())
- throw new IllegalArgumentException("Source/sink sets overlap, or contain vertices not in graph");
-
- for (Map.Entry<V, ? extends Number> entry : source_voltages.entrySet())
- {
- V v = entry.getKey();
- if (sinks.contains(v))
- throw new IllegalArgumentException("Vertex " + v + " is incorrectly specified as both source and sink");
- double value = entry.getValue().doubleValue();
- if (value <= 0)
- throw new IllegalArgumentException("Source vertex " + v + " has negative voltage");
- }
-
- // set up initial voltages
- for (V v : graph.getVertices())
- {
- if (source_voltages.containsKey(v))
- setOutputValue(v, source_voltages.get(v).doubleValue());
- else
- setOutputValue(v, 0.0);
- }
- }
-
- /**
- * @see edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer#update(Object)
- */
- @Override
- public double update(V v)
- {
- // if it's a voltage source or sink, we're done
- Number source_volts = source_voltages.get(v);
- if (source_volts != null)
- {
- setOutputValue(v, source_volts.doubleValue());
- return 0.0;
- }
- if (sinks.contains(v))
- {
- setOutputValue(v, 0.0);
- return 0.0;
- }
-
- Collection<E> edges = graph.getInEdges(v);
- double voltage_sum = 0;
- double weight_sum = 0;
- for (E e: edges)
- {
- int incident_count = getAdjustedIncidentCount(e);
- for (V w : graph.getIncidentVertices(e))
- {
- if (!w.equals(v) || hyperedges_are_self_loops)
- {
- double weight = getEdgeWeight(w,e).doubleValue() / incident_count;
- voltage_sum += getCurrentValue(w).doubleValue() * weight;
- weight_sum += weight;
- }
- }
-// V w = graph.getOpposite(v, e);
-// double weight = getEdgeWeight(w,e).doubleValue();
-// voltage_sum += getCurrentValue(w).doubleValue() * weight;
-// weight_sum += weight;
- }
-
- // if either is 0, new value is 0
- if (voltage_sum == 0 || weight_sum == 0)
- {
- setOutputValue(v, 0.0);
- return getCurrentValue(v).doubleValue();
- }
-
- setOutputValue(v, voltage_sum / weight_sum);
- return Math.abs(getCurrentValue(v).doubleValue() - voltage_sum / weight_sum);
- }
-
-}
-
Code Review / controller.git / blobdiff