TopologicalSortDemo.java |
1 /**************************************************************************** 2 * This demo file is part of yFiles for Java 2.14. 3 * Copyright (c) 2000-2017 by yWorks GmbH, Vor dem Kreuzberg 28, 4 * 72070 Tuebingen, Germany. All rights reserved. 5 * 6 * yFiles demo files exhibit yFiles for Java functionalities. Any redistribution 7 * of demo files in source code or binary form, with or without 8 * modification, is not permitted. 9 * 10 * Owners of a valid software license for a yFiles for Java version that this 11 * demo is shipped with are allowed to use the demo source code as basis 12 * for their own yFiles for Java powered applications. Use of such programs is 13 * governed by the rights and conditions as set out in the yFiles for Java 14 * license agreement. 15 * 16 * THIS SOFTWARE IS PROVIDED ''AS IS'' AND ANY EXPRESS OR IMPLIED 17 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 18 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN 19 * NO EVENT SHALL yWorks BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 20 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 21 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 22 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 23 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 24 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 * 27 ***************************************************************************/ 28 package demo.algo; 29 30 import y.algo.Dfs; 31 import y.base.Graph; 32 import y.base.Node; 33 import y.base.NodeCursor; 34 import y.base.NodeList; 35 36 import demo.base.RandomGraphGenerator; 37 38 /** 39 * This class demonstrates how to sort the node set of an acyclic graph 40 * topologically. 41 * A topological node order <CODE>S</CODE> of an 42 * acyclic graph <CODE>G</CODE> 43 * has the property that for each node <CODE>v</CODE> of <CODE>G</CODE> 44 * all of its successors have a higher rank than <CODE>v</CODE> in 45 * <CODE>S</CODE>. 46 * <br> 47 * The main purpose of this demo is to show how the generic Depth First Search 48 * class ({@link y.algo.Dfs}) can be utilized to implement more sophisticated 49 * graph algorithms. 50 * 51 */ 52 53 public class TopologicalSortDemo 54 { 55 /** 56 * Main method: 57 * <p> 58 * Usage: java demo.algo.TopologicalSortDemo <nodeCount> <edgeCount> 59 * </p><p> 60 * the first argument gives the desired node count of the graph 61 * and the second argument gives the desired edge count of the 62 * graph. 63 * </p> 64 */ 65 public static void main(String[] args) 66 { 67 int nodeCount = 30; 68 int edgeCount = 60; 69 70 if(args.length == 2) { 71 try { 72 nodeCount = Integer.parseInt(args[0]); 73 edgeCount = Integer.parseInt(args[1]); 74 } catch(NumberFormatException ex) { 75 usage(); 76 } 77 } 78 79 // Create a random acyclic graph with the given edge and node count 80 RandomGraphGenerator randomGraph = new RandomGraphGenerator(0L); 81 randomGraph.setNodeCount(nodeCount); 82 randomGraph.setEdgeCount(edgeCount); 83 randomGraph.allowCycles( false ); //create a DAG 84 Graph graph = randomGraph.generate(); 85 86 final NodeList tsOrder = new NodeList(); 87 88 if(!graph.isEmpty()) 89 { 90 // find start node with indegree 0 91 Node startNode = graph.firstNode(); 92 for(NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) 93 { 94 if(nc.node().inDegree() == 0) 95 { 96 startNode = nc.node(); 97 break; 98 } 99 } 100 101 // specialize DFS algorithm to collect topological information 102 Dfs dfs = new Dfs() { 103 protected void postVisit(Node v, int dfsNum, int compNum) 104 { 105 tsOrder.addFirst(v); 106 } 107 }; 108 109 // put dfs in directed mode 110 dfs.setDirectedMode(true); 111 // start specialized dfs 112 dfs.start(graph, startNode); 113 114 } 115 116 System.out.println("Topological Order:"); 117 int index = 0; 118 for(NodeCursor nc = tsOrder.nodes(); nc.ok(); nc.next(), index++) 119 { 120 System.out.println("" + index + ". " + nc.node()); 121 } 122 123 } 124 125 static void usage() 126 { 127 System.err.println("Usage: java demo.algo.TopologicalSortDemo <nodeCount> <edgeCount>"); 128 System.err.println("Usage: Both <nodeCount> and <edgeCount> must be integral values."); 129 System.exit(1); 130 } 131 } 132