1
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
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