Package ptolemy.graph.analysis.strategy

Class FloydWarshallAllPairShortestPathStrategy

  • All Implemented Interfaces:
    AllPairShortestPathAnalyzer, Analyzer, GraphAnalyzer
    public class FloydWarshallAllPairShortestPathStrategy
extends FloydWarshallStrategy
implements AllPairShortestPathAnalyzer
    Computation of the all pair shortest path of a directed graph using the Floyd-Warshall algorithm. The result is in the form of two dimensional array (matrix). The first dimension is indexed by the source node label while the second one is indexed by the sink node label. In graphs that have multiple edges between two nodes obviously the edge with the minimum weight is being considered for the shortest path. The distance between a node and itself is being considered Double.MAX_VALUE, unless otherwise specified by a self edge for a cyclic graph. ((double[][])result())[i][i] would be the length of the shortest cycle that includes the node with label "i".

    Since:
    Ptolemy II 4.0
    Version:
    $Id$
    Author:
    Shahrooz Shahparnia
    See Also:
    AllPairShortestPathAnalysis
    Pt.AcceptedRating:
    Red (ssb)
    Pt.ProposedRating:
    Red (shahrooz)

    • Constructor Detail

      • FloydWarshallAllPairShortestPathStrategy

        public FloydWarshallAllPairShortestPathStrategy​(Graph graph,
                                                ToDoubleMapping edgeLengths)
        Construct an AllPairShortestPathAnalyzer which works using the Floyd-Warshall strategy.
        Parameters:
        graph - The given graph.
        edgeLengths - The edge lengths.

    • Method Detail

      • shortestPath

        public java.util.List shortestPath​(Node startNode,
                                   Node endNode)
        Return the nodes on the shortest path from the node startNode to the node endNode in the form of an ordered list.
        Specified by:
        shortestPath in interface AllPairShortestPathAnalyzer
        Parameters:
        startNode - The starting node of the path.
        endNode - The ending node of the path.
        Returns:
        Return the nodes on the shortest path from the node startNode to the node endNode in the form of an ordered list.

      • shortestPathLength

        public double shortestPathLength​(Node startNode,
                                 Node endNode)
        Return the length of the shortest path from the node startNode to the node endNode.
        Specified by:
        shortestPathLength in interface AllPairShortestPathAnalyzer
        Parameters:
        startNode - The starting node of the path.
        endNode - The end node of the path.
        Returns:
        Return the length of the shortest path from the node startNode to the node endNode.

      • shortestPathMatrix

        public double[][] shortestPathMatrix()
        Return the all pair shortest path of the graph in the form of two dimensional array (matrix). The first dimension is indexed by the source node label while the second one is indexed by the sink node label. In graphs that have multiple edges between two nodes obviously the edge with the minimum weight is being considered for the shortest path. The distance between a node and itself is being considered Double.MAX_VALUE unless otherwise specified by a self edge. for a cyclic graph ((double[][])result())[i][i] would be the length of the shortest cycle that includes the node with label "i".
        Specified by:
        shortestPathMatrix in interface AllPairShortestPathAnalyzer
        Returns:
        The all pair shortest path matrix as a double[][].
        See Also:
        Graph.nodeLabel(ptolemy.graph.Node)

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

      • valid

        public boolean valid()
        Check for compatibility between the analysis and the given graph. A graph needs to be an instance of a DirectedGraph in order to use this algorithm. In addition the given object should be the same graph associated with this analyzer.
        Specified by:
        valid in interface Analyzer
        Returns:
        True if the graph is a directed graph.

      • _compute

        protected java.lang.Object _compute()
        Compute the all pair shortest path of the graph in the form of two dimensional array (matrix).
        Overrides:
        _compute in class FloydWarshallStrategy
        Returns:
        The all pair shortest path matrix as a double[][] Object.

      • _floydWarshallComputation

        protected final void _floydWarshallComputation​(int k,
                                               int i,
                                               int j)
        The FloydWarshall computation associated with this, analysis.
        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.