+++ /dev/null
-/*
-* Copyright (c) 2003, 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.shortestpath;
-
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.LinkedHashMap;
-import java.util.LinkedList;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-import org.apache.commons.collections15.Transformer;
-
-import edu.uci.ics.jung.graph.Graph;
-
-/**
- * <p>Calculates distances and shortest paths using Dijkstra's
- * single-source-shortest-path algorithm. This is a lightweight
- * extension of <code>DijkstraDistance</code> that also stores
- * path information, so that the shortest paths can be reconstructed.</p>
- *
- * <p> The elements in the maps returned by
- * <code>getIncomingEdgeMap</code> are ordered (that is, returned
- * by the iterator) by nondecreasing distance from <code>source</code>.</p>
- *
- * @author Joshua O'Madadhain
- * @author Tom Nelson converted to jung2
- * @see DijkstraDistance
- */
-public class DijkstraShortestPath<V,E> extends DijkstraDistance<V,E> implements ShortestPath<V,E>
-{
- /**
- * <p>Creates an instance of <code>DijkstraShortestPath</code> for
- * the specified graph and the specified method of extracting weights
- * from edges, which caches results locally if and only if
- * <code>cached</code> is <code>true</code>.
- *
- * @param g the graph on which distances will be calculated
- * @param nev the class responsible for returning weights for edges
- * @param cached specifies whether the results are to be cached
- */
- public DijkstraShortestPath(Graph<V,E> g, Transformer<E, ? extends Number> nev, boolean cached)
- {
- super(g, nev, cached);
- }
-
- /**
- * <p>Creates an instance of <code>DijkstraShortestPath</code> for
- * the specified graph and the specified method of extracting weights
- * from edges, which caches results locally.
- *
- * @param g the graph on which distances will be calculated
- * @param nev the class responsible for returning weights for edges
- */
- public DijkstraShortestPath(Graph<V,E> g, Transformer<E, ? extends Number> nev)
- {
- super(g, nev);
- }
-
- /**
- * <p>Creates an instance of <code>DijkstraShortestPath</code> for
- * the specified unweighted graph (that is, all weights 1) which
- * caches results locally.
- *
- * @param g the graph on which distances will be calculated
- */
- public DijkstraShortestPath(Graph<V,E> g)
- {
- super(g);
- }
-
- /**
- * <p>Creates an instance of <code>DijkstraShortestPath</code> for
- * the specified unweighted graph (that is, all weights 1) which
- * caches results locally.
- *
- * @param g the graph on which distances will be calculated
- * @param cached specifies whether the results are to be cached
- */
- public DijkstraShortestPath(Graph<V,E> g, boolean cached)
- {
- super(g, cached);
- }
-
- @Override
- protected SourceData getSourceData(V source)
- {
- SourceData sd = sourceMap.get(source);
- if (sd == null)
- sd = new SourcePathData(source);
- return sd;
- }
-
- /**
- * <p>Returns the last edge on a shortest path from <code>source</code>
- * to <code>target</code>, or null if <code>target</code> is not
- * reachable from <code>source</code>.</p>
- *
- * <p>If either vertex is not in the graph for which this instance
- * was created, throws <code>IllegalArgumentException</code>.</p>
- */
- public E getIncomingEdge(V source, V target)
- {
- if (!g.containsVertex(source))
- throw new IllegalArgumentException("Specified source vertex " +
- source + " is not part of graph " + g);
-
- if (!g.containsVertex(target))
- throw new IllegalArgumentException("Specified target vertex " +
- target + " is not part of graph " + g);
-
- Set<V> targets = new HashSet<V>();
- targets.add(target);
- singleSourceShortestPath(source, targets, g.getVertexCount());
- Map<V,E> incomingEdgeMap =
- ((SourcePathData)sourceMap.get(source)).incomingEdges;
- E incomingEdge = incomingEdgeMap.get(target);
-
- if (!cached)
- reset(source);
-
- return incomingEdge;
- }
-
- /**
- * <p>Returns a <code>LinkedHashMap</code> which maps each vertex
- * in the graph (including the <code>source</code> vertex)
- * to the last edge on the shortest path from the
- * <code>source</code> vertex.
- * The map's iterator will return the elements in order of
- * increasing distance from <code>source</code>.</p>
- *
- * @see DijkstraDistance#getDistanceMap(Object,int)
- * @see DijkstraDistance#getDistance(Object,Object)
- * @param source the vertex from which distances are measured
- */
- public Map<V,E> getIncomingEdgeMap(V source)
- {
- return getIncomingEdgeMap(source, g.getVertexCount());
- }
-
- /**
- * Returns a <code>List</code> of the edges on the shortest path from
- * <code>source</code> to <code>target</code>, in order of their
- * occurrence on this path.
- * If either vertex is not in the graph for which this instance
- * was created, throws <code>IllegalArgumentException</code>.
- */
- private List<E> getPath(V source, V target, boolean spath)
- {
- if(!g.containsVertex(source))
- throw new IllegalArgumentException("Specified source vertex " +
- source + " is not part of graph " + g);
-
- if(!g.containsVertex(target))
- throw new IllegalArgumentException("Specified target vertex " +
- target + " is not part of graph " + g);
-
- LinkedList<E> path = new LinkedList<E>();
-
- // collect path data; must use internal method rather than
- // calling getIncomingEdge() because getIncomingEdge() may
- // wipe out results if results are not cached
- Set<V> targets = new HashSet<V>();
- targets.add(target);
- if (spath == true) {
- singleSourceShortestPath(source, targets, g.getVertexCount());
- } else {
- singleSourceMaxThroughputPath(source, targets, g.getVertexCount());
- }
- Map<V,E> incomingEdges =
- ((SourcePathData)sourceMap.get(source)).incomingEdges;
-
- if (incomingEdges.isEmpty() || incomingEdges.get(target) == null)
- return path;
- V current = target;
- while (!current.equals(source))
- {
- E incoming = incomingEdges.get(current);
- path.addFirst(incoming);
- current = ((Graph<V,E>)g).getOpposite(current, incoming);
- }
- return path;
- }
-
- /**
- * Returns a <code>List</code> of the edges on the shortest path from
- * <code>source</code> to <code>target</code>, in order of their
- * occurrence on this path.
- * If either vertex is not in the graph for which this instance
- * was created, throws <code>IllegalArgumentException</code>.
- */
- public List<E> getPath(V source, V target)
- {
-
- return getPath(source,target, true);
- }
-
- /**
- * Returns a <code>List</code> of the edges on the Max Througput Shortest
- * path from <code>source</code> to <code>target</code>, in order of their
- * their occurrence on this path.
- * Important - Transformer fn should return the appropriate edge weight
- * for this API to return the Path Correctly.
- * If either vertex is not in the graph for which this instance
- * was created, throws <code>IllegalArgumentException</code>.
- */
- public List<E> getMaxThroughputPath(V source, V target)
- {
-
- return getPath(source,target, false);
- }
-
-
- /**
- * <p>Returns a <code>LinkedHashMap</code> which maps each of the closest
- * <code>numDist</code> vertices to the <code>source</code> vertex
- * in the graph (including the <code>source</code> vertex)
- * to the incoming edge along the path from that vertex. Throws
- * an <code>IllegalArgumentException</code> if <code>source</code>
- * is not in this instance's graph, or if <code>numDests</code> is
- * either less than 1 or greater than the number of vertices in the
- * graph.
- *
- * @see #getIncomingEdgeMap(Object)
- * @see #getPath(Object,Object)
- * @param source the vertex from which distances are measured
- * @param numDests the number of vertices for which to measure distances
- */
- public LinkedHashMap<V,E> getIncomingEdgeMap(V source, int numDests)
- {
- if (g.getVertices().contains(source) == false)
- throw new IllegalArgumentException("Specified source vertex " +
- source + " is not part of graph " + g);
-
- if (numDests < 1 || numDests > g.getVertexCount())
- throw new IllegalArgumentException("numDests must be >= 1 " +
- "and <= g.numVertices()");
-
- singleSourceShortestPath(source, null, numDests);
-
- LinkedHashMap<V,E> incomingEdgeMap =
- ((SourcePathData)sourceMap.get(source)).incomingEdges;
-
- if (!cached)
- reset(source);
-
- return incomingEdgeMap;
- }
-
-
- /**
- * For a given source vertex, holds the estimated and final distances,
- * tentative and final assignments of incoming edges on the shortest path from
- * the source vertex, and a priority queue (ordered by estimaed distance)
- * of the vertices for which distances are unknown.
- *
- * @author Joshua O'Madadhain
- */
- protected class SourcePathData extends SourceData
- {
- protected Map<V,E> tentativeIncomingEdges;
- protected LinkedHashMap<V,E> incomingEdges;
-
- protected SourcePathData(V source)
- {
- super(source);
- incomingEdges = new LinkedHashMap<V,E>();
- tentativeIncomingEdges = new HashMap<V,E>();
- }
-
- @Override
- public void update(V dest, E tentative_edge, double new_dist)
- {
- super.update(dest, tentative_edge, new_dist);
- tentativeIncomingEdges.put(dest, tentative_edge);
- }
-
- @Override
- public Map.Entry<V,Number> getNextVertex()
- {
- Map.Entry<V,Number> p = super.getNextVertex();
- V v = p.getKey();
- E incoming = tentativeIncomingEdges.remove(v);
- incomingEdges.put(v, incoming);
- return p;
- }
-
- @Override
- public void restoreVertex(V v, double dist)
- {
- super.restoreVertex(v, dist);
- E incoming = incomingEdges.get(v);
- tentativeIncomingEdges.put(v, incoming);
- }
-
- @Override
- public void createRecord(V w, E e, double new_dist)
- {
- super.createRecord(w, e, new_dist);
- tentativeIncomingEdges.put(w, e);
- }
-
- }
-
-}
Code Review / controller.git / blobdiff