1   /****************************************************************************
2    * This demo file is part of yFiles for Java 2.14.
3    * Copyright (c) 2000-2017 by yWorks GmbH, Vor dem Kreuzberg 28,
4    * 72070 Tuebingen, Germany. All rights reserved.
5    * 
6    * yFiles demo files exhibit yFiles for Java functionalities. Any redistribution
7    * of demo files in source code or binary form, with or without
8    * modification, is not permitted.
9    * 
10   * Owners of a valid software license for a yFiles for Java version that this
11   * demo is shipped with are allowed to use the demo source code as basis
12   * for their own yFiles for Java powered applications. Use of such programs is
13   * governed by the rights and conditions as set out in the yFiles for Java
14   * license agreement.
15   * 
16   * THIS SOFTWARE IS PROVIDED ''AS IS'' AND ANY EXPRESS OR IMPLIED
17   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18   * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
19   * NO EVENT SHALL yWorks BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
21   * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23   * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24   * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26   *
27   ***************************************************************************/
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  /**
43   * Tests consistency and performance of two different cycle detection mechanisms
44   * in yFiles.
45   */
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      //find a set of edges whose reversal make the given graph
81      //acyclic.  reverse whose edges
82      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      //check acyclicity of graph
94      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     //use alternative DFS based method to detect
105     //with a set of cyclicity edges. 
106     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