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.NodeOrders;
17  
18  import y.util.YRandom;
19  import y.util.Timer;
20  import y.util.D;
21  import y.base.Graph;
22  import y.base.NodeCursor;
23  import y.base.Node;
24  
25  import demo.base.RandomGraphGenerator;
26  
27  /**
28   * This class compares different methods that calculate a topological
29   * node ordering on the nodes of an acyclic graph.
30   **/
31  public class TopologicalTest
32  {
33    private Timer timerA = new Timer(false);
34    private Timer timerB = new Timer(false);
35    private Timer timerC = new Timer(false);
36    private Timer timerD = new Timer(false);
37  
38    public static void main(String[] args)
39    {
40      (new TopologicalTest()).testTOP();
41    }
42    
43  
44    
45    private void testTOP()
46    {
47      timerA.reset();
48      timerB.reset();
49      timerC.reset();
50      timerD.reset();
51      
52      timerD.start();
53      for(int i = 0; i < 1000; i++)
54        testTOP(i);
55      timerD.stop();
56      D.bug(
57        "overall = "    + timerD + 
58        "\ngenerate = " + timerC + 
59        "\ntopological   = "      + timerA + 
60        "\ndfs completion = "      + timerB
61        );
62    }
63    
64    private void testTOP(int loop)
65    {
66      D.bug("test TOP " + loop);
67      
68      YRandom random = new YRandom(loop);
69      
70      RandomGraphGenerator rg = new RandomGraphGenerator(loop);
71      
72      rg.allowCycles(loop % 2 == 0);
73      rg.setNodeCount(100);
74      rg.setEdgeCount(1000);
75      
76      
77      timerC.start();
78      Graph G = rg.generate();
79      timerC.stop();
80      
81      
82      int[] topOrderA = new int[G.N()];
83      int[] topOrderB = new int[G.N()];
84      
85      timerA.start();
86      boolean resultA = NodeOrders.topological(G,topOrderA);
87      timerA.stop();
88  
89      if(resultA)
90      {
91        check("topological", G, topOrderA);
92      }
93      
94      timerB.start();
95      NodeOrders.dfsCompletion(G,topOrderB);
96      timerB.stop();
97      if(resultA)
98      {
99        check("dfs completion", G, reverse(topOrderB));
100     }
101   }
102   
103   
104   private int[] reverse(int[] order)
105   {
106     int[] reverse = new int[order.length];
107     for(int i = 0; i < order.length; i++)
108     {
109       reverse[i] = order.length-1-order[i];
110     }
111     return reverse;
112   }
113   
114   private void check(String desc, Graph G, int[] topOrder)
115   {
116     boolean[] tag = new boolean[G.N()];
117     for(NodeCursor nc = G.nodes(); nc.ok(); nc.next())
118     {
119       Node v = nc.node();
120       int vid = v.index();
121       int order = topOrder[vid];
122       if(order < 0 || order >= G.N())
123         error(desc + " : order number for " + v + " out of bounds: " + order);
124       if(tag[order]) 
125         error(desc + " : order number for " + v + " already assigned: " + order);
126       for(NodeCursor ncc = v.successors(); ncc.ok(); ncc.next())
127       {
128         Node u = ncc.node();
129         int uid = u.index();
130         if(topOrder[uid] <= order)
131           error(desc + " : nodes in wrong order!");
132       }
133       tag[order] = true;
134     }
135   }
136 
137   private void error(String msg)
138   {
139     D.bug(msg);
140     System.exit(1);
141   }
142 }
143