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$

Author:

Shahrooz Shahparnia

See Also:

AllPairShortestPathAnalysis

Pt.AcceptedRating:

Red (ssb)

Pt.ProposedRating:

Red (shahrooz)

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
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.
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

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.