001/* Computation of sink nodes in a graph.
002
003 Copyright (c) 2003-2014 The University of Maryland. All rights reserved.
004 Permission is hereby granted, without written agreement and without
005 license or royalty fees, to use, copy, modify, and distribute this
006 software and its documentation for any purpose, provided that the above
007 copyright notice and the following two paragraphs appear in all copies
008 of this software.
009
010 IN NO EVENT SHALL THE UNIVERSITY OF MARYLAND BE LIABLE TO ANY PARTY
011 FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
012 ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
013 THE UNIVERSITY OF MARYLAND HAS BEEN ADVISED OF THE POSSIBILITY OF
014 SUCH DAMAGE.
015
016 THE UNIVERSITY OF MARYLAND SPECIFICALLY DISCLAIMS ANY WARRANTIES,
017 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
018 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
019 PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
020 MARYLAND HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
021 ENHANCEMENTS, OR MODIFICATIONS.
022
023
024 */
025package ptolemy.graph.analysis.strategy;
026
027import java.util.ArrayList;
028import java.util.Collections;
029import java.util.Iterator;
030import java.util.List;
031
032import ptolemy.graph.DirectedGraph;
033import ptolemy.graph.Graph;
034import ptolemy.graph.Node;
035import ptolemy.graph.analysis.analyzer.SinkNodeAnalyzer;
036
037///////////////////////////////////////////////////////////////////
038//// SinkNodeStrategy
039
040/**
041 Computation of sink nodes in a graph.
042 The collection returned cannot be modified.
043 <p>
044 This analysis requires <em>O</em>(<em>N</em>) time, where <em>N</em> is the
045 number of nodes in the graph.
046 <p>
047 @see ptolemy.graph.analysis.SinkNodeAnalysis
048 @since Ptolemy II 4.0
049 @Pt.ProposedRating Red (ssb)
050 @Pt.AcceptedRating Red (ssb)
051 @author Ming Yung Ko, Shahrooz Shahparnia
052 @version $Id$
053 */
054public class SinkNodeStrategy extends CachedStrategy
055        implements SinkNodeAnalyzer {
056    /** Construct a sink node analysis for a given graph.
057     *  @param graph The given graph.
058     */
059    public SinkNodeStrategy(Graph graph) {
060        super(graph);
061    }
062
063    ///////////////////////////////////////////////////////////////////
064    ////                         public methods                    ////
065
066    /** Compute the sink nodes in the graph in the form of
067     *  a collection. Each element of the collection is a {@link Node}.
068     *  @return The sink nodes.
069     */
070    @Override
071    public List nodes() {
072        return (List) _result();
073    }
074
075    /** Return a description of sink nodes.
076     *
077     *  @return A description of the sink nodes.
078     */
079    @Override
080    public String toString() {
081        String result = "Sink node analysis for the following graph.\n"
082                + graph().toString();
083        result += "The sink nodes are:\n" + _result();
084        return result;
085    }
086
087    /** Check compatibility of the class of graph. The given graph
088     *  must be an instance of DirectedGraph.
089     *
090     *  @return True if the given graph is of class DirectedGraph.
091     */
092    @Override
093    public boolean valid() {
094        return graph() instanceof DirectedGraph;
095    }
096
097    ///////////////////////////////////////////////////////////////////
098    ////                         protected methods                 ////
099
100    /** Compute the sink nodes in the graph in the form of
101     *  a collection. Each element of the collection is a {@link Node}.
102     *  @return The sink nodes.
103     */
104    @Override
105    protected Object _compute() {
106        ArrayList sinkNodes = new ArrayList();
107        Iterator nodes = graph().nodes().iterator();
108
109        while (nodes.hasNext()) {
110            Node node = (Node) nodes.next();
111
112            if (((DirectedGraph) graph()).outputEdgeCount(node) == 0) {
113                sinkNodes.add(node);
114            }
115        }
116
117        return sinkNodes;
118    }
119
120    /** Return the result of this analysis (collection of sink nodes)
121     *  in a form that cannot be modified.
122     *  @return The analysis result in unmodifiable form.
123     */
124    protected Object _convertResult() {
125        return Collections.unmodifiableList((List) _result());
126    }
127}