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; 033 034import java.util.ArrayList; 035import java.util.HashMap; 036import java.util.Iterator; 037import java.util.LinkedList; 038import java.util.List; 039 040import org.graphstream.graph.Edge; 041import org.graphstream.graph.Graph; 042import org.graphstream.graph.Node; 043import org.graphstream.stream.SinkAdapter; 044import org.graphstream.util.Filter; 045import org.graphstream.util.FilteredEdgeIterator; 046import org.graphstream.util.FilteredNodeIterator; 047import org.graphstream.util.Filters; 048 049//import org.graphstream.util.set.FixedArrayList; 050 051/** 052 * Compute and update the number of connected components of a dynamic graph. 053 * 054 * <p> 055 * This algorithm computes the connected components for a given graph. Connected 056 * components are the set of its connected subgraphs. Two nodes belong to the 057 * same connected component when there exists a path (without considering the 058 * direction of the edges) between them. Therefore, the algorithm does not 059 * consider the direction of the edges. The number of connected components of an 060 * undirected graph is equal to the number of connected components of the same 061 * directed graph. See <a 062 * href="http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29" 063 * >wikipedia</a> for details. 064 * </p> 065 * 066 * <h2>Dynamics</h2> 067 * 068 * <p> 069 * This algorithm tries to handle the dynamics of the graph, trying not to 070 * recompute all from scratch at each change (kind of re-optimization). In this 071 * way, each instance of the algorithm is registered as a graph sink. Each 072 * change in the graph topology may affect the algorithm. 073 * </p> 074 * 075 * <h2>Usage</h2> 076 * 077 * <p> 078 * To start using the algorithm, you first need an instance of 079 * {@link org.graphstream.graph.Graph}, then you only have to instantiate the 080 * algorithm class. Whether you specify a reference to the graph in the 081 * constructor or you set it with the {@link #init(Graph)} method. 082 * </p> 083 * 084 * <p> 085 * The computation of the algorithm starts only when the graph is specified with 086 * the {@link #init(Graph)} method or with the appropriated constructor. In case 087 * of a static graph, you may call the {@link #compute()} method. In case of a 088 * dynamic graph, the algorithm will compute itself automatically when an event 089 * (node or edge added or removed) occurs. 090 * </p> 091 * 092 * <p> 093 * Finally you may ask the algorithm for the number of connected components at 094 * any moment with a call to the {@link #getConnectedComponentsCount()} method. 095 * </p> 096 * 097 * <h2>Example</h2> 098 * 099 * <pre> 100 * import org.graphstream.algorithm.ConnectedComponents; 101 * import org.graphstream.graph.Graph; 102 * import org.graphstream.graph.implementations.DefaultGraph; 103 * 104 * public class CCTest { 105 * public static void main(String[] args) { 106 * 107 * Graph graph = new DefaultGraph("CC Test"); 108 * 109 * graph.addNode("A"); 110 * graph.addNode("B"); 111 * graph.addNode("C"); 112 * graph.addEdge("AB", "A", "B"); 113 * graph.addEdge("AC", "A", "C"); 114 * 115 * ConnectedComponents cc = new ConnectedComponents(); 116 * cc.init(graph); 117 * 118 * System.out.printf("%d connected component(s) in this graph, so far.%n", 119 * cc.getConnectedComponentsCount()); 120 * 121 * graph.removeEdge("AC"); 122 * 123 * System.out.printf("Eventually, there are %d.%n", cc 124 * .getConnectedComponentsCount()); 125 * 126 * } 127 * } 128 * </pre> 129 * 130 * <h2>Additional features</h2> 131 * 132 * 133 * <h3>Threshold and Ceiling</h3> 134 * <p> 135 * It is possible to get rid of connected components belong a size threshold 136 * when counting the overall number of connected components. It is also possible 137 * to define a ceiling size for the connected component. Above that size 138 * ceiling, connected components will not be counted. Use the 139 * {@link #getConnectedComponentsCount(int)} or 140 * {@link #getConnectedComponentsCount(int, int)} methods. 141 * </p> 142 * 143 * <h3>Components Identifiers</h3> 144 * <p> 145 * You can tag each node with an integer that identifies the component it 146 * pertains to using {@link #setCountAttribute(String)}. The argument of this 147 * method is an arbitrary name that will be used as attribute on each node of 148 * the graph. The value of this attribute will be an integer (counting from 149 * zero) that is different for each connected component. 150 * </p> 151 * 152 * <h3>Giant component</h3> 153 * <p> 154 * The {@link #getGiantComponent()} method gives you a list of nodes belonging 155 * to the biggest connected component of the graph. 156 * </p> 157 * 158 * <h3>Cut Attribute</h3> 159 * <p> 160 * The cut attribute is a feature that can optionally simulate a given edge to 161 * be invisible (as if the edge did not exist). In other words if an edge is 162 * given such a cut attribute, it will be ignored by the algorithm when 163 * counting. You can enable (or disable by passing null) the cut attribute by 164 * specifying it with the {@link #setCutAttribute(String)} method, and by giving 165 * the special edges the same attribute. 166 * </p> 167 * <p> 168 * What is it useful for? Well you may want to simulate the removal of a given 169 * edge and see if it increases the number of connected components. You may not 170 * want to really remove and then re-add that edge in the graph, because such 171 * removal event may have consequences on other algorithms, viewer, writers... 172 * </p> 173 * <p> 174 * Note that setting the cut attribute will trigger a new computation of the 175 * algorithm. 176 * </p> 177 * 178 * @author Yoann Pigné 179 * @author Antoine Dutot 180 * @author Guillaume-Jean Herbiet 181 * 182 * @since June 26 2007 183 * 184 * @complexity For the initial computation, let n be the number of nodes, then 185 * the complexity is 0(n). For the re-optimization steps, let k be 186 * the number of nodes concerned by the changes (k <= n), the 187 * complexity is O(k). 188 */ 189public class ConnectedComponents extends SinkAdapter implements 190 DynamicAlgorithm, Iterable<ConnectedComponents.ConnectedComponent> { 191 192 /** 193 * Map of connected components. 194 */ 195 private HashMap<Node, Integer> connectedComponentsMap; 196 197 /** 198 * The Graph the algorithm is working on. 199 */ 200 protected Graph graph; 201 202 /** 203 * The number of connected components 204 */ 205 protected int connectedComponents = 0; 206 207 /** 208 * Size of each connected component 209 */ 210 protected HashMap<Integer, Integer> connectedComponentsSize; 211 212 /** 213 * Single IDs to identify the connected components. 214 */ 215 protected FixedArrayList<String> ids = new FixedArrayList<String>(); 216 217 protected FixedArrayList<ConnectedComponent> components = new FixedArrayList<ConnectedComponent>(); 218 219 /** 220 * A token to decide whether or not the algorithm is started. 221 */ 222 protected boolean started = false; 223 224 /** 225 * Optional edge attribute that make it "invisible". The algorithm will find 226 * two connected components if such an edge is the only link between two 227 * node groups. 228 */ 229 protected String cutAttribute = null; 230 231 /** 232 * Optional attribute to set on each node of a given component. This 233 * attribute will have for value an index different for each component. 234 */ 235 protected String countAttribute = null; 236 237 /** 238 * Construction of an instance with no parameter. The process is not 239 * initialized and the algorithm will not receive any event from any graph. 240 * You will have to call the {@link #init(Graph)} method with a reference to 241 * a graph so that the computation is able to start. 242 * 243 * After the {@link #init(Graph)} method is invoked, the computation starts 244 * as soon as and event is received or if the {@link #compute()} method is 245 * invoked. 246 */ 247 public ConnectedComponents() { 248 this(null); 249 } 250 251 /** 252 * Constructor with the given graph. The computation of the algorithm start 253 * only when the {@link #init(Graph)} method is invoked. This Constructor 254 * will call the {@link #init(Graph)} method anyway. 255 * 256 * @param graph 257 * The graph who's connected components will be computed. 258 */ 259 public ConnectedComponents(Graph graph) { 260 ids.add(""); // The dummy first identifier (since zero is a special 261 // value). 262 263 if (graph != null) 264 init(graph); 265 } 266 267 /** 268 * Computes a list of nodes that belong to the biggest connected component. 269 * 270 * @return nodes of the biggest CC. 271 */ 272 public List<Node> getGiantComponent() { 273 if (!started) { 274 compute(); 275 } 276 277 // Get the biggest component 278 int maxSize = Integer.MIN_VALUE; 279 int maxIndex = -1; 280 for (Integer c : connectedComponentsSize.keySet()) { 281 if (connectedComponentsSize.get(c) > maxSize) { 282 maxSize = connectedComponentsSize.get(c); 283 maxIndex = c; 284 } 285 } 286 // Get the list of nodes within this component 287 if (maxIndex != -1) { 288 ArrayList<Node> giant = new ArrayList<Node>(); 289 for (Node n : graph.getNodeSet()) { 290 if (connectedComponentsMap.get(n) == maxIndex) { 291 giant.add(n); 292 } 293 } 294 return giant; 295 } else { 296 return null; 297 } 298 } 299 300 /** 301 * Ask the algorithm for the number of connected components. 302 * 303 * @return the number of connected components in this graph. 304 */ 305 public int getConnectedComponentsCount() { 306 return getConnectedComponentsCount(1); 307 } 308 309 /** 310 * Ask the algorithm for the number of connected components whose size is 311 * equal to or greater than the specified threshold. 312 * 313 * @param sizeThreshold 314 * Minimum size for the connected component to be considered 315 * 316 * @return the number of connected components, bigger than the given size 317 * threshold, in this graph. 318 */ 319 public int getConnectedComponentsCount(int sizeThreshold) { 320 return getConnectedComponentsCount(sizeThreshold, 0); 321 } 322 323 /** 324 * Ask the algorithm for the number of connected components whose size is 325 * equal to or greater than the specified threshold and lesser than the 326 * specified ceiling. 327 * 328 * @param sizeThreshold 329 * Minimum size for the connected component to be considered 330 * @param sizeCeiling 331 * Maximum size for the connected component to be considered (use 332 * 0 or lower values to ignore the ceiling) 333 * 334 * @return the number of connected components, bigger than the given size 335 * threshold, and smaller than the given size ceiling, in this 336 * graph. 337 */ 338 public int getConnectedComponentsCount(int sizeThreshold, int sizeCeiling) { 339 if (!started) { 340 compute(); 341 } 342 343 // Simplest case : threshold is lesser than or equal to 1 and 344 // no ceiling is specified, we return all the counted components 345 if (sizeThreshold <= 1 && sizeCeiling <= 0) { 346 return connectedComponents; 347 } 348 349 // Otherwise, parse the connected components size map to consider only 350 // the components whose size is in [sizeThreshold ; sizeCeiling [ 351 else { 352 int count = 0; 353 for (Integer c : connectedComponentsSize.keySet()) { 354 if (connectedComponentsSize.get(c) >= sizeThreshold 355 && (sizeCeiling <= 0 || connectedComponentsSize.get(c) < sizeCeiling)) { 356 count++; 357 } 358 } 359 return count; 360 } 361 } 362 363 public Iterator<ConnectedComponent> iterator() { 364 while (components.size() > connectedComponents) 365 components.remove(components.getLastIndex()); 366 367 return components.iterator(); 368 } 369 370 /** 371 * Allocate a new identifier for a connected component. 372 * 373 * @return The new component identifier. 374 */ 375 protected int addIdentifier() { 376 ids.add(""); 377 return ids.getLastIndex(); 378 } 379 380 /** 381 * Remove a identifier that is no more used. 382 * 383 * @param identifier 384 * The identifier to remove. 385 */ 386 protected void removeIdentifier(int identifier) { 387 /* 388 * // Eventual verification to ensure no used identifier is removed. 389 * 390 * for( Node node: graph.getNodeSet() ) { if( 391 * connectedComponentsMap.get( node ) == identifier ) System.err.printf( 392 * " **** ID %d STILL USED BY node %s%n", identifier, node.getId() 393 * ); } 394 */ 395 ids.remove(identifier); 396 } 397 398 /** 399 * Enable (or disable by passing null) an optional attribute that makes 400 * edges that have it invisible (as if the edge did not existed). Be 401 * careful, setting the cut attribute will trigger a new computation of the 402 * algorithm. 403 * 404 * @param cutAttribute 405 * The name for the cut attribute or null if the cut attribute 406 * option must be disabled. 407 */ 408 public void setCutAttribute(String cutAttribute) { 409 this.cutAttribute = cutAttribute; 410 411 compute(); 412 } 413 414 /** 415 * Enable (or disable by passing null for countAttribute) an optional 416 * attribute that will be assigned to each node. The value of this attribute 417 * will be an integer different for each computed component. 418 * 419 * @param countAttribute 420 * The name of the attribute to put on each node (pass null to 421 * disable this feature). 422 */ 423 public void setCountAttribute(String countAttribute) { 424 removeMarks(); 425 this.countAttribute = countAttribute; 426 remapMarks(); 427 } 428 429 protected void removeMarks() { 430 Iterator<? extends Node> nodes = graph.getNodeIterator(); 431 432 while (nodes.hasNext()) { 433 Node node = nodes.next(); 434 435 if (countAttribute == null) 436 node.removeAttribute(countAttribute); 437 } 438 } 439 440 protected void remapMarks() { 441 442 if (countAttribute != null && connectedComponentsMap != null) { 443 Iterator<? extends Node> nodes = graph.getNodeIterator(); 444 445 while (nodes.hasNext()) { 446 Node v = nodes.next(); 447 int id = connectedComponentsMap.get(v); 448 449 v.addAttribute(countAttribute, id - 1); 450 } 451 } 452 } 453 454 /* 455 * (non-Javadoc) 456 * 457 * @see 458 * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph) 459 */ 460 public void init(Graph graph) { 461 if (this.graph != null) 462 this.graph.removeSink(this); 463 464 this.graph = graph; 465 466 this.graph.addSink(this); 467 } 468 469 /* 470 * (non-Javadoc) 471 * 472 * @see org.graphstream.algorithm.Algorithm#compute() 473 */ 474 public void compute() { 475 connectedComponents = 0; 476 started = true; 477 478 ids.clear(); 479 ids.add(""); // The dummy first identifier (since zero is a special 480 // value). 481 components.add(new ConnectedComponent(0)); 482 483 connectedComponentsMap = new HashMap<Node, Integer>(); 484 485 // Initialize the size count structure 486 connectedComponentsSize = new HashMap<Integer, Integer>(); 487 488 Iterator<? extends Node> nodes = graph.getNodeIterator(); 489 490 while (nodes.hasNext()) { 491 connectedComponentsMap.put(nodes.next(), 0); 492 } 493 494 nodes = graph.getNodeIterator(); 495 496 while (nodes.hasNext()) { 497 Node v = nodes.next(); 498 499 if (connectedComponentsMap.get(v) == 0) { 500 connectedComponents++; 501 502 int newIdentifier = addIdentifier(); 503 int size = computeConnectedComponent(v, newIdentifier, null); 504 505 if (size > 0) 506 components.add(new ConnectedComponent(newIdentifier)); 507 508 // Initial size count of all connected components 509 connectedComponentsSize.put(newIdentifier, size); 510 } 511 } 512 513 remapMarks(); 514 } 515 516 /* 517 * (non-Javadoc) 518 * 519 * @see org.graphstream.algorithm.DynamicAlgorithm#terminate() 520 */ 521 public void terminate() { 522 if (graph != null) { 523 graph.removeSink(this); 524 525 graph = null; 526 started = false; 527 528 connectedComponents = 0; 529 connectedComponentsSize.clear(); 530 } 531 } 532 533 /** 534 * Goes recursively (depth first) into the connected component and assigns 535 * each node an id. 536 * 537 * @param v 538 * The considered node. 539 * @param id 540 * The id to assign to the given node. 541 * @param exception 542 * An optional edge that may not be considered (useful when 543 * receiving a {@link #edgeRemoved(String, long, String)} event. 544 * @return size The size (number of elements) of the connected component 545 */ 546 private int computeConnectedComponent(Node v, int id, Edge exception) { 547 int size = 0; 548 549 LinkedList<Node> open = new LinkedList<Node>(); 550 551 open.add(v); 552 553 while (!open.isEmpty()) { 554 Node n = open.remove(); 555 556 connectedComponentsMap.put(n, id); 557 size++; 558 559 markNode(n, id); 560 561 Iterator<? extends Edge> edges = n.getEdgeIterator(); 562 563 while (edges.hasNext()) { 564 Edge e = edges.next(); 565 566 if (e != exception) { 567 if ((cutAttribute != null) ? (!e.hasAttribute(cutAttribute)) 568 : true) { 569 Node n2 = e.getOpposite(n); 570 571 if (connectedComponentsMap.get(n2) != id) { 572 open.add(n2); 573 connectedComponentsMap.put(n2, id); 574 markNode(n2, id); /* useless */ 575 } 576 // Also work with (but slower): 577 /* 578 * if( connectedComponentsMap.get( n2 ) != id && ! 579 * open.contains(n2) ) { open.add( n2 ); } 580 */ 581 582 } 583 } 584 } 585 } 586 return size; 587 } 588 589 protected void markNode(Node node, int id) { 590 if (countAttribute != null) { 591 node.addAttribute(countAttribute, id - 1); 592 } 593 } 594 595 /* 596 * (non-Javadoc) 597 * 598 * @see org.graphstream.stream.SinkAdapter#edgeAdded(java.lang.String, long, 599 * java.lang.String, java.lang.String, java.lang.String, boolean) 600 */ 601 @Override 602 public void edgeAdded(String graphId, long timeId, String edgeId, 603 String fromNodeId, String toNodeId, boolean directed) { 604 if (!started && graph != null) { 605 compute(); 606 } else if (started) { 607 Edge edge = graph.getEdge(edgeId); 608 609 if (edge != null) { 610 if (!(connectedComponentsMap.get(edge.getNode0()) 611 .equals(connectedComponentsMap.get(edge.getNode1())))) { 612 connectedComponents--; 613 614 int id0 = connectedComponentsMap.get(edge.getNode0()); 615 int id1 = connectedComponentsMap.get(edge.getNode1()); 616 617 computeConnectedComponent(edge.getNode1(), id0, edge); 618 removeIdentifier(id1); 619 620 // Merge the size of the two connected components 621 // and remove the entry for the dismissed identifier 622 connectedComponentsSize.put(id0, connectedComponentsSize 623 .get(id0) 624 + connectedComponentsSize.get(id1)); 625 connectedComponentsSize.remove(id1); 626 } 627 } 628 } 629 } 630 631 /* 632 * (non-Javadoc) 633 * 634 * @see org.graphstream.stream.SinkAdapter#nodeAdded(java.lang.String, long, 635 * java.lang.String) 636 */ 637 @Override 638 public void nodeAdded(String graphId, long timeId, String nodeId) { 639 if (!started && graph != null) { 640 compute(); 641 } else if (started) { 642 Node node = graph.getNode(nodeId); 643 644 if (node != null) { 645 connectedComponents++; 646 647 int id = addIdentifier(); 648 649 connectedComponentsMap.put(node, id); 650 markNode(node, id); 651 652 // Node is a new connected component 653 connectedComponentsSize.put(id, 1); 654 } 655 } 656 } 657 658 /* 659 * (non-Javadoc) 660 * 661 * @see org.graphstream.stream.SinkAdapter#edgeRemoved(java.lang.String, 662 * long, java.lang.String) 663 */ 664 @Override 665 public void edgeRemoved(String graphId, long timeId, String edgeId) { 666 if (!started && graph != null) { 667 compute(); 668 } 669 670 if (started) { 671 Edge edge = graph.getEdge(edgeId); 672 673 if (edge != null) { 674 int id = addIdentifier(); 675 int oldId = connectedComponentsMap.get(edge.getNode0()); 676 677 // Get the size of the "old" component 678 int oldSize = connectedComponentsSize.get(oldId); 679 int newSize = computeConnectedComponent(edge.getNode0(), id, 680 edge); 681 682 if (!(connectedComponentsMap.get(edge.getNode0()) 683 .equals(connectedComponentsMap.get(edge.getNode1())))) { 684 685 // Two new connected components are created 686 // we need to get the size of each of them 687 if (newSize > 0) { 688 connectedComponentsSize.put(id, newSize); 689 connectedComponents++; 690 } 691 692 if (oldSize - newSize > 0) { 693 connectedComponentsSize.put(oldId, oldSize - newSize); 694 695 } else { 696 connectedComponentsSize.remove(oldId); 697 connectedComponents--; 698 } 699 700 } else { 701 removeIdentifier(oldId); 702 703 // No new connected component, simply "translate" the entry 704 connectedComponentsSize.put(id, connectedComponentsSize 705 .get(oldId)); 706 connectedComponentsSize.remove(oldId); 707 708 } 709 } 710 } 711 } 712 713 /* 714 * (non-Javadoc) 715 * 716 * @see org.graphstream.stream.SinkAdapter#nodeRemoved(java.lang.String, 717 * long, java.lang.String) 718 */ 719 @Override 720 public void nodeRemoved(String graphId, long timeId, String nodeId) { 721 if (!started && graph != null) { 722 compute(); 723 } 724 725 if (started) { 726 Node node = graph.getNode(nodeId); 727 728 if (node != null) { 729 730 // Delete the entry corresponding to this node 731 connectedComponentsSize 732 .remove(connectedComponentsMap.get(node)); 733 734 connectedComponents--; 735 removeIdentifier(connectedComponentsMap.get(node)); 736 } 737 } 738 } 739 740 /* 741 * (non-Javadoc) 742 * 743 * @see org.graphstream.stream.SinkAdapter#graphCleared(java.lang.String, 744 * long) 745 */ 746 @Override 747 public void graphCleared(String graphId, long timeId) { 748 // terminate(); 749 if (started) { 750 connectedComponents = 0; 751 ids.clear(); 752 ids.add(""); 753 components.clear(); 754 components.add(new ConnectedComponent(0)); 755 756 connectedComponentsMap.clear(); 757 connectedComponentsSize.clear(); 758 } 759 } 760 761 /* 762 * (non-Javadoc) 763 * 764 * @see 765 * org.graphstream.stream.SinkAdapter#edgeAttributeAdded(java.lang.String, 766 * long, java.lang.String, java.lang.String, java.lang.Object) 767 */ 768 @Override 769 public void edgeAttributeAdded(String graphId, long timeId, String edgeId, 770 String attribute, Object value) { 771 if (cutAttribute != null && attribute.equals(cutAttribute)) { 772 if (!started && graph != null) 773 compute(); 774 775 Edge edge = graph.getEdge(edgeId); 776 777 // The attribute is added. Do as if the edge was removed. 778 779 int id = addIdentifier(); 780 int oldId = connectedComponentsMap.get(edge.getNode0()); 781 782 // Get the size of the "old" component 783 int oldSize = connectedComponentsSize.get(oldId); 784 int newSize = computeConnectedComponent(edge.getNode0(), id, edge); 785 786 if (!connectedComponentsMap.get(edge.getNode0()).equals( 787 connectedComponentsMap.get(edge.getNode1()))) { 788 789 // Two new connected components are created 790 // we need to get the size of each of them 791 if (newSize > 0) { 792 connectedComponentsSize.put(id, newSize); 793 connectedComponents++; 794 } 795 796 if (oldSize - newSize > 0) { 797 connectedComponentsSize.put(oldId, oldSize - newSize); 798 799 } else { 800 connectedComponentsSize.remove(oldId); 801 connectedComponents--; 802 } 803 804 } else { 805 removeIdentifier(oldId); 806 807 // No new connected component, simply "translate" the entry 808 connectedComponentsSize.put(id, connectedComponentsSize 809 .get(oldId)); 810 connectedComponentsSize.remove(oldId); 811 } 812 } 813 } 814 815 /* 816 * (non-Javadoc) 817 * 818 * @see 819 * org.graphstream.stream.SinkAdapter#edgeAttributeRemoved(java.lang.String, 820 * long, java.lang.String, java.lang.String) 821 */ 822 @Override 823 public void edgeAttributeRemoved(String graphId, long timeId, 824 String edgeId, String attribute) { 825 if (cutAttribute != null && attribute.equals(cutAttribute)) { 826 if (!started && graph != null) 827 compute(); 828 829 Edge edge = graph.getEdge(edgeId); 830 831 // The attribute is removed. Do as if the edge was added. 832 833 if (!(connectedComponentsMap.get(edge.getNode0()) 834 .equals(connectedComponentsMap.get(edge.getNode1())))) { 835 connectedComponents--; 836 837 int id0 = connectedComponentsMap.get(edge.getNode0()); 838 int id1 = connectedComponentsMap.get(edge.getNode1()); 839 840 computeConnectedComponent(edge.getNode1(), id0, edge); 841 removeIdentifier(id1); 842 843 // Merge the size of the two connected components 844 // and remove the entry for the dismissed identifier 845 connectedComponentsSize.put(id0, connectedComponentsSize 846 .get(id0) 847 + connectedComponentsSize.get(id1)); 848 connectedComponentsSize.remove(id1); 849 } 850 } 851 } 852 853 public class ConnectedComponent implements Iterable<Node> { 854 public final Integer id; 855 Filter<Node> nodeFilter; 856 Filter<Edge> edgeFilter; 857 Iterable<Edge> eachEdge; 858 859 public ConnectedComponent(Integer id) { 860 this.id = id; 861 this.nodeFilter = null; 862 this.edgeFilter = null; 863 this.eachEdge = null; 864 } 865 866 public Iterator<Node> iterator() { 867 if (nodeFilter == null) 868 nodeFilter = Filters.byAttributeFilter(countAttribute, id); 869 870 return new FilteredNodeIterator<Node>(graph, nodeFilter); 871 } 872 873 public Iterable<Node> getEachNode() { 874 return this; 875 } 876 877 public Iterable<Edge> getEachEdge() { 878 if (eachEdge == null) { 879 eachEdge = new Iterable<Edge>() { 880 public Iterator<Edge> iterator() { 881 return getEdgeIterator(); 882 } 883 }; 884 } 885 886 return eachEdge; 887 } 888 889 public Iterator<Edge> getEdgeIterator() { 890 if (edgeFilter == null) { 891 if (nodeFilter == null) 892 nodeFilter = Filters.byAttributeFilter(countAttribute, id); 893 894 edgeFilter = new EdgeFilter(nodeFilter); 895 } 896 897 return new FilteredEdgeIterator<Edge>(graph, edgeFilter); 898 } 899 } 900 901 private static class EdgeFilter implements Filter<Edge> { 902 Filter<Node> f; 903 904 public EdgeFilter(Filter<Node> f) { 905 this.f = f; 906 } 907 908 public boolean isAvailable(Edge e) { 909 return f.isAvailable(e.getNode0()) && f.isAvailable(e.getNode1()); 910 } 911 } 912}