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.SpanningTrees;
31  import y.algo.GraphConnectivity;
32  
33  import y.util.YRandom;
34  import y.util.DataProviders;
35  import y.util.Timer;
36  import y.util.D;
37  import y.base.Graph;
38  import y.base.Edge;
39  import y.base.DataProvider;
40  import y.base.EdgeList;
41  import y.base.EdgeCursor;
42  
43  import demo.base.RandomGraphGenerator;
44  
45  /**
46   * This class compares the performance of different minimum spanning tree algorithms.
47   */
48  public class SpanningTreeTest
49  {
50    private static long seed = 0;
51  
52    /**
53     * Program launcher. Accepts a random seed on the command line.
54     */  
55    public static void main(String[] args)
56    {
57      try 
58      {
59        seed = Long.parseLong(args[0]);
60      }
61      catch(Exception ex) {}
62      
63      (new SpanningTreeTest()).testMST();
64    }
65    
66  
67    
68    private void testMST()
69    {
70      D.bug(">>> testMST");
71      Timer timerA = new Timer(false);
72      Timer timerB = new Timer(false);
73      timerA.reset();
74      timerB.reset();
75      
76      YRandom random = new YRandom(seed);
77      
78      RandomGraphGenerator rg = new RandomGraphGenerator(seed);
79      rg.allowCycles(true);
80      
81      for(int size = 100; size <= 100000; size *= 10)
82      {
83        for(int trial = 0; trial < 100; trial++)
84        {
85          if(trial % 60 == 59) D.bug("."); else D.bu(".");
86          
87          rg.setNodeCount(random.nextInt(1000,2000));
88          rg.setEdgeCount(random.nextInt(size/10,size));
89          
90          Graph G = rg.generate();
91          int eCount = GraphConnectivity.makeConnected(G).size();
92          
93          double[] cost = new double[G.E()];
94          
95          for(EdgeCursor ec = G.edges(); ec.ok(); ec.next())
96          {
97            Edge e = ec.edge();
98            int eid = e.index();
99            cost[eid] = random.nextInt(100000);
100         }
101         
102         DataProvider c = DataProviders.createEdgeDataProvider(cost);
103         
104         timerA.start();
105         EdgeList resultA = SpanningTrees.kruskal(G,c);
106         double costA = SpanningTrees.cost(resultA,c);
107         timerA.stop();
108         
109         timerB.start();
110         EdgeList resultB = SpanningTrees.prim(G,c);
111         double costB = SpanningTrees.cost(resultB,c);
112         timerB.stop();
113         
114         if(costA != costB)
115         {
116           D.bug("\ncost mismatch: trial = " + trial);
117           D.bug("costA = " + costA + "   costBi = " + costB);
118         }
119       }
120       D.bug("\nsize=" + size + "\nkruskal " + timerA + "\nprim    " + timerB);
121       timerA.reset();
122       timerB.reset();
123     }
124     
125     D.bug("<<< testMST\n\n");
126   }
127 }
128