/*
* Copyright (c) 2003, 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.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 com.google.common.base.Function;

import edu.uci.ics.jung.graph.Graph;

/**
 * 

Calculates distances and shortest paths using Dijkstra's * single-source-shortest-path algorithm. This is a lightweight * extension of DijkstraDistance that also stores * path information, so that the shortest paths can be reconstructed. * *

The elements in the maps returned by * getIncomingEdgeMap are ordered (that is, returned * by the iterator) by nondecreasing distance from source. * * @author Joshua O'Madadhain * @author Tom Nelson converted to jung2 * @see DijkstraDistance */ public class DijkstraShortestPath extends DijkstraDistance implements ShortestPath { /** *

Creates an instance of DijkstraShortestPath for * the specified graph and the specified method of extracting weights * from edges, which caches results locally if and only if * cached is true. * * @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 g, Function nev, boolean cached) { super(g, nev, cached); } /** *

Creates an instance of DijkstraShortestPath 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 g, Function nev) { super(g, nev); } /** *

Creates an instance of DijkstraShortestPath 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 g) { super(g); } /** *

Creates an instance of DijkstraShortestPath 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 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; } /** *

Returns the last edge on a shortest path from source * to target, or null if target is not * reachable from source. * *

If either vertex is not in the graph for which this instance * was created, throws IllegalArgumentException. * * @param source the vertex where the shortest path starts * @param target the vertex where the shortest path ends * @return the last edge on a shortest path from {@code source} to {@code target} * or null if {@code target} is not reachable from {@code source} */ 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 targets = new HashSet(); targets.add(target); singleSourceShortestPath(source, targets, g.getVertexCount()); @SuppressWarnings("unchecked") Map incomingEdgeMap = ((SourcePathData)sourceMap.get(source)).incomingEdges; E incomingEdge = incomingEdgeMap.get(target); if (!cached) reset(source); return incomingEdge; } /** *

Returns a LinkedHashMap which maps each vertex * in the graph (including the source vertex) * to the last edge on the shortest path from the * source vertex. * The map's iterator will return the elements in order of * increasing distance from source. * * @see DijkstraDistance#getDistanceMap(Object,int) * @see DijkstraDistance#getDistance(Object,Object) * @param source the vertex from which distances are measured */ public Map getIncomingEdgeMap(V source) { return getIncomingEdgeMap(source, g.getVertexCount()); } /** * Returns a List of the edges on the shortest path from * source to target, in order of their * occurrence on this path. * If either vertex is not in the graph for which this instance * was created, throws IllegalArgumentException. * * @param source the starting vertex for the path to generate * @param target the ending vertex for the path to generate * @return the edges on the shortest path from {@code source} to {@code target}, * in order of their occurrence */ public List getPath(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); LinkedList path = new LinkedList(); // collect path data; must use internal method rather than // calling getIncomingEdge() because getIncomingEdge() may // wipe out results if results are not cached Set targets = new HashSet(); targets.add(target); singleSourceShortestPath(source, targets, g.getVertexCount()); @SuppressWarnings("unchecked") Map 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)g).getOpposite(current, incoming); } return path; } /** *

Returns a LinkedHashMap which maps each of the closest * numDests vertices to the source vertex * in the graph (including the source vertex) * to the incoming edge along the path from that vertex. Throws * an IllegalArgumentException if source * is not in this instance's graph, or if numDests 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 * @return a map from each of the closest {@code numDests} vertices * to the last edge on the shortest path to that vertex starting from {@code source} */ public LinkedHashMap 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); @SuppressWarnings("unchecked") LinkedHashMap 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 tentativeIncomingEdges; protected LinkedHashMap incomingEdges; protected SourcePathData(V source) { super(source); incomingEdges = new LinkedHashMap(); tentativeIncomingEdges = new HashMap(); } @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 getNextVertex() { Map.Entry 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); } } }

Ads help maintain this website.