/*
* (C) Copyright 2009-2017, by Tom Larkworthy and Contributors.
*
* JGraphT : a free Java graph-theory library
*
* This program and the accompanying materials are dual-licensed under
* either
*
* (a) the terms of the GNU Lesser General Public License version 2.1
* as published by the Free Software Foundation, or (at your option) any
* later version.
*
* or (per the licensee's choosing)
*
* (b) the terms of the Eclipse Public License v1.0 as published by
* the Eclipse Foundation.
*/
package org.jgrapht.alg.shortestpath;
import java.util.*;
import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.util.*;
/**
* The Floyd-Warshall algorithm.
*
*
* The Floyd-Warshall algorithm
* finds all shortest paths (all n^2 of them) in O(n^3) time. It can also calculate the graph
* diameter. Note that during construction time, no computations are performed! All computations are
* performed the first time one of the member methods of this class is invoked. The results are
* stored, so all subsequent calls to the same method are computationally efficient.
*
* @param the graph vertex type
* @param the graph edge type
*
* @author Tom Larkworthy
* @author Soren Davidsen (soren@tanesha.net)
* @author Joris Kinable
* @author Dimitrios Michail
*/
public class FloydWarshallShortestPaths
extends BaseShortestPathAlgorithm
{
private final List vertices;
private final Map vertexIndices;
private int nShortestPaths = 0;
private double diameter = Double.NaN;
private double[][] d = null;
private Object[][] backtrace = null;
private Object[][] lastHopMatrix = null;
/**
* Create a new instance of the Floyd-Warshall all-pairs shortest path algorithm.
*
* @param graph the input graph
*/
public FloydWarshallShortestPaths(Graph graph)
{
super(graph);
this.vertices = new ArrayList<>(graph.vertexSet());
this.vertexIndices = new HashMap<>(this.vertices.size());
int i = 0;
for (V vertex : vertices) {
vertexIndices.put(vertex, i++);
}
}
/**
* Get the total number of shortest paths. Does not count the paths from a vertex to itself.
*
* @return total number of shortest paths
*/
public int getShortestPathsCount()
{
lazyCalculateMatrix();
return nShortestPaths;
}
/**
* Compute the diameter of the graph.
*
* @return the diameter (longest of all the shortest paths) computed for the graph. If the graph
* contains no vertices, return {@link Double#NaN}. If there is no path between any two
* vertices, return {@link Double#POSITIVE_INFINITY}.
*/
public double getDiameter()
{
lazyCalculateMatrix();
if (!Double.isNaN(diameter)) {
return diameter;
}
int n = vertices.size();
if (n > 0) {
diameter = 0.0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
diameter = Double.max(diameter, d[i][j]);
}
}
}
return diameter;
}
/**
* {@inheritDoc}
*/
@Override
public GraphPath getPath(V a, V b)
{
if (!graph.containsVertex(a)) {
throw new IllegalArgumentException("graph must contain the source vertex");
}
if (!graph.containsVertex(b)) {
throw new IllegalArgumentException("graph must contain the sink vertex");
}
lazyCalculateMatrix();
int v_a = vertexIndices.get(a);
int v_b = vertexIndices.get(b);
if (backtrace[v_a][v_b] == null) { // No path exists
return createEmptyPath(a, b);
}
// Reconstruct the path
List edges = new ArrayList<>();
V u = a;
while (!u.equals(b)) {
int v_u = vertexIndices.get(u);
E e = TypeUtil.uncheckedCast(backtrace[v_u][v_b], null);
edges.add(e);
u = Graphs.getOppositeVertex(graph, e, u);
}
return new GraphWalk<>(graph, a, b, null, edges, d[v_a][v_b]);
}
/**
* {@inheritDoc}
*/
@Override
public double getPathWeight(V source, V sink)
{
if (!graph.containsVertex(source)) {
throw new IllegalArgumentException("graph must contain the source vertex");
}
if (!graph.containsVertex(sink)) {
throw new IllegalArgumentException("graph must contain the sink vertex");
}
lazyCalculateMatrix();
return d[vertexIndices.get(source)][vertexIndices.get(sink)];
}
/**
* {@inheritDoc}
*/
@Override
public SingleSourcePaths getPaths(V source)
{
return new FloydWarshallSingleSourcePaths(source);
}
/**
* Returns the first hop, i.e., the second node on the shortest path from a to b. Lookup time is
* O(1). If the shortest path from a to b is a,c,d,e,b, this method returns c. If the next
* invocation would query the first hop on the shortest path from c to b, vertex d would be
* returned, etc. This method is computationally cheaper than calling
* {@link #getPath(Object, Object)} and then reading the first vertex.
*
* @param a source vertex
* @param b target vertex
* @return next hop on the shortest path from a to b, or null when there exists no path from a
* to b.
*/
public V getFirstHop(V a, V b)
{
lazyCalculateMatrix();
int v_a = vertexIndices.get(a);
int v_b = vertexIndices.get(b);
if (backtrace[v_a][v_b] == null) { // No path exists
return null;
} else {
E e = TypeUtil.uncheckedCast(backtrace[v_a][v_b], null);
return Graphs.getOppositeVertex(graph, e, a);
}
}
/**
* Returns the last hop, i.e., the second to last node on the shortest path from a to b. Lookup
* time is O(1). If the shortest path from a to b is a,c,d,e,b, this method returns e. If the
* next invocation would query the next hop on the shortest path from c to e, vertex d would be
* returned, etc. This method is computationally cheaper than calling
* {@link #getPath(Object, Object)} and then reading the vertex. The first invocation of this
* method populates a last hop matrix.
*
* @param a source vertex
* @param b target vertex
* @return last hop on the shortest path from a to b, or null when there exists no path from a
* to b.
*/
public V getLastHop(V a, V b)
{
lazyCalculateMatrix();
int v_a = vertexIndices.get(a);
int v_b = vertexIndices.get(b);
if (backtrace[v_a][v_b] == null) { // No path exists
return null;
} else {
populateLastHopMatrix();
E e = TypeUtil.uncheckedCast(lastHopMatrix[v_a][v_b], null);
return Graphs.getOppositeVertex(graph, e, b);
}
}
/**
* Calculates the matrix of all shortest paths, but does not populate the last hops matrix.
*/
private void lazyCalculateMatrix()
{
if (d != null) {
// already done
return;
}
int n = vertices.size();
// init the backtrace matrix
backtrace = new Object[n][n];
// initialize matrix, 0
d = new double[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(d[i], Double.POSITIVE_INFINITY);
}
// initialize matrix, 1
for (int i = 0; i < n; i++) {
d[i][i] = 0.0;
}
// initialize matrix, 2
if (graph instanceof UndirectedGraph, ?>) {
for (E edge : graph.edgeSet()) {
V source = graph.getEdgeSource(edge);
V target = graph.getEdgeTarget(edge);
if (!source.equals(target)) {
int v_1 = vertexIndices.get(source);
int v_2 = vertexIndices.get(target);
double edgeWeight = graph.getEdgeWeight(edge);
if (Double.compare(edgeWeight, d[v_1][v_2]) < 0) {
d[v_1][v_2] = d[v_2][v_1] = edgeWeight;
backtrace[v_1][v_2] = edge;
backtrace[v_2][v_1] = edge;
}
}
}
} else { // This works for both Directed and Mixed graphs! Iterating over
// the arcs and querying source/sink does not suffice for graphs
// which contain both edges and arcs
DirectedGraph directedGraph = (DirectedGraph) graph;
for (V v1 : directedGraph.vertexSet()) {
int v_1 = vertexIndices.get(v1);
for (E e : directedGraph.outgoingEdgesOf(v1)) {
V v2 = Graphs.getOppositeVertex(directedGraph, e, v1);
if (!v1.equals(v2)) {
int v_2 = vertexIndices.get(v2);
double edgeWeight = graph.getEdgeWeight(e);
if (Double.compare(edgeWeight, d[v_1][v_2]) < 0) {
d[v_1][v_2] = edgeWeight;
backtrace[v_1][v_2] = e;
}
}
}
}
}
// run fw alg
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
double ik_kj = d[i][k] + d[k][j];
if (Double.compare(ik_kj, d[i][j]) < 0) {
d[i][j] = ik_kj;
backtrace[i][j] = backtrace[i][k];
}
}
}
}
// count shortest paths
nShortestPaths = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && Double.isFinite(d[i][j])) {
nShortestPaths++;
}
}
}
}
/**
* Populate the last hop matrix, using the earlier computed backtrace matrix.
*/
private void populateLastHopMatrix()
{
lazyCalculateMatrix();
if (lastHopMatrix != null)
return;
// Initialize matrix
int n = vertices.size();
lastHopMatrix = new Object[n][n];
// Populate matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j || lastHopMatrix[i][j] != null || backtrace[i][j] == null)
continue;
// Reconstruct the path from i to j
List edges = new ArrayList<>();
V u = vertices.get(i);
V b = vertices.get(j);
while (!u.equals(b)) {
int v_u = vertexIndices.get(u);
E e = TypeUtil.uncheckedCast(backtrace[v_u][j], null);
edges.add(e);
V other = Graphs.getOppositeVertex(graph, e, u);
lastHopMatrix[i][vertexIndices.get(other)] = e;
u = other;
}
}
}
}
class FloydWarshallSingleSourcePaths
implements SingleSourcePaths
{
private V source;
public FloydWarshallSingleSourcePaths(V source)
{
this.source = source;
}
@Override
public Graph getGraph()
{
return graph;
}
@Override
public V getSourceVertex()
{
return source;
}
@Override
public double getWeight(V sink)
{
if (!graph.containsVertex(source)) {
throw new IllegalArgumentException("graph must contain the source vertex");
}
if (!graph.containsVertex(sink)) {
throw new IllegalArgumentException("graph must contain the sink vertex");
}
lazyCalculateMatrix();
return d[vertexIndices.get(source)][vertexIndices.get(sink)];
}
@Override
public GraphPath getPath(V sink)
{
if (!graph.containsVertex(source)) {
throw new IllegalArgumentException("graph must contain the source vertex");
}
if (!graph.containsVertex(sink)) {
throw new IllegalArgumentException("graph must contain the sink vertex");
}
lazyCalculateMatrix();
int v_a = vertexIndices.get(source);
int v_b = vertexIndices.get(sink);
if (backtrace[v_a][v_b] == null) { // No path exists
return createEmptyPath(source, sink);
}
// Reconstruct the path
List edges = new ArrayList<>();
V u = source;
while (!u.equals(sink)) {
int v_u = vertexIndices.get(u);
E e = TypeUtil.uncheckedCast(backtrace[v_u][v_b], null);
edges.add(e);
u = Graphs.getOppositeVertex(graph, e, u);
}
return new GraphWalk<>(graph, source, sink, null, edges, d[v_a][v_b]);
}
}
}
Ads help maintain this website.