ptolemy.graph.analysis
Class TransitiveClosureAnalysis

java.lang.Object
  ptolemy.graph.analysis.Analysis
      ptolemy.graph.analysis.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 57040 2010-01-27 20:52:32Z cxh $

Author:

Shahrooz Shahparnia

See Also:

Graph.nodeLabel(ptolemy.graph.Node)

Accepted Rating:

Red (ssb)

Proposed Rating:

Red (shahrooz)

Constructor Summary

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

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.

See Also:

Graph.nodeLabel(ptolemy.graph.Node)

validAnalyzerInterface

public boolean validAnalyzerInterface(Analyzer analyzer)

Check if a given analyzer is compatible with this analysis. In other words if it is possible to use it to compute the computation associated with this analysis.

Overrides:

validAnalyzerInterface in class Analysis

Parameters:

analyzer - The given analyzer.

Returns:

True if the given analyzer is valid for this analysis.