Package org.jgrapht.alg
Class KShortestPaths<V,E>
- java.lang.Object
-
- org.jgrapht.alg.KShortestPaths<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
@Deprecated public class KShortestPaths<V,E> extends java.lang.Object
Deprecated.UseKShortestPaths
instead.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. Multigraphs 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.
- Since:
- July 5, 2007
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
KShortestPaths.PathWrapper
Deprecated.
-
Field Summary
Fields Modifier and Type Field Description private Graph<V,E>
graph
Deprecated.Graph on which shortest paths are searched.private int
nMaxHops
Deprecated.private int
nPaths
Deprecated.private PathValidator<V,E>
pathValidator
Deprecated.private V
startVertex
Deprecated.
-
Constructor Summary
Constructors Constructor Description KShortestPaths(Graph<V,E> graph, V startVertex, int k)
Deprecated.Creates an object to compute ranking shortest paths between the start vertex and others vertices.KShortestPaths(Graph<V,E> graph, V startVertex, int nPaths, int nMaxHops)
Deprecated.Creates an object to calculate ranking shortest paths between the start vertex and others vertices.KShortestPaths(Graph<V,E> graph, V startVertex, int nPaths, int nMaxHops, PathValidator<V,E> pathValidator)
Deprecated.Creates an object to calculate ranking shortest paths between the start vertex and others vertices.KShortestPaths(Graph<V,E> graph, V startVertex, int k, PathValidator<V,E> pathValidator)
Deprecated.Creates an object to compute ranking shortest paths between the start vertex and others vertices.
-
Method Summary
All Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description private void
assertGetPaths(V endVertex)
Deprecated.private void
assertKShortestPathsFinder(Graph<V,E> graph, V startVertex, int nPaths, int nMaxHops)
Deprecated.java.util.List<GraphPath<V,E>>
getPaths(V endVertex)
Deprecated.Returns the k shortest simple paths in increasing order of weight.
-
-
-
Constructor Detail
-
KShortestPaths
public KShortestPaths(Graph<V,E> graph, V startVertex, int k)
Deprecated.Creates an object to compute ranking shortest paths between the start vertex and others vertices.- Parameters:
graph
- graph on which shortest paths are searched.startVertex
- start vertex of the calculated paths.k
- number of paths to be computed.
-
KShortestPaths
public KShortestPaths(Graph<V,E> graph, V startVertex, int k, PathValidator<V,E> pathValidator)
Deprecated.Creates an object to compute ranking shortest paths between the start vertex and others vertices. Providing 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 - that the path is from start to target with no loops.- Parameters:
graph
- graph on which shortest paths are searched.startVertex
- start vertex of the calculated paths.k
- number of paths to be computed.pathValidator
- the path validator to use
-
KShortestPaths
public KShortestPaths(Graph<V,E> graph, V startVertex, int nPaths, int nMaxHops)
Deprecated.Creates an object to calculate ranking shortest paths between the start vertex and others vertices.- Parameters:
graph
- graph on which shortest paths are searched.startVertex
- start vertex of the calculated paths.nPaths
- number of ranking paths between the start vertex and an end vertex.nMaxHops
- maximum number of edges of the calculated paths.- Throws:
java.lang.NullPointerException
- if the specified graph or startVertex isnull
.java.lang.IllegalArgumentException
- if nPaths is negative or 0.java.lang.IllegalArgumentException
- if nMaxHops is negative or 0.
-
KShortestPaths
public KShortestPaths(Graph<V,E> graph, V startVertex, int nPaths, int nMaxHops, PathValidator<V,E> pathValidator)
Deprecated.Creates an object to calculate ranking shortest paths between the start vertex and others vertices. Providing 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 - that the path is from start to target with no loops.- Parameters:
graph
- graph on which shortest paths are searched.startVertex
- start vertex of the calculated paths.nPaths
- number of ranking paths between the start vertex and an end vertex.nMaxHops
- maximum number of edges of the calculated paths.pathValidator
- the path validator to use- Throws:
java.lang.NullPointerException
- if the specified graph or startVertex isnull
.java.lang.IllegalArgumentException
- if nPaths is negative or 0.java.lang.IllegalArgumentException
- if nMaxHops is negative or 0.
-
-
Method Detail
-
getPaths
public java.util.List<GraphPath<V,E>> getPaths(V endVertex)
Deprecated.Returns the k shortest simple paths in increasing order of weight.- Parameters:
endVertex
- target vertex of the calculated paths.- Returns:
- list of paths, or
null
if no path exists between the start vertex and the end vertex.
-
assertGetPaths
private void assertGetPaths(V endVertex)
Deprecated.
-
-