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