Package org.jgrapht.alg
Class FloydWarshallShortestPaths<V,E>
- java.lang.Object
-
- org.jgrapht.alg.FloydWarshallShortestPaths<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
@Deprecated public class FloydWarshallShortestPaths<V,E> extends java.lang.Object
Deprecated.In favor ofFloydWarshallShortestPaths
.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. Warning: This code has not been tested (and probably doesn't work) on multi-graphs. Code should be updated to work properly on multi-graphs.
-
-
Field Summary
Fields Modifier and Type Field Description private int[][]
backtrace
Deprecated.private double[][]
d
Deprecated.private double
diameter
Deprecated.private Graph<V,E>
graph
Deprecated.private int[][]
lastHopMatrix
Deprecated.private int
nShortestPaths
Deprecated.private java.util.Map<V,java.util.List<GraphPath<V,E>>>
paths
Deprecated.private java.util.Map<V,java.lang.Integer>
vertexIndices
Deprecated.private java.util.List<V>
vertices
Deprecated.
-
Constructor Summary
Constructors Constructor Description FloydWarshallShortestPaths(Graph<V,E> graph)
Deprecated.Create a new instance of the Floyd-Warshall all-pairs shortest path algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description double
getDiameter()
Deprecated.V
getFirstHop(V a, V b)
Deprecated.Returns the first hop, i.e., the second node on the shortest path from a to b.Graph<V,E>
getGraph()
Deprecated.V
getLastHop(V a, V b)
Deprecated.Returns the last hop, i.e., the second to last node on the shortest path from a to b.GraphPath<V,E>
getShortestPath(V a, V b)
Deprecated.Get the shortest path between two vertices.java.util.List<V>
getShortestPathAsVertexList(V a, V b)
Deprecated.Get the shortest path between two vertices as a list of vertices.java.util.List<GraphPath<V,E>>
getShortestPaths()
Deprecated.Get all shortest paths in the graph.java.util.List<GraphPath<V,E>>
getShortestPaths(V v)
Deprecated.Get shortest paths from a vertex to all other vertices in the graph.int
getShortestPathsCount()
Deprecated.private void
lazyCalculateMatrix()
Deprecated.Calculates the matrix of all shortest paths, but does not populate the paths map.private void
lazyCalculatePaths()
Deprecated.Calculate the shortest paths (not done per default) TODO: This method can be optimized.private void
populateLastHopMatrix()
Deprecated.Populate the last hop matrix, using the earlier computed backtrace matrix.double
shortestDistance(V a, V b)
Deprecated.Get the length of a shortest path.
-
-
-
Field Detail
-
vertices
private final java.util.List<V> vertices
Deprecated.
-
vertexIndices
private final java.util.Map<V,java.lang.Integer> vertexIndices
Deprecated.
-
nShortestPaths
private int nShortestPaths
Deprecated.
-
diameter
private double diameter
Deprecated.
-
d
private double[][] d
Deprecated.
-
backtrace
private int[][] backtrace
Deprecated.
-
lastHopMatrix
private int[][] lastHopMatrix
Deprecated.
-
-
Method Detail
-
getGraph
public Graph<V,E> getGraph()
Deprecated.- Returns:
- the graph on which this algorithm operates
-
getShortestPathsCount
public int getShortestPathsCount()
Deprecated.- Returns:
- total number of shortest paths
-
lazyCalculateMatrix
private void lazyCalculateMatrix()
Deprecated.Calculates the matrix of all shortest paths, but does not populate the paths map.
-
shortestDistance
public double shortestDistance(V a, V b)
Deprecated.Get the length of a shortest path.- Parameters:
a
- first vertexb
- second vertex- Returns:
- shortest distance between a and b
-
getDiameter
public double getDiameter()
Deprecated.- Returns:
- the diameter (longest of all the shortest paths) computed for the graph. If the graph is vertexless, return 0.0.
-
getShortestPath
public GraphPath<V,E> getShortestPath(V a, V b)
Deprecated.Get the shortest path between two vertices.- Parameters:
a
- from vertexb
- to vertex- Returns:
- the path, or null if none found
-
getShortestPathAsVertexList
public java.util.List<V> getShortestPathAsVertexList(V a, V b)
Deprecated.Get the shortest path between two vertices as a list of vertices.- Parameters:
a
- from vertexb
- to vertex- Returns:
- the path, or null if none found
-
getShortestPaths
public java.util.List<GraphPath<V,E>> getShortestPaths(V v)
Deprecated.Get shortest paths from a vertex to all other vertices in the graph.- Parameters:
v
- the originating vertex- Returns:
- List of paths
-
getShortestPaths
public java.util.List<GraphPath<V,E>> getShortestPaths()
Deprecated.Get all shortest paths in the graph.- Returns:
- List of paths
-
getFirstHop
public V getFirstHop(V a, V b)
Deprecated.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 getShortestPathAsVertexList(a,b).get(0);- Parameters:
a
- source vertexb
- target vertex- Returns:
- next hop on the shortest path from a to b, or null when there exists no path from a to b.
-
getLastHop
public V getLastHop(V a, V b)
Deprecated.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 getShortestPathAsVertexList(a,b).get(shortestPathListSize-1);. The first invocation of this method populates a last hop matrix.- Parameters:
a
- source vertexb
- target vertex- Returns:
- last hop on the shortest path from a to b, or null when there exists no path from a to b.
-
populateLastHopMatrix
private void populateLastHopMatrix()
Deprecated.Populate the last hop matrix, using the earlier computed backtrace matrix.
-
lazyCalculatePaths
private void lazyCalculatePaths()
Deprecated.Calculate the shortest paths (not done per default) TODO: This method can be optimized. Instead of calculating each path individidually, use a constructive method. TODO: I.e. if we have a shortest path from i to j: [i,....j] and we know that the shortest path from j to k, we can simply glue the paths together to obtain the shortest path from i to k
-
-