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.*; 035 036import org.graphstream.algorithm.util.RandomTools; 037import org.graphstream.graph.*; 038import org.graphstream.stream.GraphReplay; 039import org.graphstream.ui.layout.Layout; 040import org.graphstream.ui.layout.springbox.implementations.SpringBox; 041 042/** 043 * Lots of small often used algorithms on graphs. 044 * 045 * <p> 046 * This class contains a lot of very small algorithms that could be often useful 047 * with a graph. Most methods take a graph as first argument. 048 * </p> 049 * 050 * <h2>Usage</h2> 051 * 052 * <h3>Degrees</h3> 053 * 054 * <p> 055 * The {@link #degreeDistribution(Graph)} method allows to obtain an array where 056 * each cell index represents the degree, and the value of the cell the number 057 * of nodes having this degree. Its complexity is O(n) with n the number of 058 * nodes. 059 * </p> 060 * 061 * <p> 062 * The {@link #degreeMap(Graph)} returns an array of nodes sorted by degree in 063 * descending order. The complexity is O(n log(n)) with n the number of nodes. 064 * </p> 065 * 066 * <p> 067 * The {@link #averageDegree(Graph)} returns the average degree. The complexity 068 * is O(1). 069 * </p> 070 * 071 * <p> 072 * The {@link #degreeAverageDeviation(Graph)} returns the deviation of the 073 * average degree. The complexity is O(n) with n the number of nodes. 074 * </p> 075 * * <h3>Density</h3> 076 * 077 * <p> 078 * The {@link #density(Graph)} method returns the number of links in the graph 079 * divided by the total number of possible links. The complexity is O(1). 080 * </p> 081 * 082 * <h3>Diameter</h3> 083 * 084 * <p> 085 * The {@link #diameter(Graph)} method computes the diameter of the graph. The 086 * diameter of the graph is the largest of all the shortest paths from any node 087 * to any other node. 088 * </p> 089 * 090 * <p> 091 * The returned diameter is not an integer since some graphs have non-integer 092 * weights on edges. 093 * </p> 094 * 095 * <p> 096 * The {@link #diameter(Graph, String, boolean)} method does the same thing, but 097 * considers that the graph is weighted if the second argument is non-null. The 098 * second argument is the weight attribute name. The third argument indicates if 099 * the graph must be considered as directed or not. 100 * </p> 101 * 102 * <p> 103 * Note that this operation can be quite costly, the algorithm used depends on 104 * the fact the graph is weighted or not. If unweighted, the algorithm is in 105 * O(n*(n+m)). If weighted the algorithm is the Floyd-Warshall algorithm whose 106 * complexity is at worst of O(n^3). 107 * </p> 108 * 109 * <h3>Clustering coefficient</h3> 110 * 111 * <p> 112 * The {@link #clusteringCoefficient(Node)} method return the clustering 113 * coefficient for the given node. The complexity if O(d^2) where d is the 114 * degree of the node. 115 * </p> 116 * 117 * <p> 118 * The {@link #clusteringCoefficients(Graph)} method return the clustering 119 * coefficient of each node of the graph as an array. 120 * </p> 121 * 122 * <p> 123 * The {@link #averageClusteringCoefficient(Graph)} method return the average 124 * clustering coefficient for the graph. 125 * </p> 126 * 127 * <h3>Random nodes and edges</h3> 128 * 129 * <p> 130 * The {@link #randomNode(Graph)} returns a node chosen at random in the graph. 131 * You can alternatively pass a ``Random`` instance as parameter with 132 * {@link #randomNode(Graph, Random)}. The complexity depends on the kind of 133 * graph. 134 * </p> 135 * 136 * <p> 137 * The {@link #randomEdge(Graph)} returns an edge chosen at random in the graph. 138 * You can alternatively pass a ``Random`` instance as parameter with 139 * {@link #randomEdge(Graph, Random)}. The {@link #randomEdge(Node)} returns an 140 * edge chosen at random within the edge set of the given node. You can also use 141 * {@link #randomEdge(Node, Random)}. To chose a random edge of a node inside 142 * the entering or leaving edge sets only, you can use 143 * {@link #randomInEdge(Node)} or {@link #randomInEdge(Node, Random)}, or 144 * {@link #randomOutEdge(Node)} or finally {@link #randomOutEdge(Node, Random)}. 145 * </p> 146 * 147 * <h3>Nodes position</h3> 148 * 149 * <p> 150 * Extracting nodes position from attributes can be tricky due to the face the 151 * positions can be stored either as separate ``x``, ``y`` and ``z`` attributes 152 * or inside ``xy`` or ``xyz`` attributes. 153 * </p> 154 * 155 * <p> 156 * To simplify things you can use {@link #nodePosition(Node)} which returns an 157 * array of three doubles, containing the position of the node. You can also use 158 * {@link #nodePosition(Graph, String)} with a graph and a node identifier. 159 * </p> 160 * 161 * <p> 162 * If you already have an array of doubles with at least three cells you can 163 * also use {@link #nodePosition(Node, double[])} that will store the position 164 * in the passed array. You can as well use 165 * {@link #nodePosition(Graph, String, double[])}. 166 * </p> 167 * 168 * <p> 169 * All these methods can also handle the ``org.graphstream.ui.geom.Point3`` 170 * class instead of arrays of doubles. Methods that use such an array as 171 * argument are the same. Methods that return a ``Point3`` instead of an array 172 * are {@link #nodePointPosition(Graph, String)} and 173 * {@link #nodePointPosition(Node)}. 174 * </p> 175 * 176 * <h3>Cliques</h3> 177 * 178 * <p> 179 * A clique <i>C</i> is a subset of the node set of a graph, such that there 180 * exists an edge between each pair of nodes in <i>C</i>. In other words, the 181 * subgraph induced by <i>C</i> is complete. A maximal clique is a clique that 182 * cannot be extended by adding more nodes, that is, there is no node outside 183 * the clique connected to all the clique nodes. 184 * </p> 185 * 186 * <p> 187 * This class provides several methods for dealing with cliques. Use 188 * {@link #isClique(Collection)} or {@link #isMaximalClique(Collection, Graph)} 189 * to check if a set of nodes is a clique or a maximal clique. 190 * </p> 191 * 192 * <p> 193 * The methods {@link #getMaximalCliqueIterator(Graph)} and 194 * {@link #getMaximalCliques(Graph)} enumerate all the maximal cliques in a 195 * graph. Iterating on all the maximal cliques of a graph can take much time, 196 * because their number can grow exponentially with the size of the graph. For 197 * example, the following naive method to find the maximum clique (that is, the 198 * largest possible clique) in a graph, is practical only for small and sparse 199 * graphs. 200 * </p> 201 * 202 * <pre> 203 * List<Node> maximumClique = new ArrayList<Node>(); 204 * for (List<Node> clique : Toolkit.getMaximalCliques(g)) 205 * if (clique.size() > maximumClique.size()) 206 * maximumClique = clique; 207 * </pre> 208 * 209 * <h2>Example</h2> 210 * 211 * <p> 212 * You can use this class with a static import for example: 213 * </p> 214 * 215 * <pre> 216 * import static org.graphstream.algorithm.Toolkit.*; 217 * </pre> 218 */ 219public class Toolkit extends 220 org.graphstream.ui.graphicGraph.GraphPosLengthUtils { 221 // Access 222 223 /** 224 * Compute the weighted degree of a given node. For each entering 225 * and leaving edge the value contained by the 'weightAttribute' is 226 * considered. If the edge does not have such an attribute, the value 227 * one is used instead, resolving to a normal degree. Loop edges are counted 228 * twice. The 'weightAttribute' must contain a number or the default value 229 * is used. 230 * @param node The node to consider. 231 * @param weightAttribute The name of the attribute to look for weights on edges, it must be a number. 232 * @return The weighted degree. 233 */ 234 public static double weightedDegree(Node node, String weightAttribute) { 235 return weightedDegree(node, weightAttribute, 1); 236 } 237 238 /** 239 * Compute the weighted degree of a given node. For each entering 240 * and leaving edge the value contained by the 'weightAttribute' is 241 * considered. If the edge does not have such an attribute, the value 242 * `defaultWeightValue` is used instead. Loop edges are counted twice. 243 * The 'weightAttribute' must contain a number or the default value 244 * is used. 245 * @param node The node to consider. 246 * @param weightAttribute The name of the attribute to look for weights on edges, it must be a number. 247 * @param defaultWeightValue The default weight value to use if edges do not have the 'weightAttribute'. 248 * @return The weighted degree. 249 */ 250 public static double weightedDegree(Node node, String weightAttribute, double defaultWeightValue) { 251 double wdegree = 0; 252 253 for(Edge edge:node.getEachEdge()) { 254 if(edge.hasNumber(weightAttribute)) { 255 if(edge.getSourceNode() == edge.getTargetNode()) 256 wdegree += edge.getNumber(weightAttribute) * 2; 257 else wdegree += edge.getNumber(weightAttribute); 258 } else { 259 if(edge.getSourceNode() == edge.getTargetNode()) 260 wdegree += defaultWeightValue * 2; 261 else wdegree += defaultWeightValue; 262 } 263 } 264 265 return wdegree; 266 } 267 268 /** 269 * Compute the weighted entering degree of a given node. For each 270 * entering edge the value contained by the 'weightAttribute' is 271 * considered. If the edge does not have such an attribute, the value 272 * one is used instead, resolving to a normal degree. Loop edges are counted once 273 * if directed, but twice if undirected. The 'weightAttribute' must 274 * contain a number or the default value is used. 275 * @param node The node to consider. 276 * @param weightAttribute The name of the attribute to look on edges, it must be a number. 277 * @param defaultWeightValue The default weight value to use if edges do not have the 'weightAttribute'. 278 * @return The entering weighted degree. 279 */ 280 public static double enteringWeightedDegree(Node node, String weightAttribute) { 281 return enteringWeightedDegree(node, weightAttribute, 1); 282 } 283 284 /** 285 * Compute the weighted entering degree of a given node. For each 286 * entering edge the value contained by the 'weightAttribute' is 287 * considered. If the edge does not have such an attribute, the value 288 * 'defaultWeightValue' is used instead. Loop edges are counted once 289 * if directed, but twice if undirected. The 'weightAttribute' must 290 * contain a number or the default value is used. 291 * @param node The node to consider. 292 * @param weightAttribute The name of the attribute to look on edges, it must be a number. 293 * @param defaultWeightValue The default weight value to use if edges do not have the 'weightAttribute'. 294 * @return The entering weighted degree. 295 */ 296 public static double enteringWeightedDegree(Node node, String weightAttribute, double defaultWeightValue) { 297 double wdegree = 0; 298 299 for(Edge edge:node.getEnteringEdgeSet()) { 300 if(edge.hasNumber(weightAttribute)) { 301 wdegree += edge.getNumber(weightAttribute); 302 } else { 303 wdegree += defaultWeightValue; 304 } 305 } 306 307 return wdegree; 308 } 309 310 /** 311 * Compute the weighted leaving degree of a given node. For each 312 * leaving edge the value contained by the 'weightAttribute' is 313 * considered. If the edge does not have such an attribute, the value 314 * one is used instead, resolving to a normal degree. Loop edges are counted once 315 * if directed, but twice if undirected. The 'weightAttribute' must 316 * contain a number or the default value is used. 317 * @param node The node to consider. 318 * @param weightAttribute The name of the attribute to look on edges, it must be a number. 319 * @param defaultWeightValue The default weight value to use if edges do not have the 'weightAttribute'. 320 * @return The leaving weighted degree. 321 */ 322 public static double leavingWeightedDegree(Node node, String weightAttribute) { 323 return leavingWeightedDegree(node, weightAttribute, 1); 324 } 325 326 /** 327 * Compute the weighted leaving degree of a given node. For each 328 * leaving edge the value contained by the 'weightAttribute' is 329 * considered. If the edge does not have such an attribute, the value 330 * 'defaultWeightValue' is used instead. Loop edges are counted once 331 * if directed, but twice if undirected. The 'weightAttribute' must 332 * contain a number or the default value is used. 333 * @param node The node to consider. 334 * @param weightAttribute The name of the attribute to look on edges, it must be a number. 335 * @param defaultWeightValue The default weight value to use if edges do not have the 'weightAttribute'. 336 * @return The leaving weighted degree. 337 */ 338 public static double leavingWeightedDegree(Node node, String weightAttribute, double defaultWeightValue) { 339 double wdegree = 0; 340 341 for(Edge edge:node.getLeavingEdgeSet()) { 342 if(edge.hasNumber(weightAttribute)) { 343 wdegree += edge.getNumber(weightAttribute); 344 } else { 345 wdegree += defaultWeightValue; 346 } 347 } 348 349 return wdegree; 350 } 351 352 /** 353 * Compute the degree distribution of this graph. Each cell of the returned 354 * array contains the number of nodes having degree n where n is the index 355 * of the cell. For example cell 0 counts how many nodes have zero edges, 356 * cell 5 counts how many nodes have five edges. The last index indicates 357 * the maximum degree. 358 * 359 * @complexity O(n) where n is the number of nodes. 360 */ 361 public static int[] degreeDistribution(Graph graph) { 362 if (graph.getNodeCount() == 0) 363 return null; 364 365 int max = 0; 366 int[] dd; 367 int d; 368 369 for (Node node : graph) { 370 d = node.getDegree(); 371 372 if (d > max) 373 max = d; 374 } 375 376 dd = new int[max + 1]; 377 378 for (Node node : graph) { 379 d = node.getDegree(); 380 381 dd[d] += 1; 382 } 383 384 return dd; 385 } 386 387 /** 388 * Return a list of nodes sorted by degree, the larger first. 389 * 390 * @return The degree map. 391 * @complexity O(n log(n)) where n is the number of nodes. 392 */ 393 public static ArrayList<Node> degreeMap(Graph graph) { 394 ArrayList<Node> map = new ArrayList<Node>(); 395 396 for (Node node : graph) 397 map.add(node); 398 399 Collections.sort(map, new Comparator<Node>() { 400 public int compare(Node a, Node b) { 401 return b.getDegree() - a.getDegree(); 402 } 403 }); 404 405 return map; 406 } 407 408 /** 409 * Return a list of nodes sorted by their weighted degree, the larger first. 410 * 411 * @param graph The graph to consider. 412 * @param weightAttribute The name of the attribute to look for weights on edges, it must be a number, or the default value is used. 413 * @param defaultWeightValue The value to use if the weight attribute is not found on edges. 414 * @return The degree map. 415 * @complexity O(n log(n)) where n is the number of nodes. 416 * @see #weightedDegree(Node, String, double) 417 */ 418 public static ArrayList<Node> weightedDegreeMap(Graph graph, String weightAttribute, double defaultWeightValue) { 419 ArrayList<Node> map = new ArrayList<Node>(); 420 421 for (Node node : graph) 422 map.add(node); 423 424 Collections.sort(map, new WeightComparator(weightAttribute, defaultWeightValue)); 425 426 return map; 427 } 428 429 /** 430 * Return a list of nodes sorted by their weighted degree, the larger first. 431 * 432 * @param graph The graph to consider. 433 * @param weightAttribute The name of the attribute to look for weights on edges, it must be a number, or the default value of one is used. 434 * @return The degree map. 435 * @complexity O(n log(n)) where n is the number of nodes. 436 * @see #weightedDegree(Node, String, double) 437 */ 438 public static ArrayList<Node> weightedDegreeMap(Graph graph, String weightAttribute) { 439 return weightedDegreeMap(graph, weightAttribute, 1); 440 } 441 442 /** 443 * Compare nodes by their weighted degree. 444 */ 445 private static class WeightComparator implements Comparator<Node> { 446 private String weightAttribute = "weight"; 447 private double defaultWeightValue = 1; 448 public WeightComparator(String watt, double dwv) { 449 this.weightAttribute = watt; 450 this.defaultWeightValue = dwv; 451 } 452 public int compare(Node a, Node b) { 453 double bw = weightedDegree(b, weightAttribute, defaultWeightValue); 454 double ba = weightedDegree(a, weightAttribute, defaultWeightValue); 455 if(bw < ba) return -1; 456 else if(bw > ba) return 1; 457 else return 0; 458 } 459 } 460 461 /** 462 * Returns the value of the average degree of the graph. A node with a loop 463 * edge has degree two. 464 * 465 * @return The average degree of the graph. 466 * @complexity O(1). 467 */ 468 public static double averageDegree(Graph graph) { 469 float m = graph.getEdgeCount() * 2; 470 float n = graph.getNodeCount(); 471 472 if (n > 0) 473 return m / n; 474 475 return 0; 476 } 477 478 /** 479 * Returns the value of the degree average deviation of the graph. 480 * 481 * @return The degree average deviation. 482 * @complexity O(n) where n is the number of nodes. 483 */ 484 public static double degreeAverageDeviation(Graph graph) { 485 double average = averageDegree(graph); 486 double sum = 0; 487 488 for (Node node : graph) { 489 double d = node.getDegree() - average; 490 sum += d * d; 491 } 492 493 return Math.sqrt(sum / graph.getNodeCount()); 494 } 495 496 /** 497 * The density is the number of links in the graph divided by the total 498 * number of possible links. 499 * 500 * @return The density of the graph. 501 * @complexity O(1) 502 */ 503 public static double density(Graph graph) { 504 float m = (float) graph.getEdgeCount(); 505 float n = (float) graph.getNodeCount(); 506 507 if (n > 0) 508 return ((2 * m) / (n * (n - 1))); 509 510 return 0; 511 } 512 513 /** 514 * Clustering coefficient for each node of the graph. 515 * 516 * @return An array whose size correspond to the number of nodes, where each 517 * element is the clustering coefficient of a node. 518 * @complexity at worse O(n d^2) where n is the number of nodes and d the 519 * average or maximum degree of nodes. 520 */ 521 public static double[] clusteringCoefficients(Graph graph) { 522 int n = graph.getNodeCount(); 523 524 if (n > 0) { 525 int j = 0; 526 double[] coefs = new double[n]; 527 528 for (Node node : graph) 529 coefs[j++] = clusteringCoefficient(node); 530 531 assert (j == n); 532 533 return coefs; 534 } 535 536 return new double[0]; 537 } 538 539 /** 540 * Average clustering coefficient of the whole graph. Average of each node 541 * individual clustering coefficient. 542 * 543 * @return The average clustering coefficient. 544 * @complexity at worse O(n d^2) where n is the number of nodes and d the 545 * average or maximum degree of nodes. 546 */ 547 public static double averageClusteringCoefficient(Graph graph) { 548 int n = graph.getNodeCount(); 549 550 if (n > 0) { 551 double cc = 0; 552 553 for (Node node : graph) 554 cc += clusteringCoefficient(node); 555 556 return cc / n; 557 } 558 559 return 0; 560 } 561 562 /** 563 * Clustering coefficient for one node of the graph. For a node i with 564 * degree k, if Ni is the neighborhood of i (a set of nodes), clustering 565 * coefficient of i is defined as the count of edge e_uv with u,v in Ni 566 * divided by the maximum possible count, ie. k * (k-1) / 2. 567 * 568 * This method only works with undirected graphs. 569 * 570 * @param node 571 * The node to compute the clustering coefficient for. 572 * @return The clustering coefficient for this node. 573 * @complexity O(d^2) where d is the degree of the given node. 574 * @reference D. J. Watts and Steven Strogatz (June 1998). 575 * "Collective dynamics of 'small-world' networks" . Nature 393 576 * (6684): 440–442 577 */ 578 public static double clusteringCoefficient(Node node) { 579 double coef = 0.0; 580 int n = node.getDegree(); 581 582 if (n > 1) { 583 Node[] nodes = new Node[n]; 584 585 // 586 // Collect the neighbor nodes. 587 // 588 for (int i = 0; i < n; i++) 589 nodes[i] = node.getEdge(i).getOpposite(node); 590 591 // 592 // Check all edge possibilities 593 // 594 for (int i = 0; i < n; ++i) 595 for (int j = 0; j < n; ++j) 596 if (j != i) { 597 Edge e = nodes[j].getEdgeToward(nodes[i].getId()); 598 599 if (e != null && e.getSourceNode() == nodes[j]) 600 coef++; 601 } 602 603 coef /= (n * (n - 1)) / 2.0; 604 } 605 606 return coef; 607 } 608 609 /** 610 * Choose a node at random. 611 * 612 * @return A node chosen at random, null if the graph is empty. 613 * @complexity O(1). 614 */ 615 public static Node randomNode(Graph graph) { 616 return randomNode(graph, new Random()); 617 } 618 619 /** 620 * Choose a node at random. 621 * 622 * @param random 623 * The random number generator to use. 624 * @return A node chosen at random, null if the graph is empty. 625 * @complexity O(1). 626 */ 627 public static Node randomNode(Graph graph, Random random) { 628 int n = graph.getNodeCount(); 629 630 if (n > 0) { 631 return graph.getNode(random.nextInt(n)); 632 // int r = random.nextInt(n); 633 // int i = 0; 634 // 635 // for (Node node : graph) { 636 // if (r == i) 637 // return node; 638 // i++; 639 // } 640 } 641 642 return null; 643 } 644 645 /** 646 * Choose an edge at random. 647 * 648 * @return An edge chosen at random. 649 * @complexity O(1). 650 */ 651 public static Edge randomEdge(Graph graph) { 652 return randomEdge(graph, new Random()); 653 } 654 655 /** 656 * Choose an edge at random. 657 * 658 * @param random 659 * The random number generator to use. 660 * @return O(1). 661 */ 662 public static Edge randomEdge(Graph graph, Random random) { 663 int n = graph.getEdgeCount(); 664 665 if (n > 0) { 666 return graph.getEdge(random.nextInt(n)); 667 // int r = random.nextInt(n); 668 // int i = 0; 669 // 670 // for (Edge edge : graph.getEachEdge()) { 671 // if (r == i) 672 // return edge; 673 // i++; 674 // } 675 } 676 677 return null; 678 } 679 680 /** 681 * Choose an edge at random from the edges connected to the given node. 682 * 683 * @return O(1). 684 */ 685 public static Edge randomEdge(Node node) { 686 return randomEdge(node, new Random()); 687 } 688 689 /** 690 * Choose an edge at random from the entering edges connected to the given 691 * node. 692 * 693 * @return O(1). 694 */ 695 public static Edge randomInEdge(Node node) { 696 return randomInEdge(node, new Random()); 697 } 698 699 /** 700 * Choose an edge at random from the leaving edges connected to the given 701 * node. 702 * 703 * @return An edge chosen at random, null if the node has no leaving edges. 704 * @complexity O(1). 705 */ 706 public static Edge randomOutEdge(Node node) { 707 return randomOutEdge(node, new Random()); 708 } 709 710 /** 711 * Choose an edge at random from the edges connected to the given node. 712 * 713 * @param random 714 * The random number generator to use. 715 * @return An edge chosen at random, null if the node has no edges. 716 * @complexity O(1). 717 */ 718 public static Edge randomEdge(Node node, Random random) { 719 int n = node.getDegree(); 720 721 if (n > 0) { 722 return node.getEdge(random.nextInt(n)); 723 // int r = random.nextInt(n); 724 // int i = 0; 725 // 726 // for (Edge edge : node.getEdgeSet()) { 727 // if (r == i) 728 // return edge; 729 // i++; 730 // } 731 } 732 733 return null; 734 } 735 736 /** 737 * Choose an edge at random from the entering edges connected to the given 738 * node. 739 * 740 * @param random 741 * The random number generator to use. 742 * @return An edge chosen at random, null if the node has no entering edges. 743 * @complexity O(1). 744 */ 745 public static Edge randomInEdge(Node node, Random random) { 746 int n = node.getInDegree(); 747 748 if (n > 0) { 749 return node.getEnteringEdge(random.nextInt(n)); 750 // int r = random.nextInt(n); 751 // int i = 0; 752 // 753 // for (Edge edge : node.getEnteringEdgeSet()) { 754 // if (r == i) 755 // return edge; 756 // i++; 757 // } 758 } 759 760 return null; 761 } 762 763 /** 764 * Choose an edge at random from the leaving edges connected to the given 765 * node. 766 * 767 * @param random 768 * The random number generator to use. 769 * @return An edge chosen at random, null if the node has no leaving edges. 770 * @complexity O(1). 771 */ 772 public static Edge randomOutEdge(Node node, Random random) { 773 int n = node.getOutDegree(); 774 775 if (n > 0) { 776 return node.getLeavingEdge(random.nextInt(n)); 777 // int r = random.nextInt(n); 778 // int i = 0; 779 // 780 // for (Edge edge : node.getLeavingEdgeSet()) { 781 // if (r == i) 782 // return edge; 783 // i += 1; 784 // } 785 } 786 787 return null; 788 } 789 790 /** 791 * Return set of nodes grouped by the value of one attribute (the marker). 792 * For example, if the marker is "color" and in the graph there are nodes 793 * whose "color" attribute value is "red" and others with value "blue", this 794 * method will return two sets, one containing all nodes corresponding to 795 * the nodes whose "color" attribute is red, the other with blue nodes. If 796 * some nodes do not have the "color" attribute, a third set is returned. 797 * The returned sets are stored in a hash map whose keys are the values of 798 * the marker attribute (in our example, the keys would be "red" and "blue", 799 * and if there are nodes that do not have the "color" attribute, the third 800 * set will have key "NULL_COMMUNITY"). 801 * 802 * @param marker 803 * The attribute that allows to group nodes. 804 * @return The communities indexed by the value of the marker. 805 * @complexity O(n) with n the number of nodes. 806 */ 807 public static HashMap<Object, HashSet<Node>> communities(Graph graph, 808 String marker) { 809 HashMap<Object, HashSet<Node>> communities = new HashMap<Object, HashSet<Node>>(); 810 811 for (Node node : graph) { 812 Object communityMarker = node.getAttribute(marker); 813 814 if (communityMarker == null) 815 communityMarker = "NULL_COMMUNITY"; 816 817 HashSet<Node> community = communities.get(communityMarker); 818 819 if (community == null) { 820 community = new HashSet<Node>(); 821 communities.put(communityMarker, community); 822 } 823 824 community.add(node); 825 } 826 827 return communities; 828 } 829 830 /** 831 * Create the modularity matrix E from the communities. The given 832 * communities are set of nodes forming the communities as produced by the 833 * {@link #communities(Graph,String)} method. 834 * 835 * @param graph 836 * Graph to which the computation will be applied 837 * @param communities 838 * Set of nodes. 839 * @return The E matrix as defined by Newman and Girvan. 840 * @complexity O(m!k) with m the number of communities and k the average 841 * number of nodes per community. 842 */ 843 public static double[][] modularityMatrix(Graph graph, 844 HashMap<Object, HashSet<Node>> communities) { 845 return modularityMatrix(graph, communities, null); 846 } 847 848 /** 849 * Create the weighted modularity matrix E from the communities. The given 850 * communities are set of nodes forming the communities as produced by the 851 * {@link #communities(Graph,String)} method. 852 * 853 * @param graph 854 * Graph to which the computation will be applied 855 * @param communities 856 * Set of nodes. 857 * @param weightMarker 858 * The marker used to store the weight of each edge 859 * @return The E matrix as defined by Newman and Girvan. 860 * @complexity O(m!k) with m the number of communities and k the average 861 * number of nodes per community. 862 */ 863 public static double[][] modularityMatrix(Graph graph, 864 HashMap<Object, HashSet<Node>> communities, String weightMarker) { 865 866 double edgeCount = 0; 867 if (weightMarker == null) { 868 edgeCount = graph.getEdgeCount(); 869 } else { 870 for (Edge e : graph.getEdgeSet()) { 871 if (e.hasAttribute(weightMarker)) { 872 edgeCount += (Double) e.getAttribute(weightMarker); 873 } 874 } 875 } 876 877 int communityCount = communities.size(); 878 879 double E[][] = new double[communityCount][]; 880 Object keys[] = new Object[communityCount]; 881 882 int k = 0; 883 884 for (Object key : communities.keySet()) 885 keys[k++] = key; 886 887 for (int i = 0; i < communityCount; ++i) 888 E[i] = new double[communityCount]; 889 890 for (int y = 0; y < communityCount; ++y) { 891 for (int x = y; x < communityCount; ++x) { 892 E[x][y] = modularityCountEdges(communities.get(keys[x]), 893 communities.get(keys[y]), weightMarker); 894 E[x][y] /= edgeCount; 895 896 if (x != y) { 897 E[y][x] = E[x][y] / 2; 898 E[x][y] = E[y][x]; 899 } 900 } 901 } 902 903 return E; 904 } 905 906 /** 907 * Compute the modularity of the graph from the E matrix. 908 * 909 * @param E 910 * The E matrix given by {@link #modularityMatrix(Graph,HashMap)} 911 * . 912 * @return The modularity of the graph. 913 * @complexity O(m!) with m the number of communities. 914 */ 915 public static double modularity(double[][] E) { 916 double sumE = 0, Tr = 0; 917 double communityCount = E.length; 918 919// for (int y = 0; y < communityCount; ++y) { 920// for (int x = y; x < communityCount; ++x) { 921// if (x == y) 922// Tr += E[x][y]; 923// 924// sumE += E[x][y] * E[x][y]; 925// } 926// } 927 928 for (int i = 0; i < communityCount; i++) { 929 Tr += E[i][i]; 930 double a = 0; 931 for (int j = 0; j < communityCount; j++) 932 a += E[i][j]; 933 sumE += a * a; 934 } 935 936 return (Tr - sumE); 937 } 938 939 /** 940 * Computes the modularity as defined by Newman and Girvan in "Finding and 941 * evaluating community structure in networks". This algorithm traverses the 942 * graph to count nodes in communities. For this to work, there must exist 943 * an attribute on each node whose value define the community the node 944 * pertains to (see {@link #communities(Graph,String)}). 945 * 946 * This method is an utility method that call: 947 * <ul> 948 * <li>{@link #communities(Graph,String)}</li> 949 * <li>{@link #modularityMatrix(Graph,HashMap)}</li> 950 * <li>{@link #modularity(double[][])}</li> 951 * </ul> 952 * in order to produce the modularity value. 953 * 954 * @param marker 955 * The community attribute stored on nodes. 956 * @return The graph modularity. 957 * @complexity 0(n + m! + m!k) with n the number of nodes, m the number of 958 * communities and k the average number of nodes per 959 * communities. 960 * @see org.graphstream.algorithm.measure.Modularity 961 */ 962 public static double modularity(Graph graph, String marker) { 963 return modularity(modularityMatrix(graph, communities(graph, marker))); 964 } 965 966 /** 967 * Computes the weighted modularity. This algorithm traverses the graph to 968 * count nodes in communities. For this to work, there must exist an 969 * attribute on each node whose value define the community the node pertains 970 * to (see {@link #communities(Graph,String)}) and a attribute on each edge 971 * storing their weight (all edges without this attribute will be ignored in 972 * the computation). 973 * 974 * This method is an utility method that call: 975 * <ul> 976 * <li>{@link #communities(Graph,String)}</li> 977 * <li>{@link #modularityMatrix(Graph,HashMap,String)}</li> 978 * <li>{@link #modularity(double[][])}</li> 979 * </ul> 980 * in order to produce the modularity value. 981 * 982 * @param marker 983 * The community attribute stored on nodes. 984 * @param weightMarker 985 * The marker used to store the weight of each edge. 986 * @return The graph modularity. 987 * @complexity 0(n + m! + m!k) with n the number of nodes, m the number of 988 * communities and k the average number of nodes per 989 * communities. 990 * @see org.graphstream.algorithm.measure.Modularity 991 */ 992 public static double modularity(Graph graph, String marker, 993 String weightMarker) { 994 return modularity(modularityMatrix(graph, communities(graph, marker), 995 weightMarker)); 996 } 997 998 /** 999 * Count the number of edges between the two communities (works if the two 1000 * communities are the same). 1001 * 1002 * @param community 1003 * The first community. 1004 * @param otherCommunity 1005 * The second community. 1006 * @return The number of edges between the two communities. 1007 */ 1008 protected static double modularityCountEdges(HashSet<Node> community, 1009 HashSet<Node> otherCommunity) { 1010 return modularityCountEdges(community, otherCommunity, null); 1011 } 1012 1013 /** 1014 * Count the total weight of edges between the two communities (works if the 1015 * two communities are the same). 1016 * 1017 * @param community 1018 * The first community. 1019 * @param otherCommunity 1020 * The second community. 1021 * @param weightMarker 1022 * The marker used to store the weight of each edge 1023 * @return The number of edges between the two communities. 1024 */ 1025 protected static double modularityCountEdges(HashSet<Node> community, 1026 HashSet<Node> otherCommunity, String weightMarker) { 1027 HashSet<Edge> marked = new HashSet<Edge>(); 1028 1029 float edgeCount = 0; 1030 1031 if (community != otherCommunity) { 1032 // Count edges between the two communities 1033 1034 for (Node node : community) { 1035 for (Edge edge : node.getEdgeSet()) { 1036 if (!marked.contains(edge)) { 1037 marked.add(edge); 1038 1039 if ((community.contains(edge.getNode0()) && otherCommunity 1040 .contains(edge.getNode1())) 1041 || (community.contains(edge.getNode1()) && otherCommunity 1042 .contains(edge.getNode0()))) { 1043 if (weightMarker == null) 1044 edgeCount++; 1045 else if (edge.hasAttribute(weightMarker)) 1046 edgeCount += (Double) edge 1047 .getAttribute(weightMarker); 1048 } 1049 } 1050 } 1051 } 1052 } else { 1053 // Count inner edges. 1054 1055 for (Node node : community) { 1056 for (Edge edge : node.getEdgeSet()) { 1057 if (!marked.contains(edge)) { 1058 marked.add(edge); 1059 1060 if (community.contains(edge.getNode0()) 1061 && community.contains(edge.getNode1())) { 1062 if (weightMarker == null) 1063 edgeCount++; 1064 else if (edge.hasAttribute(weightMarker)) 1065 edgeCount += (Double) edge 1066 .getAttribute(weightMarker); 1067 } 1068 } 1069 } 1070 } 1071 } 1072 1073 return edgeCount; 1074 } 1075 1076 /** 1077 * Compute the diameter of the graph. 1078 * 1079 * <p> 1080 * The diameter of the graph is the largest of all the shortest paths from 1081 * any node to any other node. The graph is considered non weighted. 1082 * </p> 1083 * 1084 * <p> 1085 * Note that this operation can be quite costly, O(n*(n+m)). 1086 * </p> 1087 * 1088 * <p> 1089 * The returned diameter is not an integer since some graphs have 1090 * non-integer weights on edges. Although this version of the diameter 1091 * algorithm will return an integer. 1092 * </p> 1093 * 1094 * @param graph 1095 * The graph to use. 1096 * @return The diameter. 1097 */ 1098 public static double diameter(Graph graph) { 1099 return diameter(graph, null, false); 1100 } 1101 1102 /** 1103 * Compute the diameter of the graph. 1104 * 1105 * <p> 1106 * The diameter of the graph is the largest of all the shortest paths from 1107 * any node to any other node. 1108 * </p> 1109 * 1110 * <p> 1111 * Note that this operation can be quite costly. Two algorithms are used 1112 * here. If the graph is not weighted (the weightAttributeName parameter is 1113 * null), the algorithm use breath first search from all the nodes to find 1114 * the max depth (or eccentricity) of each node. The diameter is then the 1115 * maximum of these maximum depths. The complexity of this algorithm is 1116 * O(n*(n+m)), with n the number of nodes and m the number of edges. 1117 * </p> 1118 * 1119 * <p> 1120 * If the graph is weighted, the algorithm used to compute all shortest 1121 * paths is the Floyd-Warshall algorithm whose complexity is at worst of 1122 * O(n^3). 1123 * </p> 1124 * 1125 * <p> 1126 * The returned diameter is not an integer since weighted graphs have 1127 * non-integer weights on edges. 1128 * </p> 1129 * 1130 * @param graph 1131 * The graph to use. 1132 * @param weightAttributeName 1133 * The name used to store weights on the edges (must be a 1134 * Number). 1135 * @param directed 1136 * Does The edge direction should be considered ?. 1137 * @return The diameter. 1138 */ 1139 public static double diameter(Graph graph, String weightAttributeName, 1140 boolean directed) { 1141 double diameter = Double.MIN_VALUE; 1142 1143 if (weightAttributeName == null) { 1144 int d = 0; 1145 1146 for (Node node : graph) { 1147 d = unweightedEccentricity(node, directed); 1148 if (d > diameter) 1149 diameter = d; 1150 } 1151 } else { 1152 APSP apsp = new APSP(graph, weightAttributeName, directed); 1153 1154 apsp.compute(); 1155 1156 for (Node node : graph) { 1157 APSP.APSPInfo info = (APSP.APSPInfo) node 1158 .getAttribute(APSP.APSPInfo.ATTRIBUTE_NAME); 1159 1160 for (APSP.TargetPath path : info.targets.values()) { 1161 if (path.distance > diameter) 1162 diameter = path.distance; 1163 } 1164 } 1165 1166 } 1167 1168 return diameter; 1169 } 1170 1171 /** 1172 * Eccentricity of a node not considering edge weights. 1173 * 1174 * <p> 1175 * The eccentricity is the largest shortest path between the given node and 1176 * any other. It is here computed on number of edges crossed, not 1177 * considering the eventual weights of edges. 1178 * </p> 1179 * 1180 * <p> 1181 * This is computed using a breath first search and looking at the maximum 1182 * depth of the search. 1183 * </p> 1184 * 1185 * @param node 1186 * The node for which the eccentricity is to be computed. 1187 * @param directed 1188 * If true, the computation will respect edges direction, if any. 1189 * 1190 * @complexity O(n+m) with n the number of nodes and m the number of edges. 1191 * 1192 * @return The eccentricity. 1193 */ 1194 public static int unweightedEccentricity(Node node, boolean directed) { 1195 BreadthFirstIterator<Node> k = new BreadthFirstIterator<Node>(node, 1196 directed); 1197 while (k.hasNext()) { 1198 k.next(); 1199 } 1200 return k.getDepthMax(); 1201 } 1202 1203 /** 1204 * Checks if a set of nodes is a clique. 1205 * 1206 * @param nodes 1207 * a set of nodes 1208 * @return {@code true} if {@code nodes} form a clique 1209 * @complexity O(<i>k</i>), where <i>k</i> is the size of {@code nodes} 1210 */ 1211 public static boolean isClique(Collection<? extends Node> nodes) { 1212 if (nodes.isEmpty()) 1213 return false; 1214 for (Node x : nodes) 1215 for (Node y : nodes) 1216 if (x != y && x.getEdgeBetween(y.getId()) == null) 1217 return false; 1218 return true; 1219 } 1220 1221 /** 1222 * Checks if a set of nodes is a maximal clique. 1223 * 1224 * @param nodes 1225 * a set of nodes 1226 * @return {@code true} if {@nodes} form a maximal clique 1227 * @complexity O(<i>kn</i>), where <i>n</i> is the number of nodes in the 1228 * graph and <i>k</i> is the size of {@code nodes} 1229 */ 1230 public static boolean isMaximalClique(Collection<? extends Node> nodes, 1231 Graph graph) { 1232 if (!isClique(nodes)) 1233 return false; 1234 for (Node x : graph) { 1235 String xId = x.getId(); 1236 boolean isXConnectedToAll = true; 1237 for (Node y : nodes) 1238 if (y == x || y.getEdgeBetween(xId) == null) { 1239 isXConnectedToAll = false; 1240 break; 1241 } 1242 if (isXConnectedToAll) 1243 return false; 1244 } 1245 return true; 1246 } 1247 1248 /** 1249 * This iterator traverses all the maximal cliques in a graph. Each call to 1250 * {@link java.util.Iterator#next()} returns a maximal clique in the form of 1251 * list of nodes. This iterator does not support remove. 1252 * 1253 * @param graph 1254 * a graph, must not have loop edges 1255 * @return an iterator on the maximal cliques of {@code graph} 1256 * @throws IllegalArgumentException 1257 * if {@code graph} has loop edges 1258 * @complexity This iterator implements the Bron–Kerbosch algorithm. There 1259 * is no guarantee that each call to 1260 * {@link java.util.Iterator#next()} will run in polynomial 1261 * time. However, iterating over <em>all</em> the maximal 1262 * cliques is efficient in worst case sense. The whole iteration 1263 * takes O(3<sup><i>n</i>/3</sup>) time in the worst case and it 1264 * is known that a <i>n</i>-node graph has at most 1265 * 3<sup><i>n</i>/3</sup> maximal cliques. 1266 */ 1267 public static <T extends Node> Iterator<List<T>> getMaximalCliqueIterator( 1268 Graph graph) { 1269 for (Edge edge : graph.getEachEdge()) 1270 if (edge.isLoop()) 1271 throw new IllegalArgumentException( 1272 "The graph must not have loop edges"); 1273 return new BronKerboschIterator<T>(graph); 1274 } 1275 1276 /** 1277 * An iterable view of the set of all the maximal cliques in a graph. Uses 1278 * {@link #getMaximalCliqueIterator(Graph)}. 1279 * 1280 * @param graph 1281 * a graph 1282 * @return An iterable view of the maximal cliques in {@code graph}. 1283 */ 1284 public static <T extends Node> Iterable<List<T>> getMaximalCliques( 1285 final Graph graph) { 1286 return new Iterable<List<T>>() { 1287 public Iterator<List<T>> iterator() { 1288 return getMaximalCliqueIterator(graph); 1289 } 1290 1291 }; 1292 } 1293 1294 protected static class StackElement<T extends Node> { 1295 protected List<T> candidates; 1296 protected int candidateIndex; 1297 protected List<T> excluded; 1298 protected String pivotId; 1299 1300 protected boolean moreCandidates() { 1301 return candidateIndex < candidates.size(); 1302 } 1303 1304 protected T currentCandidate() { 1305 return candidates.get(candidateIndex); 1306 } 1307 1308 protected int nonNeighborCandidateCount(Node node) { 1309 int count = 0; 1310 String nodeId = node.getId(); 1311 for (T c : candidates) 1312 if (c.getEdgeBetween(nodeId) == null) 1313 count++; 1314 return count; 1315 } 1316 1317 protected void setPivot() { 1318 pivotId = null; 1319 int minCount = candidates.size() + 1; 1320 for (T x : candidates) { 1321 int count = nonNeighborCandidateCount(x); 1322 if (count < minCount) { 1323 minCount = count; 1324 pivotId = x.getId(); 1325 } 1326 } 1327 for (T x : excluded) { 1328 int count = nonNeighborCandidateCount(x); 1329 if (count < minCount) { 1330 minCount = count; 1331 pivotId = x.getId(); 1332 } 1333 } 1334 } 1335 1336 protected boolean skipCurrentCandidate() { 1337 return currentCandidate().getEdgeBetween(pivotId) != null; 1338 } 1339 1340 protected void forwardIndex() { 1341 while (moreCandidates() && skipCurrentCandidate()) 1342 candidateIndex++; 1343 } 1344 1345 protected StackElement<T> nextElement() { 1346 StackElement<T> next = new StackElement<T>(); 1347 String currentId = currentCandidate().getId(); 1348 1349 next.candidates = new ArrayList<T>(); 1350 for (T x : candidates) 1351 if (x.getEdgeBetween(currentId) != null) 1352 next.candidates.add(x); 1353 1354 next.excluded = new ArrayList<T>(); 1355 for (T x : excluded) 1356 if (x.getEdgeBetween(currentId) != null) 1357 next.excluded.add(x); 1358 1359 next.setPivot(); 1360 next.candidateIndex = 0; 1361 next.forwardIndex(); 1362 return next; 1363 } 1364 1365 protected void forward() { 1366 excluded.add(candidates.remove(candidateIndex)); 1367 forwardIndex(); 1368 } 1369 } 1370 1371 protected static class BronKerboschIterator<T extends Node> implements 1372 Iterator<List<T>> { 1373 1374 protected Stack<StackElement<T>> stack; 1375 protected Stack<T> clique; 1376 1377 protected void constructNextClique() { 1378 // backtrack 1379 while (!clique.isEmpty() && !stack.peek().moreCandidates()) { 1380 stack.pop(); 1381 clique.pop(); 1382 } 1383 // forward 1384 StackElement<T> currentElement = stack.peek(); 1385 while (currentElement.moreCandidates()) { 1386 clique.push(currentElement.currentCandidate()); 1387 stack.push(currentElement.nextElement()); 1388 currentElement.forward(); 1389 currentElement = stack.peek(); 1390 } 1391 } 1392 1393 protected void constructNextMaximalClique() { 1394 do { 1395 constructNextClique(); 1396 } while (!clique.isEmpty() && !stack.peek().excluded.isEmpty()); 1397 } 1398 1399 protected BronKerboschIterator(Graph graph) { 1400 clique = new Stack<T>(); 1401 stack = new Stack<StackElement<T>>(); 1402 StackElement<T> initial = new StackElement<T>(); 1403 1404 // initial.candidates = new ArrayList<T>(graph.<T> getNodeSet()); 1405 // More efficient initial order 1406 initial.candidates = new ArrayList<T>(graph.getNodeCount()); 1407 getDegeneracy(graph, initial.candidates); 1408 1409 initial.excluded = new ArrayList<T>(); 1410 initial.setPivot(); 1411 initial.candidateIndex = 0; 1412 initial.forwardIndex(); 1413 stack.push(initial); 1414 constructNextMaximalClique(); 1415 } 1416 1417 public boolean hasNext() { 1418 return !clique.isEmpty(); 1419 } 1420 1421 public List<T> next() { 1422 if (clique.isEmpty()) 1423 throw new NoSuchElementException(); 1424 List<T> result = new ArrayList<T>(clique); 1425 constructNextMaximalClique(); 1426 return result; 1427 } 1428 1429 public void remove() { 1430 throw new UnsupportedOperationException( 1431 "This iterator does not support remove"); 1432 } 1433 } 1434 1435 /** 1436 * <p> 1437 * This method computes the gedeneracy and the degeneracy ordering of a 1438 * graph. 1439 * </p> 1440 * 1441 * <p> 1442 * The degeneracy of a graph is the smallest number <i>d</i> such that every 1443 * subgraph has a node with degree <i>d</i> or less. The degeneracy is a 1444 * measure of sparseness of graphs. A degeneracy ordering is an ordering of 1445 * the nodes such that each node has at most <i>d</i> neighbors following it 1446 * in the ordering. The degeneracy ordering is used, among others, in greedy 1447 * coloring algorithms. 1448 * </p> 1449 * 1450 * 1451 * @param graph 1452 * a graph 1453 * @param ordering 1454 * a list of nodes. If not {@code null}, this list is first 1455 * cleared and then filled with the nodes of the graph in 1456 * degeneracy order. 1457 * @return the degeneracy of {@code graph} 1458 * @complexity O(<i>m</i>) where <i>m</i> is the number of edges in the 1459 * graph 1460 */ 1461 @SuppressWarnings("unchecked") 1462 public static <T extends Node> int getDegeneracy(Graph graph, 1463 List<T> ordering) { 1464 int n = graph.getNodeCount(); 1465 if (ordering != null) 1466 ordering.clear(); 1467 int maxDeg = 0; 1468 for (Node x : graph) 1469 if (x.getDegree() > maxDeg) 1470 maxDeg = x.getDegree(); 1471 List<DegenEntry> heads = new ArrayList<DegenEntry>(maxDeg + 1); 1472 for (int d = 0; d <= maxDeg; d++) 1473 heads.add(null); 1474 1475 Map<Node, DegenEntry> map = new HashMap<Node, DegenEntry>( 1476 4 * (n + 2) / 3); 1477 for (Node x : graph) { 1478 DegenEntry entry = new DegenEntry(); 1479 entry.node = x; 1480 entry.deg = x.getDegree(); 1481 entry.addToList(heads); 1482 map.put(x, entry); 1483 } 1484 1485 int degeneracy = 0; 1486 for (int j = 0; j < n; j++) { 1487 int i; 1488 DegenEntry entry; 1489 for (i = 0; (entry = heads.get(i)) == null; i++) 1490 ; 1491 if (i > degeneracy) 1492 degeneracy = i; 1493 entry.removeFromList(heads); 1494 entry.deg = -1; 1495 if (ordering != null) 1496 ordering.add((T) entry.node); 1497 Iterator<Node> neighborIt = entry.node.getNeighborNodeIterator(); 1498 while (neighborIt.hasNext()) { 1499 Node x = neighborIt.next(); 1500 DegenEntry entryX = map.get(x); 1501 if (entryX.deg == -1) 1502 continue; 1503 entryX.removeFromList(heads); 1504 entryX.deg--; 1505 entryX.addToList(heads); 1506 } 1507 } 1508 if (ordering != null) 1509 Collections.reverse(ordering); 1510 return degeneracy; 1511 } 1512 1513 protected static class DegenEntry { 1514 Node node; 1515 int deg; 1516 DegenEntry prev, next; 1517 1518 protected void addToList(List<DegenEntry> heads) { 1519 DegenEntry oldHead = heads.get(deg); 1520 heads.set(deg, this); 1521 prev = null; 1522 next = oldHead; 1523 if (oldHead != null) 1524 oldHead.prev = this; 1525 } 1526 1527 protected void removeFromList(List<DegenEntry> heads) { 1528 if (prev == null) 1529 heads.set(deg, next); 1530 else 1531 prev.next = next; 1532 if (next != null) 1533 next.prev = prev; 1534 } 1535 } 1536 1537 /** 1538 * Fills an array with the adjacency matrix of a graph. 1539 * 1540 * The adjacency matrix of a graph is a <i>n</i> times <i>n</i> matrix 1541 * {@code a}, where <i>n</i> is the number of nodes of the graph. The 1542 * element {@code a[i][j]} of this matrix is equal to the number of edges 1543 * from the node {@code graph.getNode(i)} to the node 1544 * {@code graph.getNode(j)}. An undirected edge between i-th and j-th node 1545 * is counted twice: in {@code a[i][j]} and in {@code a[j][i]}. 1546 * 1547 * @param graph 1548 * A graph. 1549 * @param matrix 1550 * The array where the adjacency matrix is stored. Must be of 1551 * size at least <i>n</i> times <i>n</i> 1552 * @throws IndexOutOfBoundsException 1553 * if the size of the matrix is insufficient. 1554 * @see Toolkit#getAdjacencyMatrix(Graph) 1555 * @complexity <i>O(n<sup>2</sup>)</i>, where <i>n</i> is the number of 1556 * nodes. 1557 */ 1558 public static void fillAdjacencyMatrix(Graph graph, int[][] matrix) { 1559 for (int i = 0; i < matrix.length; i++) 1560 Arrays.fill(matrix[i], 0); 1561 1562 for (Edge e : graph.getEachEdge()) { 1563 int i = e.getSourceNode().getIndex(); 1564 int j = e.getTargetNode().getIndex(); 1565 matrix[i][j]++; 1566 if (!e.isDirected()) 1567 matrix[j][i]++; 1568 } 1569 } 1570 1571 /** 1572 * Returns the adjacency matrix of a graph. 1573 * 1574 * The adjacency matrix of a graph is a <i>n</i> times <i>n</i> matrix 1575 * {@code a}, where <i>n</i> is the number of nodes of the graph. The 1576 * element {@code a[i][j]} of this matrix is equal to the number of edges 1577 * from the node {@code graph.getNode(i)} to the node 1578 * {@code graph.getNode(j)}. An undirected edge between i-th and j-th node 1579 * is counted twice: in {@code a[i][j]} and in {@code a[j][i]}. 1580 * 1581 * @param graph 1582 * A graph 1583 * @return The adjacency matrix of the graph. 1584 * @see Toolkit#fillAdjacencyMatrix(Graph, int[][]) 1585 * @complexity <i>O(n<sup>2</sup>)</i>, where <i>n</i> is the number of 1586 * nodes. 1587 */ 1588 public static int[][] getAdjacencyMatrix(Graph graph) { 1589 int n = graph.getNodeCount(); 1590 int[][] matrix = new int[n][n]; 1591 fillAdjacencyMatrix(graph, matrix); 1592 return matrix; 1593 } 1594 1595 /** 1596 * Fills an array with the incidence matrix of a graph. 1597 * 1598 * The incidence matrix of a graph is a <i>n</i> times <i>m</i> matrix 1599 * {@code a}, where <i>n</i> is the number of nodes and <i>m</i> is the 1600 * number of edges of the graph. The coefficients {@code a[i][j]} of this 1601 * matrix have the following values: 1602 * <ul> 1603 * <li>-1 if {@code graph.getEdge(j)} is directed and 1604 * {@code graph.getNode(i)} is its source.</li> 1605 * <li>1 if {@code graph.getEdge(j)} is undirected and 1606 * {@code graph.getNode(i)} is its source.</li> 1607 * <li>1 if {@code graph.getNode(i)} is the target of 1608 * {@code graph.getEdge(j)}.</li> 1609 * <li>0 otherwise. 1610 * </ul> 1611 * In the special case when the j-th edge is a loop connecting the i-th node 1612 * to itself, the coefficient {@code a[i][j]} is 0 if the loop is directed 1613 * and 2 if the loop is undirected. All the other coefficients in the j-th 1614 * column are 0. 1615 * 1616 * @param graph 1617 * A graph 1618 * @param matrix 1619 * The array where the incidence matrix is stored. Must be at 1620 * least of size <i>n</i> times <i>m</i> 1621 * @throws IndexOutOfBoundsException 1622 * if the size of the matrix is insufficient 1623 * @see #getIncidenceMatrix(Graph) 1624 * @complexity <i>O(mn)</i>, where <i>n</i> is the number of nodes and 1625 * <i>m</i> is the number of edges. 1626 */ 1627 public static void fillIncidenceMatrix(Graph graph, byte[][] matrix) { 1628 for (int i = 0; i < matrix.length; i++) 1629 Arrays.fill(matrix[i], (byte) 0); 1630 1631 for (Edge e : graph.getEachEdge()) { 1632 int j = e.getIndex(); 1633 matrix[e.getSourceNode().getIndex()][j] += e.isDirected() ? -1 : 1; 1634 matrix[e.getTargetNode().getIndex()][j] += 1; 1635 } 1636 } 1637 1638 /** 1639 * Returns the incidence matrix of a graph. 1640 * 1641 * The incidence matrix of a graph is a <i>n</i> times <i>m</i> matrix 1642 * {@code a}, where <i>n</i> is the number of nodes and <i>m</i> is the 1643 * number of edges of the graph. The coefficients {@code a[i][j]} of this 1644 * matrix have the following values: 1645 * <ul> 1646 * <li>-1 if {@code graph.getEdge(j)} is directed and 1647 * {@code graph.getNode(i)} is its source.</li> 1648 * <li>1 if {@code graph.getEdge(j)} is undirected and 1649 * {@code graph.getNode(i)} is its source.</li> 1650 * <li>1 if {@code graph.getNode(i)} is the target of 1651 * {@code graph.getEdge(j)}.</li> 1652 * <li>0 otherwise.</li> 1653 * </ul> 1654 * In the special case when the j-th edge is a loop connecting the i-th node 1655 * to itself, the coefficient {@code a[i][j]} is 0 if the loop is directed 1656 * and 2 if the loop is undirected. All the other coefficients in the j-th 1657 * column are 0. 1658 * 1659 * @param graph 1660 * A graph 1661 * @return The incidence matrix of the graph. 1662 * @see #fillIncidenceMatrix(Graph, byte[][]) 1663 * @complexity <i>O(mn)</i>, where <i>n</i> is the number of nodes and 1664 * <i>m</i> is the number of edges. 1665 */ 1666 public static byte[][] getIncidenceMatrix(Graph graph) { 1667 byte[][] matrix = new byte[graph.getNodeCount()][graph.getEdgeCount()]; 1668 fillIncidenceMatrix(graph, matrix); 1669 return matrix; 1670 } 1671 1672 /** 1673 * Compute coordinates of nodes using a layout algorithm. 1674 * 1675 * @param g 1676 * the graph 1677 * @param layout 1678 * layout algorithm to use for computing coordinates 1679 * @param stab 1680 * stabilization limit 1681 */ 1682 public static void computeLayout(Graph g, Layout layout, double stab) { 1683 GraphReplay r = new GraphReplay(g.getId()); 1684 1685 stab = Math.min(stab, 1); 1686 1687 layout.addAttributeSink(g); 1688 r.addSink(layout); 1689 r.replay(g); 1690 r.removeSink(layout); 1691 1692 layout.shake(); 1693 layout.compute(); 1694 1695 do 1696 layout.compute(); 1697 while (layout.getStabilization() < stab); 1698 1699 layout.removeAttributeSink(g); 1700 } 1701 1702 /** 1703 * Compute coordinates of nodes using default layout algorithm (SpringBox). 1704 * 1705 * @param g 1706 * the graph 1707 * @param stab 1708 * stabilization limit 1709 */ 1710 public static void computeLayout(Graph g, double stab) { 1711 computeLayout(g, new SpringBox(), stab); 1712 } 1713 1714 /** 1715 * Compute coordinates of nodes using default layout algorithm and default 1716 * stabilization limit. 1717 * 1718 * @param g 1719 * the graph 1720 */ 1721 public static void computeLayout(Graph g) { 1722 computeLayout(g, new SpringBox(), 0.99); 1723 } 1724 1725 /** 1726 * Returns a random subset of nodes of fixed size. Each node has the same 1727 * chance to be chosen. 1728 * 1729 * @param graph 1730 * A graph. 1731 * @param k 1732 * The size of the subset. 1733 * @return A random subset of nodes of size <code>k</code>. 1734 * @throws IllegalArgumentException 1735 * If <code>k</code> is negative or greater than the number of 1736 * nodes. 1737 * @complexity O(<code>k</code>) 1738 */ 1739 public static <T extends Node> List<T> randomNodeSet(Graph graph, int k) { 1740 return randomNodeSet(graph, k, new Random()); 1741 } 1742 1743 /** 1744 * Returns a random subset of nodes of fixed size. Each node has the same 1745 * chance to be chosen. 1746 * 1747 * @param graph 1748 * A graph. 1749 * @param k 1750 * The size of the subset. 1751 * @param random 1752 * A source of randomness. 1753 * @return A random subset of nodes of size <code>k</code>. 1754 * @throws IllegalArgumentException 1755 * If <code>k</code> is negative or greater than the number of 1756 * nodes. 1757 * @complexity O(<code>k</code>) 1758 */ 1759 public static <T extends Node> List<T> randomNodeSet(Graph graph, int k, 1760 Random random) { 1761 if (k < 0 || k > graph.getNodeCount()) 1762 throw new IllegalArgumentException("k must be between 0 and " 1763 + graph.getNodeCount()); 1764 Set<Integer> subset = RandomTools.randomKsubset(graph.getNodeCount(), 1765 k, null, random); 1766 List<T> result = new ArrayList<T>(subset.size()); 1767 for (int i : subset) 1768 result.add(graph.<T> getNode(i)); 1769 return result; 1770 } 1771 1772 /** 1773 * Returns a random subset of nodes. Each node is chosen with given 1774 * probability. 1775 * 1776 * @param graph 1777 * A graph. 1778 * @param p 1779 * The probability to choose each node. 1780 * @return A random subset of nodes. 1781 * @throws IllegalArgumentException 1782 * If <code>p</code> is negative or greater than one. 1783 * @complexity In average O(<code>n * p<code>), where <code>n</code> is the 1784 * number of nodes. 1785 */ 1786 public static <T extends Node> List<T> randomNodeSet(Graph graph, double p) { 1787 return randomNodeSet(graph, p, new Random()); 1788 } 1789 1790 /** 1791 * Returns a random subset of nodes. Each node is chosen with given 1792 * probability. 1793 * 1794 * @param graph 1795 * A graph. 1796 * @param p 1797 * The probability to choose each node. 1798 * @param random 1799 * A source of randomness. 1800 * @return A random subset of nodes. 1801 * @throws IllegalArgumentException 1802 * If <code>p</code> is negative or greater than one. 1803 * @complexity In average O(<code>n * p<code>), where <code>n</code> is the 1804 * number of nodes. 1805 */ 1806 public static <T extends Node> List<T> randomNodeSet(Graph graph, double p, 1807 Random random) { 1808 if (p < 0 || p > 1) 1809 throw new IllegalArgumentException("p must be between 0 and 1"); 1810 Set<Integer> subset = RandomTools.randomPsubset(graph.getNodeCount(), 1811 p, null, random); 1812 List<T> result = new ArrayList<T>(subset.size()); 1813 for (int i : subset) 1814 result.add(graph.<T> getNode(i)); 1815 return result; 1816 } 1817 1818 /** 1819 * Returns a random subset of edges of fixed size. Each edge has the same 1820 * chance to be chosen. 1821 * 1822 * @param graph 1823 * A graph. 1824 * @param k 1825 * The size of the subset. 1826 * @return A random subset of edges of size <code>k</code>. 1827 * @throws IllegalArgumentException 1828 * If <code>k</code> is negative or greater than the number of 1829 * edges. 1830 * @complexity O(<code>k</code>) 1831 */ 1832 public static <T extends Edge> List<T> randomEdgeSet(Graph graph, int k) { 1833 return randomEdgeSet(graph, k, new Random()); 1834 } 1835 1836 /** 1837 * Returns a random subset of edges of fixed size. Each edge has the same 1838 * chance to be chosen. 1839 * 1840 * @param graph 1841 * A graph. 1842 * @param k 1843 * The size of the subset. 1844 * @param random 1845 * A source of randomness. 1846 * @return A random subset of edges of size <code>k</code>. 1847 * @throws IllegalArgumentException 1848 * If <code>k</code> is negative or greater than the number of 1849 * edges. 1850 * @complexity O(<code>k</code>) 1851 */ 1852 public static <T extends Edge> List<T> randomEdgeSet(Graph graph, int k, 1853 Random random) { 1854 if (k < 0 || k > graph.getEdgeCount()) 1855 throw new IllegalArgumentException("k must be between 0 and " 1856 + graph.getEdgeCount()); 1857 Set<Integer> subset = RandomTools.randomKsubset(graph.getEdgeCount(), 1858 k, null, random); 1859 List<T> result = new ArrayList<T>(subset.size()); 1860 for (int i : subset) 1861 result.add(graph.<T> getEdge(i)); 1862 return result; 1863 } 1864 1865 /** 1866 * Returns a random subset of edges. Each edge is chosen with given 1867 * probability. 1868 * 1869 * @param graph 1870 * A graph. 1871 * @param p 1872 * The probability to choose each edge. 1873 * @return A random subset of edges. 1874 * @throws IllegalArgumentException 1875 * If <code>p</code> is negative or greater than one. 1876 * @complexity In average O(<code>m * p<code>), where <code>m</code> is the 1877 * number of edges. 1878 */ 1879 public static <T extends Edge> List<T> randomEdgeSet(Graph graph, double p) { 1880 return randomEdgeSet(graph, p, new Random()); 1881 } 1882 1883 /** 1884 * Returns a random subset of edges. Each edge is chosen with given 1885 * probability. 1886 * 1887 * @param graph 1888 * A graph. 1889 * @param p 1890 * The probability to choose each edge. 1891 * @param random 1892 * A source of randomness. 1893 * @return A random subset of edges. 1894 * @throws IllegalArgumentException 1895 * If <code>p</code> is negative or greater than one. 1896 * @complexity In average O(<code>m * p<code>), where <code>m</code> is the 1897 * number of edges. 1898 */ 1899 public static <T extends Edge> List<T> randomEdgeSet(Graph graph, double p, 1900 Random random) { 1901 if (p < 0 || p > 1) 1902 throw new IllegalArgumentException("p must be between 0 and 1"); 1903 Set<Integer> subset = RandomTools.randomPsubset(graph.getEdgeCount(), 1904 p, null, random); 1905 List<T> result = new ArrayList<T>(subset.size()); 1906 for (int i : subset) 1907 result.add(graph.<T> getEdge(i)); 1908 return result; 1909 } 1910 1911 /** 1912 * Determines if a graph is (weakly) connected. 1913 * 1914 * @param graph A graph. 1915 * @return {@code true} if the graph is connected. 1916 * @complexity O({@code m + n}) where {@code m} is the number of edges and {@code n} is the number of nodes. 1917 */ 1918 public static boolean isConnected(Graph graph) { 1919 if (graph.getNodeCount() == 0) 1920 return true; 1921 Iterator<Node> it = graph.getNode(0).getBreadthFirstIterator(false); 1922 int visited = 0; 1923 while (it.hasNext()) { 1924 it.next(); 1925 visited++; 1926 } 1927 return visited == graph.getNodeCount(); 1928 } 1929}