| TopologicalSortDemo.java |
1 /****************************************************************************
2 **
3 ** This file is part of yFiles-2.9.
4 **
5 ** yWorks proprietary/confidential. Use is subject to license terms.
6 **
7 ** Redistribution of this file or of an unauthorized byte-code version
8 ** of this file is strictly forbidden.
9 **
10 ** Copyright (c) 2000-2011 by yWorks GmbH, Vor dem Kreuzberg 28,
11 ** 72070 Tuebingen, Germany. All rights reserved.
12 **
13 ***************************************************************************/
14 package demo.algo;
15
16 import y.algo.Dfs;
17 import y.base.Graph;
18 import y.base.Node;
19 import y.base.NodeCursor;
20 import y.base.NodeList;
21
22 import demo.base.RandomGraphGenerator;
23
24 /**
25 * This class demonstrates how to sort the node set of an acyclic graph
26 * topologically.
27 * A topological node order <CODE>S</CODE> of an
28 * acyclic graph <CODE>G</CODE>
29 * has the property that for each node <CODE>v</CODE> of <CODE>G</CODE>
30 * all of its successors have a higher rank than <CODE>v</CODE> in
31 * <CODE>S</CODE>.
32 * <br>
33 * The main purpose of this demo is to show how the generic Depth First Search
34 * class ({@link y.algo.Dfs}) can be utilized to implement more sophisticated
35 * graph algorithms.
36 *
37 */
38
39 public class TopologicalSortDemo
40 {
41 /**
42 * Main method:
43 * <p>
44 * Usage: java demo.algo.TopologicalSortDemo <nodeCount> <edgeCount>
45 * </p><p>
46 * the first argument gives the desired node count of the graph
47 * and the second argument gives the desired edge count of the
48 * graph.
49 * </p>
50 */
51 public static void main(String[] args)
52 {
53 int nodeCount = 30;
54 int edgeCount = 60;
55
56 if(args.length == 2) {
57 try {
58 nodeCount = Integer.parseInt(args[0]);
59 edgeCount = Integer.parseInt(args[1]);
60 } catch(NumberFormatException ex) {
61 usage();
62 }
63 }
64
65 // Create a random acyclic graph with the given edge and node count
66 RandomGraphGenerator randomGraph = new RandomGraphGenerator(0L);
67 randomGraph.setNodeCount(nodeCount);
68 randomGraph.setEdgeCount(edgeCount);
69 randomGraph.allowCycles( false ); //create a DAG
70 Graph graph = randomGraph.generate();
71
72 final NodeList tsOrder = new NodeList();
73
74 if(!graph.isEmpty())
75 {
76 // find start node with indegree 0
77 Node startNode = graph.firstNode();
78 for(NodeCursor nc = graph.nodes(); nc.ok(); nc.next())
79 {
80 if(nc.node().inDegree() == 0)
81 {
82 startNode = nc.node();
83 break;
84 }
85 }
86
87 // specialize DFS algorithm to collect topological information
88 Dfs dfs = new Dfs() {
89 protected void postVisit(Node v, int dfsNum, int compNum)
90 {
91 tsOrder.addFirst(v);
92 }
93 };
94
95 // put dfs in directed mode
96 dfs.setDirectedMode(true);
97 // start specialized dfs
98 dfs.start(graph, startNode);
99
100 }
101
102 System.out.println("Topological Order:");
103 int index = 0;
104 for(NodeCursor nc = tsOrder.nodes(); nc.ok(); nc.next(), index++)
105 {
106 System.out.println("" + index + ". " + nc.node());
107 }
108
109 }
110
111 static void usage()
112 {
113 System.err.println("Usage: java demo.algo.TopologicalSortDemo <nodeCount> <edgeCount>");
114 System.err.println("Usage: Both <nodeCount> and <edgeCount> must be integral values.");
115 System.exit(1);
116 }
117 }
118