ptolemy.graph.analysis
Class SingleSourceLongestPathAnalysis

java.lang.Object
  ptolemy.graph.analysis.Analysis
      ptolemy.graph.analysis.SingleSourceLongestPathAnalysis

public class SingleSourceLongestPathAnalysis
extends Analysis

An analysis to find the longest path from a single source to all the other nodes in a directed graph. In a graph with multiple edges between two nodes the one with the largest associated value is being considered for the longest path.

Since:

Ptolemy II 4.0

Version:

$Id: SingleSourceLongestPathAnalysis.java 57040 2010-01-27 20:52:32Z cxh $

Author:

Shahrooz Shahparnia

Accepted Rating:

Red (ssb)

Proposed Rating:

Red (shahrooz)

Constructor Summary

SingleSourceLongestPathAnalysis(Graph graph, Node startNode, ToDoubleMapping edgeLengths)
Construct an instance of this class with a default analyzer.

SingleSourceLongestPathAnalysis(SingleSourceLongestPathAnalyzer analyzer)
Construct an instance of this class with a given analyzer.

Method Summary

double[]	distance() Return the distance from the node "startNode" to all the other nodes in the graph.
Node	getStartNode() Return the single source-node (start node) of this analyzer.
java.util.List	path(Node endNode) Return the longest path from node "startNode" to node "endNode" in the form of an ordered list.
double	pathLength(Node endNode) Return the length of the longest path from node "startNode" to node "endNode".
void	setStartNode(Node startNode) Set the start-node of this analysis to the given node.
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

SingleSourceLongestPathAnalysis

public SingleSourceLongestPathAnalysis(Graph graph,
                                       Node startNode,
                                       ToDoubleMapping edgeLengths)

Construct an instance of this class with a default analyzer. The default analyzer runs in O(E), in which E is the number of edges.

Parameters:

graph - The given graph.

startNode - The node from which the longest path is going to be calculated.

edgeLengths - The lengths of the edges of the given graph, which are going to be used to calculated the longest path.

SingleSourceLongestPathAnalysis

public SingleSourceLongestPathAnalysis(SingleSourceLongestPathAnalyzer analyzer)

Construct an instance of this class with a given analyzer.

Parameters:

analyzer - The given analyzer.

Method Detail

distance

public double[] distance()

Return the distance from the node "startNode" to all the other nodes in the graph. The result is a double[] indexed by the destination node-label.

Returns:

Return the distance from the start node to all the other nodes in the graph.

See Also:

Graph.nodeLabel(ptolemy.graph.Node)

getStartNode

public Node getStartNode()

Return the single source-node (start node) of this analyzer.

Returns:

Return the starting node of this analyzer.

See Also:

setStartNode(Node)

path

public java.util.List path(Node endNode)

Return the longest path from node "startNode" to node "endNode" in the form of an ordered list.

Parameters:

endNode - The ending node of the path.

Returns:

The longest path from "startNode" to "endNode".

pathLength

public double pathLength(Node endNode)

Return the length of the longest path from node "startNode" to node "endNode". The source node can be set using setStartNode(ptolemy.graph.Node).

Parameters:

endNode - The ending node of the path.

Returns:

The length of the longest path.

setStartNode

public void setStartNode(Node startNode)

Set the start-node of this analysis to the given node.

Parameters:

startNode - The given node.

See Also:

getStartNode()

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.