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  
17  import demo.base.RandomGraphGenerator;
18  import y.algo.Cycles;
19  import y.algo.GraphChecker;
20  import y.base.EdgeCursor;
21  import y.base.EdgeList;
22  import y.base.EdgeMap;
23  import y.base.Graph;
24  import y.util.D;
25  import y.util.Maps;
26  import y.util.Timer;
27  
28  /**
29   * Tests consistency and performance of two different cycle detection mechanisms
30   * in yFiles.
31   */
32  public class CyclesTest {
33  
34    private Timer t1 = new Timer( false );
35    private Timer t2 = new Timer( false );
36  
37    private int akku1 = 0;
38    private int akku2 = 0;
39  
40  
41    public static void main( String args[] ) {
42      CyclesTest cyclesTest = new CyclesTest();
43      cyclesTest.doIt();
44    }
45  
46    private void doIt() {
47      for ( int i = 0; i < 1000; i++ ) {
48        D.bug( "test " + i );
49        test( i );
50      }
51  
52      D.bug( "overall reversed edges (default method) " + akku1 + "    time: " + t1 );
53      D.bug( "overall reversed edges (dfs     method) " + akku2 + "    time: " + t2 );
54    }
55  
56    private void test( int seed ) {
57      RandomGraphGenerator rg = new RandomGraphGenerator( seed );
58      rg.setNodeCount( 100 );
59      rg.setEdgeCount( 300 );
60      rg.allowCycles( true );
61  
62      Graph graph1 = rg.generate();
63  
64      EdgeMap cycleEdge = Maps.createIndexEdgeMap( new boolean[graph1.E()] );
65  
66      //find a set of edges whose reversal make the given graph
67      //acyclic.  reverse whose edges
68      t1.start();
69      Cycles.findCycleEdges( graph1, cycleEdge );
70      int count1 = 0;
71      for ( EdgeCursor ec = graph1.edges(); ec.ok(); ec.next() ) {
72        if ( cycleEdge.getBool( ec.edge() ) ) {
73          graph1.reverseEdge( ec.edge() );
74          count1++;
75        }
76      }
77      t1.stop();
78  
79      //check acyclicity of graph
80      if ( GraphChecker.isCyclic( graph1 ) ) {
81        D.bug( "graph1 still contains cycles!!!" );
82        EdgeList cycle = Cycles.findCycle( graph1, true );
83        error( "cycle = " + cycle );
84      }
85  
86  
87      rg.setSeed( seed );
88      Graph graph2 = rg.generate();
89  
90      //use alternative DFS based method to detect
91      //with a set of cyclicity edges. 
92      t2.start();
93      Cycles.findCycleEdgesDFS( graph2, cycleEdge );
94      int count2 = 0;
95      for ( EdgeCursor ec = graph2.edges(); ec.ok(); ec.next() ) {
96        if ( cycleEdge.getBool( ec.edge() ) ) {
97          graph2.reverseEdge( ec.edge() );
98          count2++;
99        }
100     }
101     t2.stop();
102 
103     if ( GraphChecker.isCyclic( graph2 ) ) {
104       D.bug( "graph2 still contains cycles!!!" );
105       EdgeList cycle = Cycles.findCycle( graph2, true );
106       error( "cycle = " + cycle );
107     }
108 
109     akku1 += count1;
110     akku2 += count2;
111   }
112 
113   private void error( String msg ) {
114     D.bug( msg );
115     System.exit( 666 );
116   }
117 }
118