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 final NumberedGraph<T>	G

Constructor Summary

Constructors

Constructor	Description
FloydWarshall(NumberedGraph<T> g)

Method Summary

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()
protected void	pathCallback(int i, int j, int k)
static <T> int[][]	shortestPathLengths(NumberedGraph<T> G)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

G

protected final NumberedGraph<T> G

Constructor Details

FloydWarshall

public FloydWarshall(NumberedGraph<T> g)

Method Details

edgeCost

protected int edgeCost()

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)