Package ptolemy.graph.analysis

Class AllPairShortestPathAnalysis

  • public class AllPairShortestPathAnalysis
extends Analysis
    An analysis to compute of the all pair shortest path of a directed graph. 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 there is a self-edge.

    The result of shortestPathMatrix()[i][i] would be the length of the shortest cycle that includes the node with label "i".

    The default analyzer runs in O(N^3) in which N is the number of nodes.

    Since:
    Ptolemy II 4.0
    Version:
    $Id$
    Author:
    Shahrooz Shahparnia
    See Also:
    Graph.nodeLabel(ptolemy.graph.Node)
    Pt.AcceptedRating:
    Red (ssb)
    Pt.ProposedRating:
    Red (shahrooz)

    • Constructor Detail

      • AllPairShortestPathAnalysis

        public AllPairShortestPathAnalysis​(Graph graph,
                                   ToDoubleMapping edgeLength)
        Construct an instance of this class with a default analyzer. The default analyzer runs in O(N^3) where N is the number of nodes.
        Parameters:
        graph - The given graph.
        edgeLength - A mapping between the graph edges and double values, which play the role of edge costs.

      • AllPairShortestPathAnalysis

        public AllPairShortestPathAnalysis​(AllPairShortestPathAnalyzer analyzer)
        Construct an instance of this class with a given analyzer.
        Parameters:
        analyzer - The given analyzer.

    • 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.
        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.
        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 a matrix representing the result of the all pair shortest path algorithm. The first dimension is indexed by the source node label while the second one is indexed by the sink node label. The result of shortestPathMatrix()[i][i] would be the length of the shortest cycle that includes the node with label "i" and the result of shortestPathMatrix()[i][j] would be the length of the shortest from the node with label "i" to the node with label "j".
        Returns:
        Return a matrix representing the result of the all pair shortest path algorithm.

      • toString

        public java.lang.String toString()
        Return a description of the analysis and the associated analyzer.
        Overrides:
        toString in class Analysis
        Returns:
        A description of the analysis and the associated analyzer.

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