1
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
48 public class SpanningTreeTest
49 {
50 private static long seed = 0;
51
52
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