001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.algorithm.measure; 033 034import java.util.Arrays; 035import java.util.HashSet; 036import java.util.Iterator; 037import java.util.LinkedList; 038 039import org.graphstream.algorithm.Algorithm; 040import org.graphstream.algorithm.DynamicAlgorithm; 041import org.graphstream.algorithm.flow.EdmondsKarpAlgorithm; 042import org.graphstream.graph.Edge; 043import org.graphstream.graph.Graph; 044import org.graphstream.graph.Node; 045import org.graphstream.stream.Sink; 046import org.graphstream.stream.SinkAdapter; 047 048/** 049 * Get the vertex-connectivity of a graph. 050 * 051 * A graph is said to be k-vertex-connected (or k-connected) if the graph 052 * remains connected when you delete fewer than k vertices from the graph (from 053 * <a 054 * href="https://en.wikipedia.org/wiki/K-vertex-connected_graph">Wikipedia</a>). 055 * 056 */ 057public class ConnectivityMeasure { 058 /** 059 * Get the vertex-connectivity k of a graph such that there is a k-tuple of 060 * nodes whose removal disconnects the graph. 061 * 062 * @param g 063 * the graph 064 * @return vertex connectivity 065 */ 066 public static int getVertexConnectivity(Graph g) { 067 int previous; 068 int current = Integer.MIN_VALUE; 069 boolean isPreviousConnected; 070 boolean isCurrentConnected; 071 072 /* 073 * We start with the max degree. 074 */ 075 for (Node n : g.getEachNode()) 076 current = Math.max(current, n.getDegree()); 077 078 isCurrentConnected = isKVertexConnected(g, current); 079 080 do { 081 isPreviousConnected = isCurrentConnected; 082 previous = current; 083 084 if (isPreviousConnected) 085 current = previous + 1; 086 else 087 current = previous - 1; 088 089 isCurrentConnected = isKVertexConnected(g, current); 090 } while (!((isPreviousConnected && !isCurrentConnected && previous == current - 1) || (!isPreviousConnected 091 && isCurrentConnected && previous == current + 1))); 092 093 if (!isPreviousConnected) 094 return current; 095 096 return previous; 097 } 098 099 /** 100 * Get the edge-connectivity k of a graph such that there is a k-tuple of 101 * edges whose removal disconnects the graph. This uses the Ford-Fulkerson 102 * algorithm to compute maximum flows in the graph. 103 * 104 * A simple algorithm would, for every pair (u,v), determine the maximum 105 * flow from u to v with the capacity of all edges in G set to 1 for both 106 * directions. A graph is k-edge-connected if and only if the maximum flow 107 * from u to v is at least k for any pair (u,v), so k is the least u-v-flow 108 * among all (u,v). Source <a 109 * href="https://en.wikipedia.org/wiki/K-edge-connected_graph" 110 * >Wikipedia</a>. 111 * 112 * @param g 113 * the graph 114 * @return edge connectivity 115 */ 116 public static int getEdgeConnectivity(Graph g) { 117 int k = Integer.MAX_VALUE; 118 EdmondsKarpAlgorithm flow = new EdmondsKarpAlgorithm(); 119 120 if (g.getNodeCount() < 2) 121 return 0; 122 123 for (int u = 0; u < g.getNodeCount() - 1; u++) { 124 for (int v = u + 1; v < g.getNodeCount(); v++) { 125 flow.init(g, g.getNode(u).getId(), g.getNode(v).getId()); 126 flow.setAllCapacities(1.0); 127 flow.compute(); 128 129 k = Math.min(k, (int) flow.getMaximumFlow()); 130 } 131 } 132 133 return k; 134 } 135 136 /** 137 * Check if a graph is k-vertex-connected, ie. there is no (k-1)-node-tuple 138 * such that the removal of these nodes leads to disconnect the graph. 139 * 140 * @param g 141 * the graph 142 * @param k 143 * connectivity being checked 144 * @return true if g is k-vertex-connected 145 */ 146 public static boolean isKVertexConnected(Graph g, int k) { 147 Node[] tuple = getKDisconnectingNodeTuple(g, k - 1); 148 return tuple == null; 149 } 150 151 /** 152 * Check if a graph is k-edge-connected, ie. there is no (k-1)-edge-tuple 153 * such that the removal of these edges leads to disconnect the graph. 154 * 155 * @param g 156 * the graph 157 * @param k 158 * connectivity being checked 159 * @return true if g is k-edge-connected 160 */ 161 public static boolean isKEdgeConnected(Graph g, int k) { 162 Edge[] tuple = getKDisconnectingEdgeTuple(g, k - 1); 163 return tuple == null; 164 } 165 166 /** 167 * Get a k-tuple of nodes whose removal causes the disconnection of the 168 * graph. 169 * 170 * @param g 171 * the graph 172 * @param k 173 * max size of the required tuple 174 * @return a k-tuple of nodes or null if graph is (k+1)-vertex-connected 175 */ 176 public static Node[] getKDisconnectingNodeTuple(Graph g, int k) { 177 LinkedList<Integer> toVisit = new LinkedList<Integer>(); 178 boolean[] visited = new boolean[g.getNodeCount()]; 179 HashSet<Integer> removed = new HashSet<Integer>(); 180 KIndexesArray karray = new KIndexesArray(k, g.getNodeCount()); 181 182 if (k >= g.getNodeCount()) 183 return g.getNodeSet().toArray(new Node[g.getNodeCount()]); 184 185 do { 186 toVisit.clear(); 187 removed.clear(); 188 Arrays.fill(visited, false); 189 190 for (int j = 0; j < k; j++) 191 removed.add(karray.get(j)); 192 193 for (int j = 0; toVisit.size() == 0; j++) 194 if (!removed.contains(j)) 195 toVisit.add(j); 196 197 while (toVisit.size() > 0) { 198 Node n = g.getNode(toVisit.poll()); 199 Iterator<Node> it = n.getNeighborNodeIterator(); 200 Integer index; 201 202 visited[n.getIndex()] = true; 203 204 while (it.hasNext()) { 205 Node o = it.next(); 206 index = o.getIndex(); 207 208 if (!visited[index] && !toVisit.contains(index) 209 && !removed.contains(index)) 210 toVisit.add(index); 211 } 212 } 213 214 for (int i = 0; i < visited.length; i++) 215 if (!visited[i] && !removed.contains(i)) { 216 Node[] tuple = new Node[k]; 217 218 for (int j = 0; j < k; j++) 219 tuple[j] = g.getNode(karray.get(j)); 220 221 return tuple; 222 } 223 } while (karray.next()); 224 225 return null; 226 } 227 228 /** 229 * Get a k-tuple of edges whose removal causes the disconnection of the 230 * graph. 231 * 232 * @param g 233 * the graph 234 * @param k 235 * max size of the required tuple 236 * @return a k-tuple of edges or null if graph is (k+1)-edge-connected 237 */ 238 public static Edge[] getKDisconnectingEdgeTuple(Graph g, int k) { 239 LinkedList<Integer> toVisit = new LinkedList<Integer>(); 240 boolean[] visited = new boolean[g.getNodeCount()]; 241 HashSet<Integer> removed = new HashSet<Integer>(); 242 KIndexesArray karray = new KIndexesArray(k, g.getNodeCount()); 243 244 int minDegree = Integer.MAX_VALUE; 245 Node nodeWithMinDegree = null; 246 247 if (k >= g.getEdgeCount()) 248 return g.getEdgeSet().toArray(new Edge[g.getEdgeCount()]); 249 250 for (int i = 0; i < g.getNodeCount(); i++) { 251 Node n = g.getNode(i); 252 253 if (n.getDegree() < minDegree) { 254 minDegree = n.getDegree(); 255 nodeWithMinDegree = n; 256 } 257 } 258 259 if (k > minDegree) { 260 Edge[] tuple = new Edge[minDegree]; 261 262 for (int i = 0; i < minDegree; i++) 263 tuple[i] = nodeWithMinDegree.getEdge(i); 264 265 return tuple; 266 } 267 268 do { 269 toVisit.clear(); 270 removed.clear(); 271 Arrays.fill(visited, false); 272 273 for (int j = 0; j < k; j++) 274 removed.add(karray.get(j)); 275 276 toVisit.add(0); 277 278 while (toVisit.size() > 0) { 279 Node n = g.getNode(toVisit.poll()); 280 Iterator<Edge> it = n.iterator(); 281 Integer index; 282 283 visited[n.getIndex()] = true; 284 285 while (it.hasNext()) { 286 Edge e = it.next(); 287 Node o = e.getOpposite(n); 288 index = o.getIndex(); 289 290 if (!visited[index] && !toVisit.contains(index) 291 && !removed.contains(e.getIndex())) 292 toVisit.add(index); 293 } 294 } 295 296 for (int i = 0; i < visited.length; i++) 297 if (!visited[i]) { 298 Edge[] tuple = new Edge[k]; 299 300 for (int j = 0; j < k; j++) 301 tuple[j] = g.getEdge(karray.get(j)); 302 303 return tuple; 304 } 305 } while (karray.next()); 306 307 return null; 308 } 309 310 private static class KIndexesArray { 311 final int[] data; 312 final int k, n; 313 314 public KIndexesArray(int k, int n) { 315 this.k = k; 316 this.n = n; 317 318 this.data = new int[k]; 319 320 for (int i = 0; i < k; i++) 321 this.data[i] = i; 322 } 323 324 public boolean next() { 325 int i = k - 1; 326 327 while (i >= 0 && data[i] >= n - (k - 1 - i)) 328 i--; 329 330 if (i >= 0) { 331 data[i]++; 332 333 for (int j = i + 1; j < k; j++) 334 data[j] = data[j - 1] + 1; 335 336 return true; 337 } 338 339 return false; 340 } 341 342 public int get(int i) { 343 return data[i]; 344 } 345 } 346 347 public static class VertexConnectivityMeasure implements DynamicAlgorithm { 348 protected Graph g; 349 protected int vertexConnectivity; 350 protected Sink trigger; 351 352 public VertexConnectivityMeasure() { 353 g = null; 354 vertexConnectivity = -1; 355 trigger = new StepTrigger(this); 356 } 357 358 /** 359 * Get the last vertex-connectivity of the registered graph compute in 360 * the last call of {@link #compute()}. 361 * 362 * @return vertex connectivity 363 */ 364 public int getVertexConnectivity() { 365 return vertexConnectivity; 366 } 367 368 /* 369 * (non-Javadoc) 370 * 371 * @see org.graphstream.algorithm.Algorithm#compute() 372 */ 373 public void compute() { 374 vertexConnectivity = ConnectivityMeasure.getVertexConnectivity(g); 375 } 376 377 /* 378 * (non-Javadoc) 379 * 380 * @see 381 * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph) 382 */ 383 public void init(Graph graph) { 384 g = graph; 385 g.addSink(trigger); 386 } 387 388 /* 389 * (non-Javadoc) 390 * 391 * @see org.graphstream.algorithm.DynamicAlgorithm#terminate() 392 */ 393 public void terminate() { 394 g.removeSink(trigger); 395 } 396 } 397 398 public static class EdgeConnectivityMeasure implements DynamicAlgorithm { 399 protected Graph g; 400 protected int edgeConnectivity; 401 protected Sink trigger; 402 403 public EdgeConnectivityMeasure() { 404 g = null; 405 edgeConnectivity = -1; 406 trigger = new StepTrigger(this); 407 } 408 409 /** 410 * Get the last vertex-connectivity of the registered graph compute in 411 * the last call of {@link #compute()}. 412 * 413 * @return vertex connectivity 414 */ 415 public int getEdgeConnectivity() { 416 return edgeConnectivity; 417 } 418 419 /* 420 * (non-Javadoc) 421 * 422 * @see org.graphstream.algorithm.Algorithm#compute() 423 */ 424 public void compute() { 425 edgeConnectivity = ConnectivityMeasure.getEdgeConnectivity(g); 426 } 427 428 /* 429 * (non-Javadoc) 430 * 431 * @see 432 * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph) 433 */ 434 public void init(Graph graph) { 435 g = graph; 436 g.addSink(trigger); 437 } 438 439 /* 440 * (non-Javadoc) 441 * 442 * @see org.graphstream.algorithm.DynamicAlgorithm#terminate() 443 */ 444 public void terminate() { 445 g.removeSink(trigger); 446 } 447 } 448 449 private static class StepTrigger extends SinkAdapter { 450 Algorithm algo; 451 452 StepTrigger(Algorithm algo) { 453 this.algo = algo; 454 } 455 456 public void stepBegins(String sourceId, long timeId, double step) { 457 algo.compute(); 458 } 459 } 460}