1 25 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 56 public class ConnectivityInspectorTest 57 extends TestCase 58 { 59 60 62 private static final String V1 = "v1"; 63 private static final String V2 = "v2"; 64 private static final String V3 = "v3"; 65 private static final String V4 = "v4"; 66 67 69 DefaultEdge e1; 71 DefaultEdge e2; 72 DefaultEdge e3; 73 DefaultEdge e3_b; 74 DefaultEdge u; 75 76 78 83 public Pseudograph<String , DefaultEdge> create() 84 { 85 Pseudograph<String , DefaultEdge> g = 86 new Pseudograph<String , 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 124 public void testDirectedGraph() 125 { 126 ListenableDirectedGraph<String , DefaultEdge> g = 127 new ListenableDirectedGraph<String , 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 , DefaultEdge> inspector = 136 new ConnectivityInspector<String , 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 149 public void testIsGraphConnected() 150 { 151 Pseudograph<String , DefaultEdge> g = create(); 152 ConnectivityInspector<String , DefaultEdge> inspector = 153 new ConnectivityInspector<String , DefaultEdge>(g); 154 155 assertEquals(false, inspector.isGraphConnected()); 156 157 g.removeVertex(V4); 158 inspector = new ConnectivityInspector<String , 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 , DefaultEdge>(g); 169 assertEquals(false, inspector.isGraphConnected()); 170 } 171 172 175 public void testStronglyConnected1() 176 { 177 DirectedGraph<String , DefaultEdge> g = 178 new DefaultDirectedGraph<String , 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); 188 g.addEdge(V3, V4); 190 StrongConnectivityInspector<String , DefaultEdge> inspector = 191 new StrongConnectivityInspector<String , DefaultEdge>(g); 192 193 Set<Set<String >> actualSets = 196 new HashSet<Set<String >>(inspector.stronglyConnectedSets()); 197 198 Set<Set<String >> expectedSets = new HashSet<Set<String >>(); 200 Set<String > set = new HashSet<String >(); 201 set.add(V1); 202 set.add(V2); 203 expectedSets.add(set); 204 set = new HashSet<String >(); 205 set.add(V3); 206 expectedSets.add(set); 207 set = new HashSet<String >(); 208 set.add(V4); 209 expectedSets.add(set); 210 211 assertEquals(expectedSets, actualSets); 212 213 actualSets.clear(); 214 215 List<DirectedSubgraph<String , DefaultEdge>> subgraphs = 216 inspector.stronglyConnectedSubgraphs(); 217 for (DirectedSubgraph<String , DefaultEdge> sg : subgraphs) { 218 actualSets.add(sg.vertexSet()); 219 220 StrongConnectivityInspector<String , DefaultEdge> ci = 221 new StrongConnectivityInspector<String , DefaultEdge>(sg); 222 assertTrue(ci.isStronglyConnected()); 223 } 224 225 assertEquals(expectedSets, actualSets); 226 } 227 228 231 public void testStronglyConnected2() 232 { 233 DirectedGraph<String , DefaultEdge> g = 234 new DefaultDirectedGraph<String , 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); 244 g.addEdge(V4, V3); g.addEdge(V3, V2); 247 StrongConnectivityInspector<String , DefaultEdge> inspector = 248 new StrongConnectivityInspector<String , DefaultEdge>(g); 249 250 Set<Set<String >> actualSets = 253 new HashSet<Set<String >>(inspector.stronglyConnectedSets()); 254 255 Set<Set<String >> expectedSets = new HashSet<Set<String >>(); 257 Set<String > set = new HashSet<String >(); 258 set.add(V1); 259 set.add(V2); 260 expectedSets.add(set); 261 set = new HashSet<String >(); 262 set.add(V3); 263 expectedSets.add(set); 264 set = new HashSet<String >(); 265 set.add(V4); 266 expectedSets.add(set); 267 268 assertEquals(expectedSets, actualSets); 269 270 actualSets.clear(); 271 272 List<DirectedSubgraph<String , DefaultEdge>> subgraphs = 273 inspector.stronglyConnectedSubgraphs(); 274 for (DirectedSubgraph<String , DefaultEdge> sg : subgraphs) { 275 actualSets.add(sg.vertexSet()); 276 277 StrongConnectivityInspector<String , DefaultEdge> ci = 278 new StrongConnectivityInspector<String , DefaultEdge>(sg); 279 assertTrue(ci.isStronglyConnected()); 280 } 281 282 assertEquals(expectedSets, actualSets); 283 } 284 285 288 public void testStronglyConnected3() 289 { 290 DirectedGraph<String , DefaultEdge> g = 291 new DefaultDirectedGraph<String , 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); 302 g.addEdge(V1, V4); 303 g.addEdge(V2, V4); 304 g.addEdge(V3, V4); 306 StrongConnectivityInspector<String , DefaultEdge> inspector = 307 new StrongConnectivityInspector<String , DefaultEdge>(g); 308 309 Set<Set<String >> actualSets = 312 new HashSet<Set<String >>(inspector.stronglyConnectedSets()); 313 314 Set<Set<String >> expectedSets = new HashSet<Set<String >>(); 316 Set<String > set = new HashSet<String >(); 317 set.add(V1); 318 set.add(V2); 319 set.add(V3); 320 expectedSets.add(set); 321 set = new HashSet<String >(); 322 set.add(V4); 323 expectedSets.add(set); 324 325 assertEquals(expectedSets, actualSets); 326 327 actualSets.clear(); 328 329 List<DirectedSubgraph<String , DefaultEdge>> subgraphs = 330 inspector.stronglyConnectedSubgraphs(); 331 332 for (DirectedSubgraph<String , DefaultEdge> sg : subgraphs) { 333 actualSets.add(sg.vertexSet()); 334 335 StrongConnectivityInspector<String , DefaultEdge> ci = 336 new StrongConnectivityInspector<String , DefaultEdge>(sg); 337 assertTrue(ci.isStronglyConnected()); 338 } 339 340 assertEquals(expectedSets, actualSets); 341 } 342 } 343 | Popular Tags |