001/* An analysis to find the longest path from a single source to all the other
002 nodes in a directed graph.
003
004 Copyright (c) 2003-2014 The University of Maryland. All rights reserved.
005 Permission is hereby granted, without written agreement and without
006 license or royalty fees, to use, copy, modify, and distribute this
007 software and its documentation for any purpose, provided that the above
008 copyright notice and the following two paragraphs appear in all copies
009 of this software.
010
011 IN NO EVENT SHALL THE UNIVERSITY OF MARYLAND BE LIABLE TO ANY PARTY
012 FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
013 ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
014 THE UNIVERSITY OF MARYLAND HAS BEEN ADVISED OF THE POSSIBILITY OF
015 SUCH DAMAGE.
016
017 THE UNIVERSITY OF MARYLAND SPECIFICALLY DISCLAIMS ANY WARRANTIES,
018 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
019 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
020 PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
021 MARYLAND HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
022 ENHANCEMENTS, OR MODIFICATIONS.
023
024
025 */
026package ptolemy.graph.analysis;
027
028import java.util.List;
029
030import ptolemy.graph.Graph;
031import ptolemy.graph.Node;
032import ptolemy.graph.analysis.analyzer.Analyzer;
033import ptolemy.graph.analysis.analyzer.SingleSourceLongestPathAnalyzer;
034import ptolemy.graph.analysis.strategy.AllEdgeSingleSourceLongestPathStrategy;
035import ptolemy.graph.mapping.ToDoubleMapping;
036
037///////////////////////////////////////////////////////////////////
038//// SingleSourceLongestPathAnalysis
039
040/**
041 An analysis to find the longest path from a single source to all the other
042 nodes in a directed graph. In a graph with multiple edges between two nodes the
043 one with the largest associated value is being considered for the longest path.
044 <p>
045
046 @since Ptolemy II 4.0
047 @Pt.ProposedRating Red (shahrooz)
048 @Pt.AcceptedRating Red (ssb)
049 @author Shahrooz Shahparnia
050 @version $Id$
051 */
052public class SingleSourceLongestPathAnalysis extends Analysis {
053    /** Construct an instance of this class with a default analyzer.
054     *  The default analyzer runs in O(E), in which E is the number of edges.
055     *
056     *  @param graph The given graph.
057     *  @param startNode The node from which the longest path is going to be
058     *  calculated.
059     *  @param edgeLengths The lengths of the edges of the given graph, which
060     *  are going to be used to calculated the longest path.
061     */
062    public SingleSourceLongestPathAnalysis(Graph graph, Node startNode,
063            ToDoubleMapping edgeLengths) {
064        super(new AllEdgeSingleSourceLongestPathStrategy(graph, startNode,
065                edgeLengths));
066    }
067
068    /** Construct an instance of this class with a given analyzer.
069     *
070     *  @param analyzer The given analyzer.
071     */
072    public SingleSourceLongestPathAnalysis(
073            SingleSourceLongestPathAnalyzer analyzer) {
074        super(analyzer);
075    }
076
077    ///////////////////////////////////////////////////////////////////
078    ////                         public methods                    ////
079
080    /** Return the distance from the node "startNode" to all the other nodes in
081     *  the graph.
082     *  The result is a double[] indexed by the destination node-label.
083     *  <p>
084     *  @see ptolemy.graph.Graph#nodeLabel
085     *
086     *  @return Return the distance from the start node to all the other nodes
087     *  in the graph.
088     */
089    public double[] distance() {
090        return ((SingleSourceLongestPathAnalyzer) analyzer()).distance();
091    }
092
093    /** Return the single source-node (start node) of this analyzer.
094     *
095     *  @return Return the starting node of this analyzer.
096     *  @see #setStartNode(Node)
097     */
098    public Node getStartNode() {
099        return ((SingleSourceLongestPathAnalyzer) analyzer()).getStartNode();
100    }
101
102    /** Return the longest path from node "startNode" to node "endNode" in the
103     *  form of an ordered list.
104     *
105     *  @param endNode The ending node of the path.
106     *  @return The longest path from "startNode" to "endNode".
107     */
108    public List path(Node endNode) {
109        return ((SingleSourceLongestPathAnalyzer) analyzer()).path(endNode);
110    }
111
112    /** Return the length of the longest path from node "startNode"
113     *  to node "endNode". The source node can be set
114     *  using {@link #setStartNode}.
115     *
116     *  @param endNode The ending node of the path.
117     *  @return The length of the longest path.
118     */
119    public double pathLength(Node endNode) {
120        return ((SingleSourceLongestPathAnalyzer) analyzer())
121                .pathLength(endNode);
122    }
123
124    /** Set the start-node of this analysis to the given node.
125     *
126     *  @param startNode The given node.
127     *  @see #getStartNode()
128     */
129    public void setStartNode(Node startNode) {
130        ((SingleSourceLongestPathAnalyzer) analyzer()).setStartNode(startNode);
131    }
132
133    /** Return a description of the analysis and the associated analyzer.
134     *
135     *  @return A description of the analysis and the associated analyzer.
136     */
137    @Override
138    public String toString() {
139        return "Single source longest path analysis using "
140                + "the following analyzer:\n" + analyzer().toString();
141    }
142
143    /** Check if a given analyzer is compatible with this analysis.
144     *  In other words if it is possible to use it to compute the computation
145     *  associated with this analysis.
146     *
147     *  @param analyzer The given analyzer.
148     *  @return True if the given analyzer is valid for this analysis.
149     */
150    @Override
151    public boolean validAnalyzerInterface(Analyzer analyzer) {
152        return analyzer instanceof SingleSourceLongestPathAnalyzer;
153    }
154}