1
28 package demo.algo;
29
30
31 import demo.base.RandomGraphGenerator;
32 import y.algo.Cycles;
33 import y.algo.GraphChecker;
34 import y.base.EdgeCursor;
35 import y.base.EdgeList;
36 import y.base.EdgeMap;
37 import y.base.Graph;
38 import y.util.D;
39 import y.util.Maps;
40 import y.util.Timer;
41
42
46 public class CyclesTest {
47
48 private Timer t1 = new Timer( false );
49 private Timer t2 = new Timer( false );
50
51 private int akku1 = 0;
52 private int akku2 = 0;
53
54
55 public static void main( String[] args ) {
56 CyclesTest cyclesTest = new CyclesTest();
57 cyclesTest.doIt();
58 }
59
60 private void doIt() {
61 for ( int i = 0; i < 1000; i++ ) {
62 D.bug( "test " + i );
63 test( i );
64 }
65
66 D.bug( "overall reversed edges (default method) " + akku1 + " time: " + t1 );
67 D.bug( "overall reversed edges (dfs method) " + akku2 + " time: " + t2 );
68 }
69
70 private void test( int seed ) {
71 RandomGraphGenerator rg = new RandomGraphGenerator( seed );
72 rg.setNodeCount( 100 );
73 rg.setEdgeCount( 300 );
74 rg.allowCycles( true );
75
76 Graph graph1 = rg.generate();
77
78 EdgeMap cycleEdge = Maps.createIndexEdgeMap( new boolean[graph1.E()] );
79
80 t1.start();
83 Cycles.findCycleEdges( graph1, cycleEdge );
84 int count1 = 0;
85 for ( EdgeCursor ec = graph1.edges(); ec.ok(); ec.next() ) {
86 if ( cycleEdge.getBool( ec.edge() ) ) {
87 graph1.reverseEdge( ec.edge() );
88 count1++;
89 }
90 }
91 t1.stop();
92
93 if ( GraphChecker.isCyclic( graph1 ) ) {
95 D.bug( "graph1 still contains cycles!!!" );
96 EdgeList cycle = Cycles.findCycle( graph1, true );
97 error( "cycle = " + cycle );
98 }
99
100
101 rg.setSeed( seed );
102 Graph graph2 = rg.generate();
103
104 t2.start();
107 Cycles.findCycleEdgesDFS( graph2, cycleEdge );
108 int count2 = 0;
109 for ( EdgeCursor ec = graph2.edges(); ec.ok(); ec.next() ) {
110 if ( cycleEdge.getBool( ec.edge() ) ) {
111 graph2.reverseEdge( ec.edge() );
112 count2++;
113 }
114 }
115 t2.stop();
116
117 if ( GraphChecker.isCyclic( graph2 ) ) {
118 D.bug( "graph2 still contains cycles!!!" );
119 EdgeList cycle = Cycles.findCycle( graph2, true );
120 error( "cycle = " + cycle );
121 }
122
123 akku1 += count1;
124 akku2 += count2;
125 }
126
127 private void error( String msg ) {
128 D.bug( msg );
129 System.exit( 666 );
130 }
131 }
132