Package ptolemy.graph.analysis.strategy

Class FloydWarshallTransitiveClosureStrategy

java.lang.Object

ptolemy.graph.analysis.strategy.CachedStrategy

ptolemy.graph.analysis.strategy.FloydWarshallStrategy

ptolemy.graph.analysis.strategy.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$

Author:

Shahrooz Shahparnia based on an initial implementation by Ming Yung Ko.

See Also:

Graph.nodeLabel(ptolemy.graph.Node), TransitiveClosureAnalysis

Pt.AcceptedRating:

Red (ssb)

Pt.ProposedRating:

Red (shahrooz)

Constructor Summary

Constructors

Constructor	Description
FloydWarshallTransitiveClosureStrategy(Graph graph)	Construct a transitive closure analysis for a given directed graph.

Method Summary

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

See Also:

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.