| 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