ptolemy.graph.analysis.strategy
Class FloydWarshallAllPairShortestPathStrategy

java.lang.Object
  ptolemy.graph.analysis.strategy.Strategy
      ptolemy.graph.analysis.strategy.CachedStrategy
          ptolemy.graph.analysis.strategy.FloydWarshallStrategy
              ptolemy.graph.analysis.strategy.FloydWarshallAllPairShortestPathStrategy

All Implemented Interfaces:

AllPairShortestPathAnalyzer, Analyzer, GraphAnalyzer

public class FloydWarshallAllPairShortestPathStrategy
extends FloydWarshallStrategy
implements AllPairShortestPathAnalyzer

Computation of the all pair shortest path of a directed graph using the Floyd-Warshall algorithm. The result is in the form of two dimensional array (matrix). The first dimension is indexed by the source node label while the second one is indexed by the sink node label. In graphs that have multiple edges between two nodes obviously the edge with the minimum weight is being considered for the shortest path. The distance between a node and itself is being considered Double.MAX_VALUE, unless otherwise specified by a self edge for a cyclic graph. ((double[][])result())[i][i] would be the length of the shortest cycle that includes the node with label "i".

Since:

Ptolemy II 4.0

Version:

$Id: FloydWarshallAllPairShortestPathStrategy.java 57040 2010-01-27 20:52:32Z cxh $

Author:

Shahrooz Shahparnia

See Also:

AllPairShortestPathAnalysis

Accepted Rating:

Red (ssb)

Proposed Rating:

Red (shahrooz)

Field Summary

private double[][][]	_allPairShortestPath
private ToDoubleMapping	_edgeLengths
private int[][]	_predecessorResult
private int[][][]	_predecessors

Constructor Summary

FloydWarshallAllPairShortestPathStrategy(Graph graph, ToDoubleMapping edgeLengths)
Construct an AllPairShortestPathAnalyzer which works using the Floyd-Warshall strategy.

Method Summary

protected java.lang.Object	_compute() Compute the all pair shortest path of the graph in the form of two dimensional array (matrix).
protected void	_floydWarshallComputation(int k, int i, int j) The FloydWarshall computation associated with this, analysis.
private int[][]	predecessors() Return the node before the end node on the shortest path from a starting node to an ending node.
java.util.List	shortestPath(Node startNode, Node endNode) Return the nodes on the shortest path from the node startNode to the node endNode in the form of an ordered list.
double	shortestPathLength(Node startNode, Node endNode) Return the length of the shortest path from the node startNode to the node endNode.
double[][]	shortestPathMatrix() Return the all pair shortest path of the graph in the form of two dimensional array (matrix).
java.lang.String	toString() Return a description of the analyzer.
boolean	valid() Check for compatibility between the analysis and the given graph.

Methods inherited from class ptolemy.graph.analysis.strategy.CachedStrategy

_convertResult, _result, cachingStatus, disableCaching, enableCaching, getCachedResult, graph, obsolete, reset, setCachedResult

Methods inherited from class java.lang.Object

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

Methods inherited from interface ptolemy.graph.analysis.analyzer.GraphAnalyzer

graph

Field Detail

_edgeLengths

private ToDoubleMapping _edgeLengths

_predecessors

private int[][][] _predecessors

_predecessorResult

private int[][] _predecessorResult

_allPairShortestPath

private double[][][] _allPairShortestPath

Constructor Detail

FloydWarshallAllPairShortestPathStrategy

public FloydWarshallAllPairShortestPathStrategy(Graph graph,
                                                ToDoubleMapping edgeLengths)

Construct an AllPairShortestPathAnalyzer which works using the Floyd-Warshall strategy.

Parameters:

graph - The given graph.

edgeLengths - The edge lengths.

Method Detail

shortestPath

public java.util.List shortestPath(Node startNode,
                                   Node endNode)

Return the nodes on the shortest path from the node startNode to the node endNode in the form of an ordered list.

Specified by:

shortestPath in interface AllPairShortestPathAnalyzer

Parameters:

startNode - The starting node of the path.

endNode - The ending node of the path.

Returns:

Return the nodes on the shortest path from the node startNode to the node endNode in the form of an ordered list.

shortestPathLength

public double shortestPathLength(Node startNode,
                                 Node endNode)

Return the length of the shortest path from the node startNode to the node endNode.

Specified by:

shortestPathLength in interface AllPairShortestPathAnalyzer

Parameters:

startNode - The starting node of the path.

endNode - The end node of the path.

Returns:

Return the length of the shortest path from the node startNode to the node endNode.

shortestPathMatrix

public double[][] shortestPathMatrix()

Return the all pair shortest path of the graph in the form of two dimensional array (matrix). The first dimension is indexed by the source node label while the second one is indexed by the sink node label. In graphs that have multiple edges between two nodes obviously the edge with the minimum weight is being considered for the shortest path. The distance between a node and itself is being considered Double.MAX_VALUE unless otherwise specified by a self edge. for a cyclic graph ((double[][])result())[i][i] would be the length of the shortest cycle that includes the node with label "i".

Specified by:

shortestPathMatrix in interface AllPairShortestPathAnalyzer

Returns:

The all pair shortest path matrix as a double[][].

See Also:

Graph.nodeLabel(ptolemy.graph.Node)

toString

public java.lang.String toString()

Return a description of the analyzer.

Specified by:

toString in interface Analyzer

Overrides:

toString in class CachedStrategy

Returns:

Return a description of the analyzer..

valid

public boolean valid()

Check for compatibility between the analysis and the given graph. A graph needs to be an instance of a DirectedGraph in order to use this algorithm. In addition the given object should be the same graph associated with this analyzer.

Specified by:

valid in interface Analyzer

Returns:

True if the graph is a directed graph.

_compute

protected java.lang.Object _compute()

Compute the all pair shortest path of the graph in the form of two dimensional array (matrix).

Overrides:

_compute in class FloydWarshallStrategy

Returns:

The all pair shortest path matrix as a double[][] Object.

_floydWarshallComputation

protected final void _floydWarshallComputation(int k,
                                               int i,
                                               int j)

The FloydWarshall computation associated with this, analysis.

Overrides:

_floydWarshallComputation in class FloydWarshallStrategy

Parameters:

k - The counting parameter of the first loop of the Floyd-Warshall computation.

i - The counting parameter of the second loop of the Floyd-Warshall computation.

j - The counting parameter of the third and last loop of the Floyd-Warshall computation.

predecessors

private int[][] predecessors()

Return the node before the end node on the shortest path from a starting node to an ending node. The first dimension is indexed by the start node label while the second one is indexed by the end node label. The shortestPathMatrix() method should be called before this method in order to make the result consistent with the current state (graph, edge values, ...).

Returns:

Return the node before the end node on the shortest path from a starting node to an ending node.