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  import demo.base.RandomGraphGenerator;
17  import y.algo.GraphConnectivity;
18  import y.base.EdgeCursor;
19  import y.base.EdgeMap;
20  import y.base.Graph;
21  import y.base.Node;
22  import y.base.NodeCursor;
23  import y.base.NodeList;
24  import y.base.NodeMap;
25  import y.util.D;
26  import y.util.Maps;
27  import y.util.Timer;
28  import y.util.YRandom;
29  
30  /**
31   * Demonstrates how to use connectivity and biconnectivity algorithms.
32   * Tests the performance of these algorithms.
33   */
34  public class GraphConnectivityTest {
35    private Timer t1 = new Timer( false );
36    private Timer t2 = new Timer( false );
37  
38    public static void main( String args[] ) {
39      (new GraphConnectivityTest()).doIt();
40    }
41  
42    private void doIt() {
43      for ( int i = 0; i < 400; i++ ) {
44        D.bug( "test " + i );
45        test1( i );
46      }
47  
48      D.bug( "connectivity timer: " + t1 + "    biconnectivity timer: " + t2 );
49    }
50  
51    private void test1( int seed ) {
52      //create random graph
53      RandomGraphGenerator rg = new RandomGraphGenerator( seed );
54      YRandom random = new YRandom( seed );
55      rg.setNodeCount( random.nextInt( 400 ) );
56      rg.setEdgeCount( random.nextInt( 800 ) );
57  
58      Graph graph = rg.generate();
59  
60      t1.start();
61      //calculatethe connected components of the graph
62      NodeList[] comps = GraphConnectivity.connectedComponents( graph );
63      t1.stop();
64  
65      //add edges to the graph until the whole graph is connected.
66      //this is done by connecting the first nodes of the first 
67      //two connected components. this operation reduces the 
68      //compinent count by one.
69      int oldCompCount = comps.length + 1;
70      while ( comps.length > 1 ) {
71        oldCompCount = comps.length;
72        //connect first two components
73        graph.createEdge( comps[0].firstNode(), comps[1].firstNode() );
74        comps = GraphConnectivity.connectedComponents( graph );
75        if ( comps.length != oldCompCount - 1 ) {
76          error( "connected components yields wrong result!" );
77        }
78      }
79  
80      //next fetch biconnected components. 
81      //be sure that the precondition is valid  
82      GraphConnectivity.makeConnected( graph );
83  
84      //use a static node map in case the node indices do not
85      //change while the map is needed. static maps are
86      //generally faster than dynamic maps
87      NodeMap aMap = Maps.createIndexNodeMap( new boolean[graph.N()] );
88      //create dynamic edge map in case the edge indices or edge set
89      //changes while the map is needed.
90      EdgeMap cMap = graph.createEdgeMap();
91  
92  
93      GraphConnectivity.makeConnected( graph );
94  
95      t2.start();
96      int bicompCount = GraphConnectivity.biconnectedComponents( graph, cMap, aMap );
97      t2.stop();
98  
99      //for the sake of demonstration we remove all edges that connect
100     //to an articulation point. 
101     for ( NodeCursor nc = graph.nodes(); nc.ok(); nc.next() ) {
102       if ( aMap.getBool( nc.node() ) ) {
103         Node v = nc.node();
104         //v is an articulation point of graph.
105         //remove all edges around an articulation point
106         for ( EdgeCursor ec = v.edges(); ec.ok(); ec.next() )
107           graph.removeEdge( ec.edge() );
108       }
109     }
110 
111     //dispose dynamic nodemap sinbce it is not needed anymore.
112     graph.disposeEdgeMap( cMap );
113 
114   }
115 
116   private static void error( String msg ) {
117     D.bug( msg );
118     System.exit( 666 );
119   }
120 
121 }
122 
123   
124       
125