ptolemy.graph.analysis

Class AllPairShortestPathAnalysis

java.lang.Object

ptolemy.graph.analysis.Analysis

ptolemy.graph.analysis.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

Author:

Shahrooz Shahparnia

See Also:

Graph.nodeLabel(ptolemy.graph.Node)

Pt.AcceptedRating:

Red (ssb)

Pt.ProposedRating:

Red (shahrooz)

Constructor Summary

Constructors

Constructor and Description
AllPairShortestPathAnalysis(AllPairShortestPathAnalyzer analyzer) Construct an instance of this class with a given analyzer.
AllPairShortestPathAnalysis(Graph graph, ToDoubleMapping edgeLength) Construct an instance of this class with a default analyzer.

Method Summary

Modifier and Type	Method and Description
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.
double	shortestPathLength(Node startNode, Node endNode) Return the length of the shortest path from the node startNode to the node endNode.
double[][]	shortestPathMatrix() Return a matrix representing the result of the all pair shortest path algorithm.
java.lang.String	toString() Return a description of the analysis and the associated analyzer.
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

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.