KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > alg > ConnectivityInspectorTest


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */

25 /* ------------------------------
26  * ConnectivityInspectorTest.java
27  * ------------------------------
28  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
29  *
30  * Original Author: Barak Naveh
31  * Contributor(s): John V. Sichi
32  *
33  * $Id: ConnectivityInspectorTest.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 07-Aug-2003 : Initial revision (BN);
38  * 20-Apr-2005 : Added StrongConnectivityInspector test (JVS);
39  *
40  */

41 package org.jgrapht.alg;
42
43 import java.util.*;
44
45 import junit.framework.*;
46
47 import org.jgrapht.*;
48 import org.jgrapht.graph.*;
49
50
51 /**
52  * .
53  *
54  * @author Barak Naveh
55  */

56 public class ConnectivityInspectorTest
57     extends TestCase
58 {
59
60     //~ Static fields/initializers --------------------------------------------
61

62     private static final String JavaDoc V1 = "v1";
63     private static final String JavaDoc V2 = "v2";
64     private static final String JavaDoc V3 = "v3";
65     private static final String JavaDoc V4 = "v4";
66
67     //~ Instance fields -------------------------------------------------------
68

69     //
70
DefaultEdge e1;
71     DefaultEdge e2;
72     DefaultEdge e3;
73     DefaultEdge e3_b;
74     DefaultEdge u;
75
76     //~ Methods ---------------------------------------------------------------
77

78     /**
79      * .
80      *
81      * @return a graph
82      */

83     public Pseudograph<String JavaDoc, DefaultEdge> create()
84     {
85         Pseudograph<String JavaDoc, DefaultEdge> g =
86             new Pseudograph<String JavaDoc, DefaultEdge>(DefaultEdge.class);
87
88         assertEquals(0, g.vertexSet().size());
89         g.addVertex(V1);
90         assertEquals(1, g.vertexSet().size());
91         g.addVertex(V2);
92         assertEquals(2, g.vertexSet().size());
93         g.addVertex(V3);
94         assertEquals(3, g.vertexSet().size());
95         g.addVertex(V4);
96         assertEquals(4, g.vertexSet().size());
97
98         assertEquals(0, g.edgeSet().size());
99
100         e1 = g.addEdge(V1, V2);
101         assertEquals(1, g.edgeSet().size());
102
103         e2 = g.addEdge(V2, V3);
104         assertEquals(2, g.edgeSet().size());
105
106         e3 = g.addEdge(V3, V1);
107         assertEquals(3, g.edgeSet().size());
108
109         e3_b = g.addEdge(V3, V1);
110         assertEquals(4, g.edgeSet().size());
111         assertNotNull(e3_b);
112
113         u = g.addEdge(V1, V1);
114         assertEquals(5, g.edgeSet().size());
115         u = g.addEdge(V1, V1);
116         assertEquals(6, g.edgeSet().size());
117
118         return g;
119     }
120
121     /**
122      * .
123      */

124     public void testDirectedGraph()
125     {
126         ListenableDirectedGraph<String JavaDoc, DefaultEdge> g =
127             new ListenableDirectedGraph<String JavaDoc, DefaultEdge>(
128                 DefaultEdge.class);
129         g.addVertex(V1);
130         g.addVertex(V2);
131         g.addVertex(V3);
132
133         g.addEdge(V1, V2);
134
135         ConnectivityInspector<String JavaDoc, DefaultEdge> inspector =
136             new ConnectivityInspector<String JavaDoc, DefaultEdge>(g);
137         g.addGraphListener(inspector);
138
139         assertEquals(false, inspector.isGraphConnected());
140
141         g.addEdge(V1, V3);
142
143         assertEquals(true, inspector.isGraphConnected());
144     }
145
146     /**
147      * .
148      */

149     public void testIsGraphConnected()
150     {
151         Pseudograph<String JavaDoc, DefaultEdge> g = create();
152         ConnectivityInspector<String JavaDoc, DefaultEdge> inspector =
153             new ConnectivityInspector<String JavaDoc, DefaultEdge>(g);
154
155         assertEquals(false, inspector.isGraphConnected());
156
157         g.removeVertex(V4);
158         inspector = new ConnectivityInspector<String JavaDoc, DefaultEdge>(g);
159         assertEquals(true, inspector.isGraphConnected());
160
161         g.removeVertex(V1);
162         assertEquals(1, g.edgeSet().size());
163
164         g.removeEdge(e2);
165         g.addEdge(V2, V2);
166         assertEquals(1, g.edgeSet().size());
167
168         inspector = new ConnectivityInspector<String JavaDoc, DefaultEdge>(g);
169         assertEquals(false, inspector.isGraphConnected());
170     }
171
172     /**
173      * .
174      */

175     public void testStronglyConnected1()
176     {
177         DirectedGraph<String JavaDoc, DefaultEdge> g =
178             new DefaultDirectedGraph<String JavaDoc, DefaultEdge>(
179                 DefaultEdge.class);
180         g.addVertex(V1);
181         g.addVertex(V2);
182         g.addVertex(V3);
183         g.addVertex(V4);
184
185         g.addEdge(V1, V2);
186         g.addEdge(V2, V1); // strongly connected
187

188         g.addEdge(V3, V4); // only weakly connected
189

190         StrongConnectivityInspector<String JavaDoc, DefaultEdge> inspector =
191             new StrongConnectivityInspector<String JavaDoc, DefaultEdge>(g);
192
193         // convert from List to Set because we need to ignore order
194
// during comparison
195
Set<Set<String JavaDoc>> actualSets =
196             new HashSet<Set<String JavaDoc>>(inspector.stronglyConnectedSets());
197
198         // construct the expected answer
199
Set<Set<String JavaDoc>> expectedSets = new HashSet<Set<String JavaDoc>>();
200         Set<String JavaDoc> set = new HashSet<String JavaDoc>();
201         set.add(V1);
202         set.add(V2);
203         expectedSets.add(set);
204         set = new HashSet<String JavaDoc>();
205         set.add(V3);
206         expectedSets.add(set);
207         set = new HashSet<String JavaDoc>();
208         set.add(V4);
209         expectedSets.add(set);
210
211         assertEquals(expectedSets, actualSets);
212
213         actualSets.clear();
214
215         List<DirectedSubgraph<String JavaDoc, DefaultEdge>> subgraphs =
216             inspector.stronglyConnectedSubgraphs();
217         for (DirectedSubgraph<String JavaDoc, DefaultEdge> sg : subgraphs) {
218             actualSets.add(sg.vertexSet());
219
220             StrongConnectivityInspector<String JavaDoc, DefaultEdge> ci =
221                 new StrongConnectivityInspector<String JavaDoc, DefaultEdge>(sg);
222             assertTrue(ci.isStronglyConnected());
223         }
224
225         assertEquals(expectedSets, actualSets);
226     }
227
228     /**
229      * .
230      */

231     public void testStronglyConnected2()
232     {
233         DirectedGraph<String JavaDoc, DefaultEdge> g =
234             new DefaultDirectedGraph<String JavaDoc, DefaultEdge>(
235                 DefaultEdge.class);
236         g.addVertex(V1);
237         g.addVertex(V2);
238         g.addVertex(V3);
239         g.addVertex(V4);
240
241         g.addEdge(V1, V2);
242         g.addEdge(V2, V1); // strongly connected
243

244         g.addEdge(V4, V3); // only weakly connected
245
g.addEdge(V3, V2); // only weakly connected
246

247         StrongConnectivityInspector<String JavaDoc, DefaultEdge> inspector =
248             new StrongConnectivityInspector<String JavaDoc, DefaultEdge>(g);
249
250         // convert from List to Set because we need to ignore order
251
// during comparison
252
Set<Set<String JavaDoc>> actualSets =
253             new HashSet<Set<String JavaDoc>>(inspector.stronglyConnectedSets());
254
255         // construct the expected answer
256
Set<Set<String JavaDoc>> expectedSets = new HashSet<Set<String JavaDoc>>();
257         Set<String JavaDoc> set = new HashSet<String JavaDoc>();
258         set.add(V1);
259         set.add(V2);
260         expectedSets.add(set);
261         set = new HashSet<String JavaDoc>();
262         set.add(V3);
263         expectedSets.add(set);
264         set = new HashSet<String JavaDoc>();
265         set.add(V4);
266         expectedSets.add(set);
267
268         assertEquals(expectedSets, actualSets);
269
270         actualSets.clear();
271
272         List<DirectedSubgraph<String JavaDoc, DefaultEdge>> subgraphs =
273             inspector.stronglyConnectedSubgraphs();
274         for (DirectedSubgraph<String JavaDoc, DefaultEdge> sg : subgraphs) {
275             actualSets.add(sg.vertexSet());
276
277             StrongConnectivityInspector<String JavaDoc, DefaultEdge> ci =
278                 new StrongConnectivityInspector<String JavaDoc, DefaultEdge>(sg);
279             assertTrue(ci.isStronglyConnected());
280         }
281
282         assertEquals(expectedSets, actualSets);
283     }
284
285     /**
286      * .
287      */

288     public void testStronglyConnected3()
289     {
290         DirectedGraph<String JavaDoc, DefaultEdge> g =
291             new DefaultDirectedGraph<String JavaDoc, DefaultEdge>(
292                 DefaultEdge.class);
293         g.addVertex(V1);
294         g.addVertex(V2);
295         g.addVertex(V3);
296         g.addVertex(V4);
297
298         g.addEdge(V1, V2);
299         g.addEdge(V2, V3);
300         g.addEdge(V3, V1); // strongly connected
301

302         g.addEdge(V1, V4);
303         g.addEdge(V2, V4);
304         g.addEdge(V3, V4); // weakly connected
305

306         StrongConnectivityInspector<String JavaDoc, DefaultEdge> inspector =
307             new StrongConnectivityInspector<String JavaDoc, DefaultEdge>(g);
308
309         // convert from List to Set because we need to ignore order
310
// during comparison
311
Set<Set<String JavaDoc>> actualSets =
312             new HashSet<Set<String JavaDoc>>(inspector.stronglyConnectedSets());
313
314         // construct the expected answer
315
Set<Set<String JavaDoc>> expectedSets = new HashSet<Set<String JavaDoc>>();
316         Set<String JavaDoc> set = new HashSet<String JavaDoc>();
317         set.add(V1);
318         set.add(V2);
319         set.add(V3);
320         expectedSets.add(set);
321         set = new HashSet<String JavaDoc>();
322         set.add(V4);
323         expectedSets.add(set);
324
325         assertEquals(expectedSets, actualSets);
326
327         actualSets.clear();
328
329         List<DirectedSubgraph<String JavaDoc, DefaultEdge>> subgraphs =
330             inspector.stronglyConnectedSubgraphs();
331
332         for (DirectedSubgraph<String JavaDoc, DefaultEdge> sg : subgraphs) {
333             actualSets.add(sg.vertexSet());
334
335             StrongConnectivityInspector<String JavaDoc, DefaultEdge> ci =
336                 new StrongConnectivityInspector<String JavaDoc, DefaultEdge>(sg);
337             assertTrue(ci.isStronglyConnected());
338         }
339
340         assertEquals(expectedSets, actualSets);
341     }
342 }
343
Popular Tags