ptolemy.graph.analysis

## Class TransitiveClosureAnalysis

• ```public class TransitiveClosureAnalysis
extends Analysis```
An analysis for the computation of transitive closure of a directed graph. While there is a path directed from node X to Y in the given graph, there is an edge from X to Y in the transformed graph. Generally, transitive closure is expressed in terms of square matrix with graph node labels as indices.

The `transitiveClosureMatrix()` method returns the transitive closure of the graph in the form of a 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. Matrix[i][j] is true if there is a path on the graph from "i" to "j".

Since:
Ptolemy II 2.0
Version:
\$Id: TransitiveClosureAnalysis.java 70398 2014-10-22 23:44:32Z cxh \$
Author:
Shahrooz Shahparnia
`Graph.nodeLabel(ptolemy.graph.Node)`
Accepted Rating:
 Red (ssb)
Proposed Rating:
 Red (shahrooz)
• ### Constructor Summary

Constructors
Constructor and Description
`TransitiveClosureAnalysis(Graph graph)`
Construct an instance of this class for a given graph with a default analyzer.
`TransitiveClosureAnalysis(TransitiveClosureAnalyzer analyzer)`
Construct an instance of this class with a given analyzer.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`boolean` ```pathExistence(Node startNode, Node endNode)```
Check if there exist a path between a starting node "startNode" and an ending node "endNode" on the graph under analysis.
`java.lang.String` `toString()`
Return a description of the analysis and the associated analyzer.
`boolean[][]` `transitiveClosureMatrix()`
Compute the transitive closure of the graph under analysis in the form of two dimensional array.
`boolean` `validAnalyzerInterface(Analyzer analyzer)`
Check if a given analyzer is compatible with this analysis.
• ### Methods inherited from class ptolemy.graph.analysis.Analysis

`analyzer, changeAnalyzer, graph, valid`
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait`
• ### Constructor Detail

• #### TransitiveClosureAnalysis

`public TransitiveClosureAnalysis(Graph graph)`
Construct an instance of this class for a given graph with a default analyzer. The complexity of the default algorithm is O(N^3), where N is the number of nodes.
Parameters:
`graph` - The given graph.
• #### TransitiveClosureAnalysis

`public TransitiveClosureAnalysis(TransitiveClosureAnalyzer analyzer)`
Construct an instance of this class with a given analyzer.
Parameters:
`analyzer` - The given analyzer.
• ### Method Detail

• #### pathExistence

```public boolean pathExistence(Node startNode,
Node endNode)```
Check if there exist a path between a starting node "startNode" and an ending node "endNode" on the graph under analysis.
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 analysis and the associated analyzer.
Overrides:
`toString` in class `Analysis`
Returns:
Return a description of the analysis and the associated 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.
Returns:
The transitive closure in the form of 2D array.
`Graph.nodeLabel(ptolemy.graph.Node)`
`public boolean validAnalyzerInterface(Analyzer analyzer)`
`validAnalyzerInterface` in class `Analysis`
`analyzer` - The given analyzer.