ptolemy.graph.analysis.strategy

## Class FloydWarshallTransitiveClosureStrategy

• All Implemented Interfaces:
Analyzer, GraphAnalyzer, TransitiveClosureAnalyzer

```public class FloydWarshallTransitiveClosureStrategy
extends FloydWarshallStrategy
implements TransitiveClosureAnalyzer```
Computation of transitive closure of a directed graph using the Floyd-Warshall algorithm described in: Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest: Introduction to Algorithms. Cambridge: MIT Press, 1990.

The complexity of this algorithm is O(N^3), where N is the number of nodes.

Since:
Ptolemy II 4.0
Version:
\$Id: FloydWarshallTransitiveClosureStrategy.java 70402 2014-10-23 00:52:20Z cxh \$
Author:
Shahrooz Shahparnia based on an initial implementation by Ming Yung Ko.
`Graph.nodeLabel(ptolemy.graph.Node)`, `TransitiveClosureAnalysis`
Accepted Rating:
 Red (ssb)
Proposed Rating:
 Red (shahrooz)
• ### Constructor Summary

Constructors
Constructor and Description
`FloydWarshallTransitiveClosureStrategy(Graph graph)`
Construct a transitive closure analysis for a given directed graph.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`protected java.lang.Object` `_compute()`
The computation associated with the Floyd-Warshall algorithm.
`protected void` ```_floydWarshallComputation(int k, int i, int j)```
Overrides the computation associated with the implementation of the Floyd-Warshall algorithm, for the purpose of computing the transitive closure.
`boolean` ```pathExistence(Node startNode, Node endNode)```
Check if there exist a path between a starting node and an ending node on the analyzer's graph.
`java.lang.String` `toString()`
Return a description of the analyzer.
`boolean[][]` `transitiveClosureMatrix()`
Compute the transitive closure of the graph under analysis in the form of two dimensional array.
`boolean` `valid()`
Check for validity of this strategy.
• ### 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

• #### FloydWarshallTransitiveClosureStrategy

`public FloydWarshallTransitiveClosureStrategy(Graph graph)`
Construct a transitive closure analysis for a given directed graph.
Parameters:
`graph` - The given directed graph.
• ### Method Detail

• #### pathExistence

```public boolean pathExistence(Node startNode,
Node endNode)```
Check if there exist a path between a starting node and an ending node on the analyzer's graph.
Specified by:
`pathExistence` in interface `TransitiveClosureAnalyzer`
Parameters:
`startNode` - The starting node.
`endNode` - The ending node.
Returns:
True if such a path exists.
• #### 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..
• #### transitiveClosureMatrix

`public boolean[][] transitiveClosureMatrix()`
Compute the transitive closure of the graph under analysis in the form of two dimensional array. The first dimension represents source node label while the second one represents sink node label. Assume i and j are labels of two nodes. transitiveClosureMatrix()[i][j] is true if there is a path on the graph from "i" to "j".
Specified by:
`transitiveClosureMatrix` in interface `TransitiveClosureAnalyzer`
Returns:
The transitive closure in the form of 2D array.
`Graph.nodeLabel(ptolemy.graph.Node)`
• #### valid

`public boolean valid()`
Check for validity of this strategy. A graph needs to be an instance of a `DirectedGraph` in order to use this algorithm.
Specified by:
`valid` in interface `Analyzer`
Returns:
True if the graph is a directed graph.
• #### _compute

`protected java.lang.Object _compute()`
The computation associated with the Floyd-Warshall algorithm.
Overrides:
`_compute` in class `FloydWarshallStrategy`
Returns:
Return the transitive closure matrix as an `Object` in order to be stored in the result-cache.
• #### _floydWarshallComputation

```protected void _floydWarshallComputation(int k,
int i,
int j)```
Overrides the computation associated with the implementation of the Floyd-Warshall algorithm, for the purpose of computing the transitive closure.
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.