| 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