ptolemy.graph.analysis.strategy
Class AllEdgeSingleSourceLongestPathStrategy

java.lang.Object
  ptolemy.graph.analysis.strategy.Strategy
      ptolemy.graph.analysis.strategy.CachedStrategy
          ptolemy.graph.analysis.strategy.AllEdgeSingleSourceLongestPathStrategy

All Implemented Interfaces:

Analyzer, GraphAnalyzer, SingleSourceLongestPathAnalyzer

public class AllEdgeSingleSourceLongestPathStrategy
extends CachedStrategy
implements SingleSourceLongestPathAnalyzer

An analyzer used to find the longest path from a single source.

This algorithm runs in O(E), in which E is the number of edges.

Since:

Ptolemy II 4.0

Version:

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

Author:

Shahrooz Shahparnia

See Also:

SingleSourceLongestPathAnalysis

Accepted Rating:

Red (ssb)

Proposed Rating:

Red (shahrooz)

Field Summary

private ToDoubleMapping	_edgeLengths
private int[]	_predecessor
private Node	_startNode

Constructor Summary

AllEdgeSingleSourceLongestPathStrategy(Graph graph, Node startNode, ToDoubleMapping edgeLengths)
Construct an instance of this analyzer.

Method Summary

protected java.lang.Object	_compute() The computation associated with this analyzer.
double[]	distance() Return the distance from the start node 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.
private int[]	predecessors() Return the predecessor array of this analyzer.
void	setStartNode(Node startNode) Set the single source node (starting node) of this analyzer to the given node.
java.lang.String	toString() Return a description of the analyzer.
boolean	valid() Check for compatibility between the analysis and the given graph.

Methods inherited from class ptolemy.graph.analysis.strategy.CachedStrategy

_convertResult, _result, cachingStatus, disableCaching, enableCaching, getCachedResult, graph, obsolete, reset, setCachedResult

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface ptolemy.graph.analysis.analyzer.GraphAnalyzer

graph

Field Detail

_edgeLengths

private ToDoubleMapping _edgeLengths

_startNode

private Node _startNode

_predecessor

private int[] _predecessor

Constructor Detail

AllEdgeSingleSourceLongestPathStrategy

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

Construct an instance of this analyzer.

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.

Method Detail

distance

public double[] distance()

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

Specified by:

distance in interface SingleSourceLongestPathAnalyzer

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.

Specified by:

getStartNode in interface SingleSourceLongestPathAnalyzer

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. The source node is defined in the constructor, and can be changed using setStartNode(ptolemy.graph.Node). The result includes the starting and the ending nodes.

Specified by:

path in interface SingleSourceLongestPathAnalyzer

Parameters:

endNode - The ending node of the path.

Returns:

The longest path.

pathLength

public double pathLength(Node endNode)

Return the length of the longest path from node startNode to node endNode. The source node is defined in the constructor and can be changed using setStartNode(ptolemy.graph.Node).

Specified by:

pathLength in interface SingleSourceLongestPathAnalyzer

Parameters:

endNode - The ending node of the path.

Returns:

The length of the longest path.

setStartNode

public void setStartNode(Node startNode)

Set the single source node (starting node) of this analyzer to the given node.

Specified by:

setStartNode in interface SingleSourceLongestPathAnalyzer

Parameters:

startNode - The given node.

See Also:

getStartNode()

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 and acyclic in order to use this algorithm. This compatibility check runs in O(N^3) in which N is the number of nodes.

Specified by:

valid in interface Analyzer

Returns:

True if the graph is a directed graph and acyclic.

_compute

protected java.lang.Object _compute()

The computation associated with this analyzer.

Overrides:

_compute in class CachedStrategy

Returns:

The result of the computation.

predecessors

private int[] predecessors()

Return the predecessor array of this analyzer. The array is indexed by a node label and contains the predecessor node label on the longest path.

Returns:

Return the predecessor array of this analyzer.