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