Package 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$
    Author:
    Shahrooz Shahparnia
    See Also:
    Graph.nodeLabel(ptolemy.graph.Node)
    Pt.AcceptedRating:
    Red (ssb)
    Pt.ProposedRating:
    Red (shahrooz)

    • 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.