/*
* Created on Jul 9, 2005
*
* Copyright (c) 2005, 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.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import com.google.common.base.Function;
import com.google.common.base.Functions;
import edu.uci.ics.jung.algorithms.util.BasicMapEntry;
import edu.uci.ics.jung.algorithms.util.MapBinaryHeap;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.Hypergraph;
/**
* Calculates distances in a specified graph, using
* Dijkstra's single-source-shortest-path algorithm. All edge weights
* in the graph must be nonnegative; if any edge with negative weight is
* found in the course of calculating distances, an
* IllegalArgumentException will be thrown.
* (Note: this exception will only be thrown when such an edge would be
* used to update a given tentative distance;
* the algorithm does not check for negative-weight edges "up front".)
*
*
Distances and partial results are optionally cached (by this instance)
* for later reference. Thus, if the 10 closest vertices to a specified source
* vertex are known, calculating the 20 closest vertices does not require
* starting Dijkstra's algorithm over from scratch.
*
*
Distances are stored as double-precision values.
* If a vertex is not reachable from the specified source vertex, no
* distance is stored. This is new behavior with version 1.4;
* the previous behavior was to store a value of
* Double.POSITIVE_INFINITY. This change gives the algorithm
* an approximate complexity of O(kD log k), where k is either the number of
* requested targets or the number of reachable vertices (whichever is smaller),
* and D is the average degree of a vertex.
*
*
The elements in the maps returned by getDistanceMap
* are ordered (that is, returned
* by the iterator) by nondecreasing distance from source.
*
*
Users are cautioned that distances calculated should be assumed to
* be invalidated by changes to the graph, and should invoke reset()
* when appropriate so that the distances can be recalculated.
*
* @author Joshua O'Madadhain
* @author Tom Nelson converted to jung2
*/
public class DijkstraDistance implements Distance
{
protected Hypergraph g;
protected Function super E,? extends Number> nev;
protected Map sourceMap; // a map of source vertices to an instance of SourceData
protected boolean cached;
protected double max_distance;
protected int max_targets;
/**
* 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 DijkstraDistance(Hypergraph g, Function super E,? extends Number> nev, boolean cached) {
this.g = g;
this.nev = nev;
this.sourceMap = new HashMap();
this.cached = cached;
this.max_distance = Double.POSITIVE_INFINITY;
this.max_targets = Integer.MAX_VALUE;
}
/**
* 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 DijkstraDistance(Hypergraph g, Function super E,? extends Number> nev) {
this(g, nev, true);
}
/**
* 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 DijkstraDistance(Graph g) {
this(g, Functions.constant(1), true);
}
/**
* 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 DijkstraDistance(Graph g, boolean cached) {
this(g, Functions.constant(1), cached);
}
/**
* Implements Dijkstra's single-source shortest-path algorithm for
* weighted graphs. Uses a MapBinaryHeap as the priority queue,
* which gives this algorithm a time complexity of O(m lg n) (m = # of edges, n =
* # of vertices).
* This algorithm will terminate when any of the following have occurred (in order
* of priority):
*
* - the distance to the specified target (if any) has been found
*
- no more vertices are reachable
*
- the specified # of distances have been found, or the maximum distance
* desired has been exceeded
*
- all distances have been found
*
*
* @param source the vertex from which distances are to be measured
* @param numDests the number of distances to measure
* @param targets the set of vertices to which distances are to be measured
* @return a mapping from vertex to the shortest distance from the source to each target
*/
protected LinkedHashMap singleSourceShortestPath(V source, Collection targets, int numDests)
{
SourceData sd = getSourceData(source);
Set to_get = new HashSet();
if (targets != null) {
to_get.addAll(targets);
Set existing_dists = sd.distances.keySet();
for(V o : targets) {
if (existing_dists.contains(o))
to_get.remove(o);
}
}
// if we've exceeded the max distance or max # of distances we're willing to calculate, or
// if we already have all the distances we need,
// terminate
if (sd.reached_max ||
(targets != null && to_get.isEmpty()) ||
(sd.distances.size() >= numDests))
{
return sd.distances;
}
while (!sd.unknownVertices.isEmpty() && (sd.distances.size() < numDests || !to_get.isEmpty()))
{
Map.Entry p = sd.getNextVertex();
V v = p.getKey();
double v_dist = p.getValue().doubleValue();
to_get.remove(v);
if (v_dist > this.max_distance)
{
// we're done; put this vertex back in so that we're not including
// a distance beyond what we specified
sd.restoreVertex(v, v_dist);
sd.reached_max = true;
break;
}
sd.dist_reached = v_dist;
if (sd.distances.size() >= this.max_targets)
{
sd.reached_max = true;
break;
}
for (E e : getEdgesToCheck(v) )
{
for (V w : g.getIncidentVertices(e))
{
if (!sd.distances.containsKey(w))
{
double edge_weight = nev.apply(e).doubleValue();
if (edge_weight < 0)
throw new IllegalArgumentException("Edges weights must be non-negative");
double new_dist = v_dist + edge_weight;
if (!sd.estimatedDistances.containsKey(w))
{
sd.createRecord(w, e, new_dist);
}
else
{
double w_dist = ((Double)sd.estimatedDistances.get(w)).doubleValue();
if (new_dist < w_dist) // update tentative distance & path for w
sd.update(w, e, new_dist);
}
}
}
}
}
return sd.distances;
}
protected SourceData getSourceData(V source)
{
SourceData sd = sourceMap.get(source);
if (sd == null)
sd = new SourceData(source);
return sd;
}
/**
* Returns the set of edges incident to v that should be tested.
* By default, this is the set of outgoing edges for instances of Graph,
* the set of incident edges for instances of Hypergraph,
* and is otherwise undefined.
* @param v the vertex whose edges are to be checked
* @return the set of edges incident to {@code v} that should be tested
*/
protected Collection getEdgesToCheck(V v)
{
if (g instanceof Graph)
return ((Graph)g).getOutEdges(v);
else
return g.getIncidentEdges(v);
}
/**
* Returns the length of a shortest path from the source to the target vertex,
* or null if the target is not reachable from the source.
* If either vertex is not in the graph for which this instance
* was created, throws IllegalArgumentException.
*
* @param source the vertex from which the distance to {@code target} is to be measured
* @param target the vertex to which the distance from {@code source} is to be measured
* @return the distance between {@code source} and {@code target}
*
* @see #getDistanceMap(Object)
* @see #getDistanceMap(Object,int)
*/
public Number getDistance(V source, V target)
{
if (g.containsVertex(target) == false)
throw new IllegalArgumentException("Specified target vertex " +
target + " is not part of graph " + g);
if (g.containsVertex(source) == false)
throw new IllegalArgumentException("Specified source vertex " +
source + " is not part of graph " + g);
Set targets = new HashSet();
targets.add(target);
Map distanceMap = getDistanceMap(source, targets);
return distanceMap.get(target);
}
/**
* Returns a {@code Map} from each element {@code t} of {@code targets} to the
* shortest-path distance from {@code source} to {@code t}.
* @param source the vertex from which the distance to each target is to be measured
* @param targets the vertices to which the distance from the source is to be measured
* @return {@code Map} from each element of {@code targets} to its distance from {@code source}
*/
public Map getDistanceMap(V source, Collection targets)
{
if (g.containsVertex(source) == false)
throw new IllegalArgumentException("Specified source vertex " +
source + " is not part of graph " + g);
if (targets.size() > max_targets)
throw new IllegalArgumentException("size of target set exceeds maximum " +
"number of targets allowed: " + this.max_targets);
Map distanceMap =
singleSourceShortestPath(source, targets,
Math.min(g.getVertexCount(), max_targets));
if (!cached)
reset(source);
return distanceMap;
}
/**
* Returns a LinkedHashMap which maps each vertex
* in the graph (including the source vertex)
* to its distance from the source vertex.
* The map's iterator will return the elements in order of
* increasing distance from source.
*
*
The size of the map returned will be the number of
* vertices reachable from source.
*
* @see #getDistanceMap(Object,int)
* @see #getDistance(Object,Object)
* @param source the vertex from which distances are measured
* @return a mapping from each vertex in the graph to its distance from {@code source}
*/
public Map getDistanceMap(V source)
{
return getDistanceMap(source, Math.min(g.getVertexCount(), max_targets));
}
/**
* Returns a LinkedHashMap which maps each of the closest
* numDist vertices to the source vertex
* in the graph (including the source vertex)
* to its distance from the source 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.
*
*
The size of the map returned will be the smaller of
* numDests and the number of vertices reachable from
* source.
*
* @see #getDistanceMap(Object)
* @see #getDistance(Object,Object)
* @param source the vertex from which distances are measured
* @param numDests the number of vertices for which to measure distances
* @return a mapping from the {@code numDests} vertices in the graph
* closest to {@code source}, to their distance from {@code source}
*
*/
public LinkedHashMap getDistanceMap(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()");
if (numDests > max_targets)
throw new IllegalArgumentException("numDests must be <= the maximum " +
"number of targets allowed: " + this.max_targets);
LinkedHashMap distanceMap =
singleSourceShortestPath(source, null, numDests);
if (!cached)
reset(source);
return distanceMap;
}
/**
* Allows the user to specify the maximum distance that this instance will calculate.
* Any vertices past this distance will effectively be unreachable from the source, in
* the sense that the algorithm will not calculate the distance to any vertices which
* are farther away than this distance. A negative value for max_dist
* will ensure that no further distances are calculated.
*
* This can be useful for limiting the amount of time and space used by this algorithm
* if the graph is very large.
*
*
Note: if this instance has already calculated distances greater than max_dist,
* and the results are cached, those results will still be valid and available; this limit
* applies only to subsequent distance calculations.
*
* @param max_dist the maximum distance that this instance will calculate
*
* @see #setMaxTargets(int)
*/
public void setMaxDistance(double max_dist)
{
this.max_distance = max_dist;
for (V v : sourceMap.keySet())
{
SourceData sd = sourceMap.get(v);
sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets);
}
}
/**
* Allows the user to specify the maximum number of target vertices per source vertex
* for which this instance will calculate distances. Once this threshold is reached,
* any further vertices will effectively be unreachable from the source, in
* the sense that the algorithm will not calculate the distance to any more vertices.
* A negative value for max_targets will ensure that no further distances are calculated.
*
*
This can be useful for limiting the amount of time and space used by this algorithm
* if the graph is very large.
*
*
Note: if this instance has already calculated distances to a greater number of
* targets than max_targets, and the results are cached, those results
* will still be valid and available; this limit applies only to subsequent distance
* calculations.
*
* @param max_targets the maximum number of targets for which this instance will calculate
* distances
*
* @see #setMaxDistance(double)
*/
public void setMaxTargets(int max_targets)
{
this.max_targets = max_targets;
for (V v : sourceMap.keySet())
{
SourceData sd = sourceMap.get(v);
sd.reached_max = (this.max_distance <= sd.dist_reached) || (sd.distances.size() >= max_targets);
}
}
/**
* Clears all stored distances for this instance.
* Should be called whenever the graph is modified (edge weights
* changed or edges added/removed). If the user knows that
* some currently calculated distances are unaffected by a
* change, reset(V) may be appropriate instead.
*
* @see #reset(Object)
*/
public void reset()
{
sourceMap = new HashMap();
}
/**
* Specifies whether or not this instance of DijkstraShortestPath
* should cache its results (final and partial) for future reference.
*
* @param enable true if the results are to be cached, and
* false otherwise
*/
public void enableCaching(boolean enable)
{
this.cached = enable;
}
/**
* Clears all stored distances for the specified source vertex
* source. Should be called whenever the stored distances
* from this vertex are invalidated by changes to the graph.
*
* @param source the vertex for which stored distances should be cleared
*
* @see #reset()
*/
public void reset(V source)
{
sourceMap.put(source, null);
}
/**
* Compares according to distances, so that the BinaryHeap knows how to
* order the tree.
*/
protected static class VertexComparator implements Comparator
{
private Map distances;
protected VertexComparator(Map distances)
{
this.distances = distances;
}
public int compare(V o1, V o2)
{
return ((Double) distances.get(o1)).compareTo((Double) distances.get(o2));
}
}
/**
* 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 estimated distance)
* of the vertices for which distances are unknown.
*
* @author Joshua O'Madadhain
*/
protected class SourceData
{
protected LinkedHashMap distances;
protected Map estimatedDistances;
protected MapBinaryHeap unknownVertices;
protected boolean reached_max = false;
protected double dist_reached = 0;
protected SourceData(V source)
{
distances = new LinkedHashMap();
estimatedDistances = new HashMap();
unknownVertices = new MapBinaryHeap(new VertexComparator(estimatedDistances));
sourceMap.put(source, this);
// initialize priority queue
estimatedDistances.put(source, new Double(0)); // distance from source to itself is 0
unknownVertices.add(source);
reached_max = false;
dist_reached = 0;
}
protected Map.Entry getNextVertex()
{
V v = unknownVertices.remove();
Double dist = (Double)estimatedDistances.remove(v);
distances.put(v, dist);
return new BasicMapEntry(v, dist);
}
protected void update(V dest, E tentative_edge, double new_dist)
{
estimatedDistances.put(dest, new_dist);
unknownVertices.update(dest);
}
protected void createRecord(V w, E e, double new_dist)
{
estimatedDistances.put(w, new_dist);
unknownVertices.add(w);
}
protected void restoreVertex(V v, double dist)
{
estimatedDistances.put(v, dist);
unknownVertices.add(v);
distances.remove(v);
}
}
}
Ads help maintain this website.