1   /****************************************************************************
2    **
3    ** This file is part of yFiles-2.6. 
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-2008 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 nodeset 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>
46     * the first argument gives the desired node count of the graph 
47     * and the second argumnent gives the desired edge count of the 
48     * graph.
49     */
50    public static void main(String args[])
51    {
52      int nodeCount = 30;
53      int edgeCount = 60;
54      
55      if(args.length == 2) {
56        try {
57          nodeCount = Integer.parseInt(args[0]);
58          edgeCount = Integer.parseInt(args[1]);
59        } catch(NumberFormatException ex) {
60          usage();
61        }
62      }
63      
64      // Create a random acyclic graph with the given edge and node count
65      RandomGraphGenerator randomGraph = new RandomGraphGenerator(0L);
66      randomGraph.setNodeCount(nodeCount);
67      randomGraph.setEdgeCount(edgeCount);
68      randomGraph.allowCycles( false ); //create a DAG
69      Graph graph = randomGraph.generate();
70      
71      final NodeList tsOrder = new NodeList();
72      
73      if(!graph.isEmpty())
74      {
75        // find start node with indegree 0
76        Node startNode = graph.firstNode();
77        for(NodeCursor nc = graph.nodes(); nc.ok(); nc.next())
78        {
79          if(nc.node().inDegree() == 0)
80          {
81            startNode = nc.node();
82            break;
83          }
84        }
85        
86        // specialize DFS algorithm to collect topological information
87        Dfs dfs = new Dfs() {
88          protected void postVisit(Node v, int dfsNum, int compNum)
89            {
90              tsOrder.addFirst(v);
91            }
92        };
93        
94        // put dfs in directed mode
95        dfs.setDirectedMode(true);
96        // start specialized dfs
97        dfs.start(graph, startNode);
98        
99      }
100     
101     System.out.println("Topological Order:");
102     int index = 0;
103     for(NodeCursor nc = tsOrder.nodes(); nc.ok(); nc.next(), index++)
104     {
105       System.out.println("" + index + ". " + nc.node());
106     }
107     
108   }
109 
110   static void usage()
111   {
112     System.err.println("Usage: java demo.algo.TopologicalSortDemo <nodeCount> <edgeCount>");
113     System.err.println("Usage: Both <nodeCount> and <edgeCount> must be integral values.");
114     System.exit(1);
115   }
116 }
117