/*
* (C) Copyright 2007-2017, by France Telecom 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.alg.interfaces.*;
import org.jgrapht.graph.*;
/**
* The algorithm determines the k shortest simple paths in increasing order of weight. Weights can
* be negative (but no negative cycle is allowed), and paths can be constrained by a maximum number
* of edges. Graphs with multiple edges are allowed.
*
*
* The algorithm is a variant of the Bellman-Ford algorithm but instead of only storing the best
* path it stores the "k" best paths at each pass, yielding a complexity of O(k*n*(m^2)) where m is
* the number of edges and n is the number of vertices.
*
* @param the graph vertex type
* @param the graph edge type
*
* @author Guillaume Boulmier
* @since July 5, 2007
*/
public class KShortestPaths
implements KShortestPathAlgorithm
{
/**
* Graph on which shortest paths are searched.
*/
private Graph graph;
private int nMaxHops;
private int nPaths;
private PathValidator pathValidator;
/**
* Constructs an object to compute ranking shortest paths in a graph.
*
* @param graph graph on which shortest paths are searched
* @param k number of paths to be computed
*/
public KShortestPaths(Graph graph, int k)
{
this(graph, k, null);
}
/**
* Constructs an object to compute ranking shortest paths in a graph. A non-null path validator
* may be used to accept/deny paths according to some external logic. These validations will be
* used in addition to the basic path validations which are that the path is from start to
* target with no loops.
*
* @param graph graph on which shortest paths are searched.
* @param k number of paths to be computed.
* @param pathValidator the path validator to use
* @throws IllegalArgumentException if k is negative or 0.
*/
public KShortestPaths(Graph graph, int k, PathValidator pathValidator)
{
this(graph, k, graph.vertexSet().size() - 1, pathValidator);
}
/**
* Constructs an object to calculate ranking shortest paths in a graph.
*
* @param graph graph on which shortest paths are searched
* @param k number of ranking paths between the start vertex and an end vertex
* @param nMaxHops maximum number of edges of the calculated paths
*
* @throws IllegalArgumentException if k is negative or 0.
* @throws IllegalArgumentException if nMaxHops is negative or 0.
*/
public KShortestPaths(Graph graph, int k, int nMaxHops)
{
this(graph, k, nMaxHops, null);
}
/**
* Constructs an object to calculate ranking shortest paths in a graph. A non-null path
* validator may be used to accept/deny paths according to some external logic. These
* validations will be used in addition to the basic path validations which are that the path is
* from start to target with no loops.
*
* @param graph graph on which shortest paths are searched
* @param k number of ranking paths between the start vertex and the end vertex
* @param nMaxHops maximum number of edges of the calculated paths
* @param pathValidator the path validator to use
*
* @throws IllegalArgumentException if k is negative or 0.
* @throws IllegalArgumentException if nMaxHops is negative or 0.
*/
public KShortestPaths(Graph graph, int k, int nMaxHops, PathValidator pathValidator)
{
this.graph = Objects.requireNonNull(graph, "graph is null");
if (k <= 0) {
throw new IllegalArgumentException("Number of paths must be positive");
}
this.nMaxHops = nMaxHops;
if (nMaxHops <= 0) {
throw new IllegalArgumentException("Max number of hops must be positive");
}
this.nPaths = k;
this.pathValidator = pathValidator;
}
/**
* Returns the k shortest simple paths in increasing order of weight.
*
* @param startVertex source vertex of the calculated paths.
* @param endVertex target vertex of the calculated paths.
*
* @return list of paths between the start vertex and the end vertex
* @throws IllegalArgumentException if the graph does not contain the startVertex or the
* endVertex
* @throws IllegalArgumentException if the startVertex and the endVertex are the same vertices
*/
@Override
public List> getPaths(V startVertex, V endVertex)
{
Objects.requireNonNull(startVertex, "Start vertex cannot be null");
Objects.requireNonNull(endVertex, "End vertex cannot be null");
if (endVertex.equals(startVertex)) {
throw new IllegalArgumentException("The end vertex is the same as the start vertex!");
}
if (!graph.containsVertex(startVertex)) {
throw new IllegalArgumentException("Graph must contain the start vertex!");
}
if (!graph.containsVertex(endVertex)) {
throw new IllegalArgumentException("Graph must contain the end vertex!");
}
KShortestPathsIterator iter =
new KShortestPathsIterator<>(graph, startVertex, endVertex, nPaths, pathValidator);
// at the i-th pass the shortest paths with less (or equal) than i edges
// are calculated.
for (int passNumber = 1; (passNumber <= nMaxHops) && iter.hasNext(); passNumber++) {
iter.next();
}
List> list = iter.getPathElements(endVertex);
if (list == null) {
return Collections.emptyList();
}
List> pathList = new ArrayList<>();
for (RankingPathElement element : list) {
pathList.add(
new GraphWalk<>(
graph, startVertex, element.getVertex(), null, element.createEdgeListPath(),
element.getWeight()));
}
return pathList;
}
}
Ads help maintain this website.