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