Package com.ibm.wala.util.graph.traverse
Class FloydWarshall<T>
- java.lang.Object
-
- com.ibm.wala.util.graph.traverse.FloydWarshall<T>
-
- Type Parameters:
T
- node type in the graph
public class FloydWarshall<T> extends Object
Floyd-Warshall algorithm to compute all-pairs shortest path in graph with no negative cycles. TODO: this API should be cleaned up.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static interface
FloydWarshall.GetPath<T>
static interface
FloydWarshall.GetPaths<T>
-
Field Summary
Fields Modifier and Type Field Description protected NumberedGraph<T>
G
-
Constructor Summary
Constructors Constructor Description FloydWarshall(NumberedGraph<T> g)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description static <T> FloydWarshall.GetPath<T>
allPairsShortestPath(NumberedGraph<T> G)
int[][]
allPairsShortestPaths()
static <T> FloydWarshall.GetPaths<T>
allPairsShortestPaths(NumberedGraph<T> G)
protected int
edgeCost(int from, int to)
protected void
pathCallback(int i, int j, int k)
static <T> int[][]
shortestPathLengths(NumberedGraph<T> G)
-
-
-
Field Detail
-
G
protected final NumberedGraph<T> G
-
-
Constructor Detail
-
FloydWarshall
public FloydWarshall(NumberedGraph<T> g)
-
-
Method Detail
-
edgeCost
protected int edgeCost(int from, int to)
-
pathCallback
protected void pathCallback(int i, int j, int k)
-
allPairsShortestPaths
public int[][] allPairsShortestPaths()
-
shortestPathLengths
public static <T> int[][] shortestPathLengths(NumberedGraph<T> G)
-
allPairsShortestPath
public static <T> FloydWarshall.GetPath<T> allPairsShortestPath(NumberedGraph<T> G)
-
allPairsShortestPaths
public static <T> FloydWarshall.GetPaths<T> allPairsShortestPaths(NumberedGraph<T> G)
-
-