Class FloydWarshallTransitiveClosureStrategy

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