/* Below is the copyright agreement for the Ptolemy II system. Copyright (c) 2010-2014 The Regents of the University of California. All rights reserved. Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software. IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. Ptolemy II includes the work of others, to see those copyrights, follow the copyright link on the splash page or see copyright.htm. */ /* Demonstration of an attribute that uses Dijkstra's algorith to find * the shorted path between two actors in a model. */ package doc.tutorial.graph; import java.awt.Frame; import java.util.HashMap; import java.util.List; import java.util.Map; import ptolemy.actor.IOPort; import ptolemy.actor.gui.EditorFactory; import ptolemy.gui.ComponentDialog; import ptolemy.gui.Query; import ptolemy.kernel.CompositeEntity; import ptolemy.kernel.Entity; import ptolemy.kernel.util.Attribute; import ptolemy.kernel.util.IllegalActionException; import ptolemy.kernel.util.NameDuplicationException; import ptolemy.kernel.util.NamedObj; import ptolemy.util.MessageHandler; /** This class is an attribute that you can insert in a model * that will calculate the minimum number of hops (the minimum * distance) between a given source actor and a given destination * actor. When you double click on the attribute's icon, a * dialog will pop up asking the user to specify the source * and destination actor. Once these are specified, this class * runs Dijkstra's algorithm and reports the minimum distance. *
* To place this attribute in model, in Vergil, select * Graph->Instantiate Attribute and specify for the class * name: doc.tutorial.graph.ShortestPathFinder. Alternatively, * you can paste the following MoML code into the model: *
* <property name="ShortestPathFinder" class="doc.tutorial.graph.ShortestPathFinder"> * <property name="_location" class="ptolemy.kernel.util.Location" value="[100, 100]"/> * </property> ** In the above, the _location property is necessary to ensure * that Vergil shows an icon for the HelloWorld attribute. * It specifies the location on the canvas where that icon * should be placed. * * @author Edward A. Lee * @version $Id: ShortestPathFinder.java 70398 2014-10-22 23:44:32Z cxh $ * */ public class ShortestPathFinder extends Attribute { /** Need this two-argument constructor to be able to instantiate * the attribute in a model using MoML. * @param container The containing model. * @param name The name to give this attribute. * @exception IllegalActionException If the factory is not of an * acceptable attribute for the container. * @exception NameDuplicationException If the name coincides with * an attribute already in the container. */ public ShortestPathFinder(NamedObj container, String name) throws IllegalActionException, NameDuplicationException { super(container, name); // Create an EditorFactory to handle double clicks. new Calculate(this, "Calculate"); } /** Return the minimum distance of the specified end node from the specified * start node in the array of nodes, where each node is an Entity * in a Ptolemy II model. The distance is the number of hops. * @param entities The array of entities. * @param start The index of the start entity. * @param end The index of the end entity. * @return The minimum distance from the start to the end. */ public static int calculateDistance(Object[] entities, int start, int end) { // Array indicating which nodes have final distances. // This initializes to false for all nodes. boolean[] visited = new boolean[entities.length]; // Array indicating the calculated distances from the start. int[] distance = new int[entities.length]; // Use max value to represent infinity (no path). for (int i = 0; i < entities.length; i++) { distance[i] = Integer.MAX_VALUE; } distance[start] = 0; // Create a way to get the index of a node given // a reference to the node itself. Map