--- /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