python-igraph manual

For using igraph from Python

   Home       Trees       Indices       Help   
Package igraph
[hide private]

Source Code for Package igraph

   1  # vim:ts=4:sw=4:sts=4:et 
   2  # -*- coding: utf-8 -*- 
   3  """ 
   4  IGraph library. 
   5   
   6  @undocumented: deprecated, _graphmethod, _add_proxy_methods, _layout_method_wrapper, 
   7                 _3d_version_for 
   8  """ 
   9   
  10  from __future__ import with_statement 
  11   
  12  __license__ = u""" 
  13  Copyright (C) 2006-2012  Tamás Nepusz <ntamas@gmail.com> 
  14  Pázmány Péter sétány 1/a, 1117 Budapest, Hungary 
  15   
  16  This program is free software; you can redistribute it and/or modify 
  17  it under the terms of the GNU General Public License as published by 
  18  the Free Software Foundation; either version 2 of the License, or 
  19  (at your option) any later version. 
  20   
  21  This program is distributed in the hope that it will be useful, 
  22  but WITHOUT ANY WARRANTY; without even the implied warranty of 
  23  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
  24  GNU General Public License for more details. 
  25   
  26  You should have received a copy of the GNU General Public License 
  27  along with this program; if not, write to the Free Software 
  28  Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
  29  02110-1301 USA 
  30  """ 
  31   
  32  # pylint: disable-msg=W0401 
  33  # W0401: wildcard import 
  34  from igraph._igraph import * 
  35  from igraph._igraph import __version__, __build_date__ 
  36  from igraph.clustering import * 
  37  from igraph.cut import * 
  38  from igraph.configuration import Configuration 
  39  from igraph.drawing import * 
  40  from igraph.drawing.colors import * 
  41  from igraph.datatypes import * 
  42  from igraph.formula import * 
  43  from igraph.layout import * 
  44  from igraph.matching import * 
  45  from igraph.remote.nexus import * 
  46  from igraph.statistics import * 
  47  from igraph.summary import * 
  48  from igraph.utils import * 
  49   
  50  import os 
  51  import math 
  52  import gzip 
  53  import sys 
  54  import operator 
  55   
  56  from collections import defaultdict 
  57  from itertools import izip 
  58  from shutil import copyfileobj 
  59  from tempfile import mkstemp 
  60  from warnings import warn 
61 62 -def deprecated(message):
63 """Prints a warning message related to the deprecation of some igraph 64 feature.""" 65 warn(message, DeprecationWarning, stacklevel=3) 66
67 # pylint: disable-msg=E1101 68 -class Graph(GraphBase):
69 """Generic graph. 70 71 This class is built on top of L{GraphBase}, so the order of the 72 methods in the Epydoc documentation is a little bit obscure: 73 inherited methods come after the ones implemented directly in the 74 subclass. L{Graph} provides many functions that L{GraphBase} does not, 75 mostly because these functions are not speed critical and they were 76 easier to implement in Python than in pure C. An example is the 77 attribute handling in the constructor: the constructor of L{Graph} 78 accepts three dictionaries corresponding to the graph, vertex and edge 79 attributes while the constructor of L{GraphBase} does not. This extension 80 was needed to make L{Graph} serializable through the C{pickle} module. 81 L{Graph} also overrides some functions from L{GraphBase} to provide a 82 more convenient interface; e.g., layout functions return a L{Layout} 83 instance from L{Graph} instead of a list of coordinate pairs. 84 85 Graphs can also be indexed by strings or pairs of vertex indices or vertex 86 names. When a graph is indexed by a string, the operation translates to 87 the retrieval, creation, modification or deletion of a graph attribute: 88 89 >>> g = Graph.Full(3) 90 >>> g["name"] = "Triangle graph" 91 >>> g["name"] 92 'Triangle graph' 93 >>> del g["name"] 94 95 When a graph is indexed by a pair of vertex indices or names, the graph 96 itself is treated as an adjacency matrix and the corresponding cell of 97 the matrix is returned: 98 99 >>> g = Graph.Full(3) 100 >>> g.vs["name"] = ["A", "B", "C"] 101 >>> g[1, 2] 102 1 103 >>> g["A", "B"] 104 1 105 >>> g["A", "B"] = 0 106 >>> g.ecount() 107 2 108 109 Assigning values different from zero or one to the adjacency matrix will 110 be translated to one, unless the graph is weighted, in which case the 111 numbers will be treated as weights: 112 113 >>> g.is_weighted() 114 False 115 >>> g["A", "B"] = 2 116 >>> g["A", "B"] 117 1 118 >>> g.es["weight"] = 1.0 119 >>> g.is_weighted() 120 True 121 >>> g["A", "B"] = 2 122 >>> g["A", "B"] 123 2 124 >>> g.es["weight"] 125 [1.0, 1.0, 2] 126 """ 127 128 # Some useful aliases 129 omega = GraphBase.clique_number 130 alpha = GraphBase.independence_number 131 shell_index = GraphBase.coreness 132 cut_vertices = GraphBase.articulation_points 133 blocks = GraphBase.biconnected_components 134 evcent = GraphBase.eigenvector_centrality 135 vertex_disjoint_paths = GraphBase.vertex_connectivity 136 edge_disjoint_paths = GraphBase.edge_connectivity 137 cohesion = GraphBase.vertex_connectivity 138 adhesion = GraphBase.edge_connectivity 139 140 # Compatibility aliases 141 shortest_paths_dijkstra = GraphBase.shortest_paths 142 subgraph = GraphBase.induced_subgraph 143
144 - def __init__(self, *args, **kwds):
145 """__init__(n=0, edges=None, directed=False, graph_attrs=None, 146 vertex_attrs=None, edge_attrs=None) 147 148 Constructs a graph from scratch. 149 150 @keyword n: the number of vertices. Can be omitted, the default is 151 zero. Note that if the edge list contains vertices with indexes 152 larger than or equal to M{m}, then the number of vertices will 153 be adjusted accordingly. 154 @keyword edges: the edge list where every list item is a pair of 155 integers. If any of the integers is larger than M{n-1}, the number 156 of vertices is adjusted accordingly. C{None} means no edges. 157 @keyword directed: whether the graph should be directed 158 @keyword graph_attrs: the attributes of the graph as a dictionary. 159 @keyword vertex_attrs: the attributes of the vertices as a dictionary. 160 Every dictionary value must be an iterable with exactly M{n} items. 161 @keyword edge_attrs: the attributes of the edges as a dictionary. Every 162 dictionary value must be an iterable with exactly M{m} items where 163 M{m} is the number of edges. 164 """ 165 # Set up default values for the parameters. This should match the order 166 # in *args 167 kwd_order = ["n", "edges", "directed", "graph_attrs", "vertex_attrs", \ 168 "edge_attrs"] 169 params = [0, [], False, {}, {}, {}] 170 171 # Is there any keyword argument in kwds that we don't know? If so, 172 # freak out. 173 unknown_kwds = set(kwds.keys()) 174 unknown_kwds.difference_update(kwd_order) 175 if unknown_kwds: 176 raise TypeError("{0}.__init__ got an unexpected keyword argument {1!r}".format( 177 self.__class__.__name__, unknown_kwds.pop() 178 )) 179 180 # If the first argument is a list, assume that the number of vertices 181 # were omitted 182 args = list(args) 183 if len(args) > 0: 184 if isinstance(args[0], list) or isinstance(args[0], tuple): 185 args.insert(0, params[0]) 186 187 # Override default parameters from args 188 params[:len(args)] = args 189 190 # Override default parameters from keywords 191 for idx, k in enumerate(kwd_order): 192 if k in kwds: 193 params[idx] = kwds[k] 194 195 # Now, translate the params list to argument names 196 nverts, edges, directed, graph_attrs, vertex_attrs, edge_attrs = params 197 198 # When the number of vertices is None, assume that the user meant zero 199 if nverts is None: 200 nverts = 0 201 202 # When 'edges' is None, assume that the user meant an empty list 203 if edges is None: 204 edges = [] 205 206 # Initialize the graph 207 GraphBase.__init__(self, nverts, edges, directed) 208 209 # Set the graph attributes 210 for key, value in graph_attrs.iteritems(): 211 if isinstance(key, (int, long)): 212 key = str(key) 213 self[key] = value 214 # Set the vertex attributes 215 for key, value in vertex_attrs.iteritems(): 216 if isinstance(key, (int, long)): 217 key = str(key) 218 self.vs[key] = value 219 # Set the edge attributes 220 for key, value in edge_attrs.iteritems(): 221 if isinstance(key, (int, long)): 222 key = str(key) 223 self.es[key] = value 224
225 - def add_edge(self, source, target, **kwds):
226 """add_edge(source, target, **kwds) 227 228 Adds a single edge to the graph. 229 230 Keyword arguments (except the source and target arguments) will be 231 assigned to the edge as attributes. 232 233 @param source: the source vertex of the edge or its name. 234 @param target: the target vertex of the edge or its name. 235 """ 236 if not kwds: 237 return self.add_edges([(source, target)]) 238 239 eid = self.ecount() 240 result = self.add_edges([(source, target)]) 241 edge = self.es[eid] 242 for key, value in kwds.iteritems(): 243 edge[key] = value 244 return result 245
246 - def add_edges(self, es):
247 """add_edges(es) 248 249 Adds some edges to the graph. 250 251 @param es: the list of edges to be added. Every edge is represented 252 with a tuple containing the vertex IDs or names of the two 253 endpoints. Vertices are enumerated from zero. 254 """ 255 return GraphBase.add_edges(self, es) 256
257 - def add_vertex(self, name=None, **kwds):
258 """add_vertex(name=None, **kwds) 259 260 Adds a single vertex to the graph. Keyword arguments will be assigned 261 as vertex attributes. Note that C{name} as a keyword argument is treated 262 specially; if a graph has C{name} as a vertex attribute, it allows one 263 to refer to vertices by their names in most places where igraph expects 264 a vertex ID. 265 """ 266 if not kwds and name is None: 267 return self.add_vertices(1) 268 269 vid = self.vcount() 270 result = self.add_vertices(1) 271 vertex = self.vs[vid] 272 for key, value in kwds.iteritems(): 273 vertex[key] = value 274 if name is not None: 275 vertex["name"] = name 276 return result 277
278 - def add_vertices(self, n):
279 """add_vertices(n) 280 281 Adds some vertices to the graph. 282 283 @param n: the number of vertices to be added, or the name of a single 284 vertex to be added, or an iterable of strings, each corresponding to the 285 name of a vertex to be added. Names will be assigned to the C{name} 286 vertex attribute. 287 """ 288 if isinstance(n, basestring): 289 # Adding a single vertex with a name 290 m = self.vcount() 291 result = GraphBase.add_vertices(self, 1) 292 self.vs[m]["name"] = n 293 return result 294 elif hasattr(n, "__iter__"): 295 m = self.vcount() 296 if not hasattr(n, "__len__"): 297 names = list(n) 298 else: 299 names = n 300 result = GraphBase.add_vertices(self, len(names)) 301 self.vs[m:]["name"] = names 302 return result 303 return GraphBase.add_vertices(self, n) 304
305 - def adjacent(self, *args, **kwds):
306 """adjacent(vertex, mode=OUT) 307 308 Returns the edges a given vertex is incident on. 309 310 @deprecated: replaced by L{Graph.incident()} since igraph 0.6 311 """ 312 deprecated("Graph.adjacent() is deprecated since igraph 0.6, please use " 313 "Graph.incident() instead") 314 return self.incident(*args, **kwds) 315
316 - def as_directed(self, *args, **kwds):
317 """as_directed(*args, **kwds) 318 319 Returns a directed copy of this graph. Arguments are passed on 320 to L{Graph.to_directed()} that is invoked on the copy. 321 """ 322 copy = self.copy() 323 copy.to_directed(*args, **kwds) 324 return copy 325
326 - def as_undirected(self, *args, **kwds):
327 """as_undirected(*args, **kwds) 328 329 Returns an undirected copy of this graph. Arguments are passed on 330 to L{Graph.to_undirected()} that is invoked on the copy. 331 """ 332 copy = self.copy() 333 copy.to_undirected(*args, **kwds) 334 return copy 335
336 - def delete_edges(self, *args, **kwds):
337 """Deletes some edges from the graph. 338 339 The set of edges to be deleted is determined by the positional and 340 keyword arguments. If any keyword argument is present, or the 341 first positional argument is callable, an edge 342 sequence is derived by calling L{EdgeSeq.select} with the same 343 positional and keyword arguments. Edges in the derived edge sequence 344 will be removed. Otherwise the first positional argument is considered 345 as follows: 346 347 - C{None} - deletes all edges 348 - a single integer - deletes the edge with the given ID 349 - a list of integers - deletes the edges denoted by the given IDs 350 - a list of 2-tuples - deletes the edges denoted by the given 351 source-target vertex pairs. When multiple edges are present 352 between a given source-target vertex pair, only one is removed. 353 """ 354 if len(args) == 0 and len(kwds) == 0: 355 raise ValueError("expected at least one argument") 356 if len(kwds)>0 or (hasattr(args[0], "__call__") and \ 357 not isinstance(args[0], EdgeSeq)): 358 edge_seq = self.es(*args, **kwds) 359 else: 360 edge_seq = args[0] 361 return GraphBase.delete_edges(self, edge_seq) 362 363
364 - def indegree(self, *args, **kwds):
365 """Returns the in-degrees in a list. 366 367 See L{degree} for possible arguments. 368 """ 369 kwds['mode'] = IN 370 return self.degree(*args, **kwds) 371
372 - def outdegree(self, *args, **kwds):
373 """Returns the out-degrees in a list. 374 375 See L{degree} for possible arguments. 376 """ 377 kwds['mode'] = OUT 378 return self.degree(*args, **kwds) 379
380 - def all_st_cuts(self, source, target):
381 """\ 382 Returns all the cuts between the source and target vertices in a 383 directed graph. 384 385 This function lists all edge-cuts between a source and a target vertex. 386 Every cut is listed exactly once. 387 388 @param source: the source vertex ID 389 @param target: the target vertex ID 390 @return: a list of L{Cut} objects. 391 392 @newfield ref: Reference 393 @ref: JS Provan and DR Shier: A paradigm for listing (s,t)-cuts in 394 graphs. Algorithmica 15, 351--372, 1996. 395 """ 396 return [Cut(self, cut=cut, partition=part) 397 for cut, part in izip(*GraphBase.all_st_cuts(self, source, target))] 398
399 - def all_st_mincuts(self, source, target, capacity=None):
400 """\ 401 Returns all the mincuts between the source and target vertices in a 402 directed graph. 403 404 This function lists all minimum edge-cuts between a source and a target 405 vertex. 406 407 @param source: the source vertex ID 408 @param target: the target vertex ID 409 @param capacity: the edge capacities (weights). If C{None}, all 410 edges have equal weight. May also be an attribute name. 411 @return: a list of L{Cut} objects. 412 413 @newfield ref: Reference 414 @ref: JS Provan and DR Shier: A paradigm for listing (s,t)-cuts in 415 graphs. Algorithmica 15, 351--372, 1996. 416 """ 417 value, cuts, parts = GraphBase.all_st_mincuts(self, source, target, capacity) 418 return [Cut(self, value, cut=cut, partition=part) 419 for cut, part in izip(cuts, parts)] 420
421 - def biconnected_components(self, return_articulation_points=False):
422 """\ 423 Calculates the biconnected components of the graph. 424 425 @param return_articulation_points: whether to return the articulation 426 points as well 427 @return: a L{VertexCover} object describing the biconnected components, 428 and optionally the list of articulation points as well 429 """ 430 if return_articulation_points: 431 trees, aps = GraphBase.biconnected_components(self, True) 432 else: 433 trees = GraphBase.biconnected_components(self, False) 434 435 clusters = [] 436 for tree in trees: 437 cluster = set() 438 for edge in self.es[tree]: 439 cluster.update(edge.tuple) 440 clusters.append(cluster) 441 clustering = VertexCover(self, clusters) 442 443 if return_articulation_points: 444 return clustering, aps 445 else: 446 return clustering 447 blocks = biconnected_components 448
449 - def cohesive_blocks(self):
450 """cohesive_blocks() 451 452 Calculates the cohesive block structure of the graph. 453 454 Cohesive blocking is a method of determining hierarchical subsets of graph 455 vertices based on their structural cohesion (i.e. vertex connectivity). 456 For a given graph G, a subset of its vertices S is said to be maximally 457 k-cohesive if there is no superset of S with vertex connectivity greater 458 than or equal to k. Cohesive blocking is a process through which, given a 459 k-cohesive set of vertices, maximally l-cohesive subsets are recursively 460 identified with l > k. Thus a hierarchy of vertex subsets is obtained in 461 the end, with the entire graph G at its root. 462 463 @return: an instance of L{CohesiveBlocks}. See the documentation of 464 L{CohesiveBlocks} for more information. 465 @see: L{CohesiveBlocks} 466 """ 467 return CohesiveBlocks(self, *GraphBase.cohesive_blocks(self)) 468
469 - def clusters(self, mode=STRONG):
470 """clusters(mode=STRONG) 471 472 Calculates the (strong or weak) clusters (connected components) for 473 a given graph. 474 475 @param mode: must be either C{STRONG} or C{WEAK}, depending on the 476 clusters being sought. Optional, defaults to C{STRONG}. 477 @return: a L{VertexClustering} object""" 478 return VertexClustering(self, GraphBase.clusters(self, mode)) 479 components = clusters 480
481 - def degree_distribution(self, bin_width = 1, *args, **kwds):
482 """degree_distribution(bin_width=1, ...) 483 484 Calculates the degree distribution of the graph. 485 486 Unknown keyword arguments are directly passed to L{degree()}. 487 488 @param bin_width: the bin width of the histogram 489 @return: a histogram representing the degree distribution of the 490 graph. 491 """ 492 result = Histogram(bin_width, self.degree(*args, **kwds)) 493 return result 494
495 - def dyad_census(self, *args, **kwds):
496 """dyad_census() 497 498 Calculates the dyad census of the graph. 499 500 Dyad census means classifying each pair of vertices of a directed 501 graph into three categories: mutual (there is an edge from I{a} to 502 I{b} and also from I{b} to I{a}), asymmetric (there is an edge 503 from I{a} to I{b} or from I{b} to I{a} but not the other way round) 504 and null (there is no connection between I{a} and I{b}). 505 506 @return: a L{DyadCensus} object. 507 @newfield ref: Reference 508 @ref: Holland, P.W. and Leinhardt, S. (1970). A Method for Detecting 509 Structure in Sociometric Data. American Journal of Sociology, 70, 510 492-513. 511 """ 512 return DyadCensus(GraphBase.dyad_census(self, *args, **kwds)) 513
514 - def get_adjacency(self, type=GET_ADJACENCY_BOTH, attribute=None, \ 515 default=0, eids=False):
516 """Returns the adjacency matrix of a graph. 517 518 @param type: either C{GET_ADJACENCY_LOWER} (uses the lower 519 triangle of the matrix) or C{GET_ADJACENCY_UPPER} 520 (uses the upper triangle) or C{GET_ADJACENCY_BOTH} 521 (uses both parts). Ignored for directed graphs. 522 @param attribute: if C{None}, returns the ordinary adjacency 523 matrix. When the name of a valid edge attribute is given 524 here, the matrix returned will contain the default value 525 at the places where there is no edge or the value of the 526 given attribute where there is an edge. Multiple edges are 527 not supported, the value written in the matrix in this case 528 will be unpredictable. This parameter is ignored if 529 I{eids} is C{True} 530 @param default: the default value written to the cells in the 531 case of adjacency matrices with attributes. 532 @param eids: specifies whether the edge IDs should be returned 533 in the adjacency matrix. Since zero is a valid edge ID, the 534 cells in the matrix that correspond to unconnected vertex 535 pairs will contain -1 instead of 0 if I{eids} is C{True}. 536 If I{eids} is C{False}, the number of edges will be returned 537 in the matrix for each vertex pair. 538 @return: the adjacency matrix as a L{Matrix}. 539 """ 540 if type != GET_ADJACENCY_LOWER and type != GET_ADJACENCY_UPPER and \ 541 type != GET_ADJACENCY_BOTH: 542 # Maybe it was called with the first argument as the attribute name 543 type, attribute = attribute, type 544 if type is None: 545 type = GET_ADJACENCY_BOTH 546 547 if eids: 548 result = Matrix(GraphBase.get_adjacency(self, type, eids)) 549 result -= 1 550 return result 551 552 if attribute is None: 553 return Matrix(GraphBase.get_adjacency(self, type)) 554 555 if attribute not in self.es.attribute_names(): 556 raise ValueError("Attribute does not exist") 557 558 data = [[default] * self.vcount() for _ in xrange(self.vcount())] 559 560 if self.is_directed(): 561 for edge in self.es: 562 data[edge.source][edge.target] = edge[attribute] 563 return Matrix(data) 564 565 if type == GET_ADJACENCY_BOTH: 566 for edge in self.es: 567 source, target = edge.tuple 568 data[source][target] = edge[attribute] 569 data[target][source] = edge[attribute] 570 elif type == GET_ADJACENCY_UPPER: 571 for edge in self.es: 572 data[min(edge.tuple)][max(edge.tuple)] = edge[attribute] 573 else: 574 for edge in self.es: 575 data[max(edge.tuple)][min(edge.tuple)] = edge[attribute] 576 577 return Matrix(data) 578 579
580 - def get_adjlist(self, mode=OUT):
581 """get_adjlist(mode=OUT) 582 583 Returns the adjacency list representation of the graph. 584 585 The adjacency list representation is a list of lists. Each item of the 586 outer list belongs to a single vertex of the graph. The inner list 587 contains the neighbors of the given vertex. 588 589 @param mode: if L{OUT}, returns the successors of the vertex. If 590 L{IN}, returns the predecessors of the vertex. If L{ALL}, both 591 the predecessors and the successors will be returned. Ignored 592 for undirected graphs. 593 """ 594 return [self.neighbors(idx, mode) for idx in xrange(self.vcount())] 595
596 - def get_adjedgelist(self, *args, **kwds):
597 """get_adjedgelist(mode=OUT) 598 599 Returns the incidence list representation of the graph. 600 601 @deprecated: replaced by L{Graph.get_inclist()} since igraph 0.6 602 @see: Graph.get_inclist() 603 """ 604 deprecated("Graph.get_adjedgelist() is deprecated since igraph 0.6, " 605 "please use Graph.get_inclist() instead") 606 return self.get_inclist(*args, **kwds) 607
608 - def get_inclist(self, mode=OUT):
609 """get_inclist(mode=OUT) 610 611 Returns the incidence list representation of the graph. 612 613 The incidence list representation is a list of lists. Each 614 item of the outer list belongs to a single vertex of the graph. 615 The inner list contains the IDs of the incident edges of the 616 given vertex. 617 618 @param mode: if L{OUT}, returns the successors of the vertex. If 619 L{IN}, returns the predecessors of the vertex. If L{ALL}, both 620 the predecessors and the successors will be returned. Ignored 621 for undirected graphs. 622 """ 623 return [self.incident(idx, mode) for idx in xrange(self.vcount())] 624
625 - def gomory_hu_tree(self, capacity=None, flow="flow"):
626 """gomory_hu_tree(capacity=None, flow="flow") 627 628 Calculates the Gomory-Hu tree of an undirected graph with optional 629 edge capacities. 630 631 The Gomory-Hu tree is a concise representation of the value of all the 632 maximum flows (or minimum cuts) in a graph. The vertices of the tree 633 correspond exactly to the vertices of the original graph in the same order. 634 Edges of the Gomory-Hu tree are annotated by flow values. The value of 635 the maximum flow (or minimum cut) between an arbitrary (u,v) vertex 636 pair in the original graph is then given by the minimum flow value (i.e. 637 edge annotation) along the shortest path between u and v in the 638 Gomory-Hu tree. 639 640 @param capacity: the edge capacities (weights). If C{None}, all 641 edges have equal weight. May also be an attribute name. 642 @param flow: the name of the edge attribute in the returned graph 643 in which the flow values will be stored. 644 @return: the Gomory-Hu tree as a L{Graph} object. 645 """ 646 graph, flow_values = GraphBase.gomory_hu_tree(self, capacity) 647 graph.es[flow] = flow_values 648 return graph 649
650 - def is_named(self):
651 """is_named() 652 653 Returns whether the graph is named, i.e. whether it has a "name" 654 vertex attribute. 655 """ 656 return "name" in self.vertex_attributes() 657
658 - def is_weighted(self):
659 """is_weighted() 660 661 Returns whether the graph is weighted, i.e. whether it has a "weight" 662 edge attribute. 663 """ 664 return "weight" in self.edge_attributes() 665
666 - def maxflow(self, source, target, capacity=None):
667 """maxflow(source, target, capacity=None) 668 669 Returns a maximum flow between the given source and target vertices 670 in a graph. 671 672 A maximum flow from I{source} to I{target} is an assignment of 673 non-negative real numbers to the edges of the graph, satisfying 674 two properties: 675 676 1. For each edge, the flow (i.e. the assigned number) is not 677 more than the capacity of the edge (see the I{capacity} 678 argument) 679 680 2. For every vertex except the source and the target, the 681 incoming flow is the same as the outgoing flow. 682 683 The value of the flow is the incoming flow of the target or the 684 outgoing flow of the source (which are equal). The maximum flow 685 is the maximum possible such value. 686 687 @param capacity: the edge capacities (weights). If C{None}, all 688 edges have equal weight. May also be an attribute name. 689 @return: a L{Flow} object describing the maximum flow 690 """ 691 return Flow(self, *GraphBase.maxflow(self, source, target, capacity)) 692
693 - def mincut(self, source=None, target=None, capacity=None):
694 """mincut(source=None, target=None, capacity=None) 695 696 Calculates the minimum cut between the given source and target vertices 697 or within the whole graph. 698 699 The minimum cut is the minimum set of edges that needs to be removed to 700 separate the source and the target (if they are given) or to disconnect the 701 graph (if neither the source nor the target are given). The minimum is 702 calculated using the weights (capacities) of the edges, so the cut with 703 the minimum total capacity is calculated. 704 705 For undirected graphs and no source and target, the method uses the 706 Stoer-Wagner algorithm. For a given source and target, the method uses the 707 push-relabel algorithm; see the references below. 708 709 @param source: the source vertex ID. If C{None}, the target must also be 710 C{None} and the calculation will be done for the entire graph (i.e. 711 all possible vertex pairs). 712 @param target: the target vertex ID. If C{None}, the source must also be 713 C{None} and the calculation will be done for the entire graph (i.e. 714 all possible vertex pairs). 715 @param capacity: the edge capacities (weights). If C{None}, all 716 edges have equal weight. May also be an attribute name. 717 @return: a L{Cut} object describing the minimum cut 718 """ 719 return Cut(self, *GraphBase.mincut(self, source, target, capacity)) 720
721 - def st_mincut(self, source, target, capacity=None):
722 """st_mincut(source, target, capacity=None) 723 724 Calculates the minimum cut between the source and target vertices in a 725 graph. 726 727 @param source: the source vertex ID 728 @param target: the target vertex ID 729 @param capacity: the capacity of the edges. It must be a list or a valid 730 attribute name or C{None}. In the latter case, every edge will have the 731 same capacity. 732 @return: the value of the minimum cut, the IDs of vertices in the 733 first and second partition, and the IDs of edges in the cut, 734 packed in a 4-tuple 735 """ 736 return Cut(self, *GraphBase.st_mincut(self, source, target, capacity)) 737
738 - def modularity(self, membership, weights=None):
739 """modularity(membership, weights=None) 740 741 Calculates the modularity score of the graph with respect to a given 742 clustering. 743 744 The modularity of a graph w.r.t. some division measures how good the 745 division is, or how separated are the different vertex types from each 746 other. It's defined as M{Q=1/(2m)*sum(Aij-ki*kj/(2m)delta(ci,cj),i,j)}. 747 M{m} is the number of edges, M{Aij} is the element of the M{A} 748 adjacency matrix in row M{i} and column M{j}, M{ki} is the degree of 749 node M{i}, M{kj} is the degree of node M{j}, and M{Ci} and C{cj} are 750 the types of the two vertices (M{i} and M{j}). M{delta(x,y)} is one iff 751 M{x=y}, 0 otherwise. 752 753 If edge weights are given, the definition of modularity is modified as 754 follows: M{Aij} becomes the weight of the corresponding edge, M{ki} 755 is the total weight of edges adjacent to vertex M{i}, M{kj} is the 756 total weight of edges adjacent to vertex M{j} and M{m} is the total 757 edge weight in the graph. 758 759 @param membership: a membership list or a L{VertexClustering} object 760 @param weights: optional edge weights or C{None} if all edges are 761 weighed equally. Attribute names are also allowed. 762 @return: the modularity score 763 764 @newfield ref: Reference 765 @ref: MEJ Newman and M Girvan: Finding and evaluating community 766 structure in networks. Phys Rev E 69 026113, 2004. 767 """ 768 if isinstance(membership, VertexClustering): 769 if membership.graph != self: 770 raise ValueError("clustering object belongs to another graph") 771 return GraphBase.modularity(self, membership.membership, weights) 772 else: 773 return GraphBase.modularity(self, membership, weights) 774
775 - def path_length_hist(self, directed=True):
776 """path_length_hist(directed=True) 777 778 Returns the path length histogram of the graph 779 780 @param directed: whether to consider directed paths. Ignored for 781 undirected graphs. 782 @return: a L{Histogram} object. The object will also have an 783 C{unconnected} attribute that stores the number of unconnected 784 vertex pairs (where the second vertex can not be reached from 785 the first one). The latter one will be of type long (and not 786 a simple integer), since this can be I{very} large. 787 """ 788 data, unconn = GraphBase.path_length_hist(self, directed) 789 hist = Histogram(bin_width=1) 790 for i, length in enumerate(data): 791 hist.add(i+1, length) 792 hist.unconnected = long(unconn) 793 return hist 794
795 - def pagerank(self, vertices=None, directed=True, damping=0.85, 796 weights=None, arpack_options=None, implementation="prpack", 797 niter=1000, eps=0.001):
798 """Calculates the Google PageRank values of a graph. 799 800 @param vertices: the indices of the vertices being queried. 801 C{None} means all of the vertices. 802 @param directed: whether to consider directed paths. 803 @param damping: the damping factor. M{1-damping} is the PageRank value 804 for nodes with no incoming links. It is also the probability of 805 resetting the random walk to a uniform distribution in each step. 806 @param weights: edge weights to be used. Can be a sequence or iterable 807 or even an edge attribute name. 808 @param arpack_options: an L{ARPACKOptions} object used to fine-tune 809 the ARPACK eigenvector calculation. If omitted, the module-level 810 variable called C{arpack_options} is used. This argument is 811 ignored if not the ARPACK implementation is used, see the 812 I{implementation} argument. 813 @param implementation: which implementation to use to solve the 814 PageRank eigenproblem. Possible values are: 815 - C{"prpack"}: use the PRPACK library. This is a new 816 implementation in igraph 0.7 817 - C{"arpack"}: use the ARPACK library. This implementation 818 was used from version 0.5, until version 0.7. 819 - C{"power"}: use a simple power method. This is the 820 implementation that was used before igraph version 0.5. 821 @param niter: The number of iterations to use in the power method 822 implementation. It is ignored in the other implementations 823 @param eps: The power method implementation will consider the 824 calculation as complete if the difference of PageRank values between 825 iterations change less than this value for every node. It is 826 ignored by the other implementations. 827 @return: a list with the Google PageRank values of the specified 828 vertices.""" 829 if arpack_options is None: 830 arpack_options = _igraph.arpack_options 831 return self.personalized_pagerank(vertices, directed, damping, None,\ 832 None, weights, arpack_options, \ 833 implementation, niter, eps) 834
835 - def spanning_tree(self, weights=None, return_tree=True):
836 """Calculates a minimum spanning tree for a graph. 837 838 @param weights: a vector containing weights for every edge in 839 the graph. C{None} means that the graph is unweighted. 840 @param return_tree: whether to return the minimum spanning tree (when 841 C{return_tree} is C{True}) or to return the IDs of the edges in 842 the minimum spanning tree instead (when C{return_tree} is C{False}). 843 The default is C{True} for historical reasons as this argument was 844 introduced in igraph 0.6. 845 @return: the spanning tree as a L{Graph} object if C{return_tree} 846 is C{True} or the IDs of the edges that constitute the spanning 847 tree if C{return_tree} is C{False}. 848 849 @newfield ref: Reference 850 @ref: Prim, R.C.: I{Shortest connection networks and some 851 generalizations}. Bell System Technical Journal 36:1389-1401, 1957. 852 """ 853 result = GraphBase._spanning_tree(self, weights) 854 if return_tree: 855 return self.subgraph_edges(result, delete_vertices=False) 856 return result 857
858 - def transitivity_avglocal_undirected(self, mode="nan", weights=None):
859 """Calculates the average of the vertex transitivities of the graph. 860 861 In the unweighted case, the transitivity measures the probability that 862 two neighbors of a vertex are connected. In case of the average local 863 transitivity, this probability is calculated for each vertex and then 864 the average is taken. Vertices with less than two neighbors require 865 special treatment, they will either be left out from the calculation 866 or they will be considered as having zero transitivity, depending on 867 the I{mode} parameter. The calculation is slightly more involved for 868 weighted graphs; in this case, weights are taken into account according 869 to the formula of Barrat et al (see the references). 870 871 Note that this measure is different from the global transitivity 872 measure (see L{transitivity_undirected()}) as it simply takes the 873 average local transitivity across the whole network. 874 875 @param mode: defines how to treat vertices with degree less than two. 876 If C{TRANSITIVITY_ZERO} or C{"zero"}, these vertices will have zero 877 transitivity. If C{TRANSITIVITY_NAN} or C{"nan"}, these vertices 878 will be excluded from the average. 879 @param weights: edge weights to be used. Can be a sequence or iterable 880 or even an edge attribute name. 881 882 @see: L{transitivity_undirected()}, L{transitivity_local_undirected()} 883 @newfield ref: Reference 884 @ref: Watts DJ and Strogatz S: I{Collective dynamics of small-world 885 networks}. Nature 393(6884):440-442, 1998. 886 @ref: Barrat A, Barthelemy M, Pastor-Satorras R and Vespignani A: 887 I{The architecture of complex weighted networks}. PNAS 101, 3747 (2004). 888 U{http://arxiv.org/abs/cond-mat/0311416}. 889 """ 890 if weights is None: 891 return GraphBase.transitivity_avglocal_undirected(self, mode) 892 893 xs = self.transitivity_local_undirected(mode=mode, weights=weights) 894 return sum(xs) / float(len(xs)) 895
896 - def triad_census(self, *args, **kwds):
897 """triad_census() 898 899 Calculates the triad census of the graph. 900 901 @return: a L{TriadCensus} object. 902 @newfield ref: Reference 903 @ref: Davis, J.A. and Leinhardt, S. (1972). The Structure of 904 Positive Interpersonal Relations in Small Groups. In: 905 J. Berger (Ed.), Sociological Theories in Progress, Volume 2, 906 218-251. Boston: Houghton Mifflin. 907 """ 908 return TriadCensus(GraphBase.triad_census(self, *args, **kwds)) 909 910 # Automorphisms
911 - def count_automorphisms_vf2(self, color=None, edge_color=None, 912 node_compat_fn=None, edge_compat_fn=None):
913 """Returns the number of automorphisms of the graph. 914 915 This function simply calls C{count_isomorphisms_vf2} with the graph 916 itself. See C{count_isomorphisms_vf2} for an explanation of the 917 parameters. 918 919 @return: the number of automorphisms of the graph 920 @see: Graph.count_isomorphisms_vf2 921 """ 922 return self.count_isomorphisms_vf2(self, color1=color, color2=color, 923 edge_color1=edge_color, edge_color2=edge_color, 924 node_compat_fn=node_compat_fn, edge_compat_fn=edge_compat_fn) 925
926 - def get_automorphisms_vf2(self, color=None, edge_color=None, 927 node_compat_fn=None, edge_compat_fn=None):
928 """Returns all the automorphisms of the graph 929 930 This function simply calls C{get_isomorphisms_vf2} with the graph 931 itself. See C{get_isomorphisms_vf2} for an explanation of the 932 parameters. 933 934 @return: a list of lists, each item containing a possible mapping 935 of the graph vertices to itself according to the automorphism 936 @see: Graph.get_isomorphisms_vf2 937 """ 938 return self.get_isomorphisms_vf2(self, color1=color, color2=color, 939 edge_color1=edge_color, edge_color2=edge_color, 940 node_compat_fn=node_compat_fn, edge_compat_fn=edge_compat_fn) 941 942 # Various clustering algorithms -- mostly wrappers around GraphBase
943 - def community_fastgreedy(self, weights=None):
944 """Community structure based on the greedy optimization of modularity. 945 946 This algorithm merges individual nodes into communities in a way that 947 greedily maximizes the modularity score of the graph. It can be proven 948 that if no merge can increase the current modularity score, the 949 algorithm can be stopped since no further increase can be achieved. 950 951 This algorithm is said to run almost in linear time on sparse graphs. 952 953 @param weights: edge attribute name or a list containing edge 954 weights 955 @return: an appropriate L{VertexDendrogram} object. 956 957 @newfield ref: Reference 958 @ref: A Clauset, MEJ Newman and C Moore: Finding community structure 959 in very large networks. Phys Rev E 70, 066111 (2004). 960 """ 961 merges, qs = GraphBase.community_fastgreedy(self, weights) 962 963 # qs may be shorter than |V|-1 if we are left with a few separated 964 # communities in the end; take this into account 965 diff = self.vcount() - len(qs) 966 qs.reverse() 967 if qs: 968 optimal_count = qs.index(max(qs)) + diff + 1 969 else: 970 optimal_count = diff 971 972 return VertexDendrogram(self, merges, optimal_count, 973 modularity_params=dict(weights=weights)) 974
975 - def community_infomap(self, edge_weights=None, vertex_weights=None, trials=10):
976 """Finds the community structure of the network according to the Infomap 977 method of Martin Rosvall and Carl T. Bergstrom. 978 979 @param edge_weights: name of an edge attribute or a list containing 980 edge weights. 981 @param vertex_weights: name of an vertex attribute or a list containing 982 vertex weights. 983 @param trials: the number of attempts to partition the network. 984 @return: an appropriate L{VertexClustering} object with an extra attribute 985 called C{codelength} that stores the code length determined by the 986 algorithm. 987 988 @newfield ref: Reference 989 @ref: M. Rosvall and C. T. Bergstrom: Maps of information flow reveal 990 community structure in complex networks, PNAS 105, 1118 (2008). 991 U{http://dx.doi.org/10.1073/pnas.0706851105}, 992 U{http://arxiv.org/abs/0707.0609}. 993 @ref: M. Rosvall, D. Axelsson, and C. T. Bergstrom: The map equation, 994 Eur. Phys. J. Special Topics 178, 13 (2009). 995 U{http://dx.doi.org/10.1140/epjst/e2010-01179-1}, 996 U{http://arxiv.org/abs/0906.1405}. 997 """ 998 membership, codelength = \ 999 GraphBase.community_infomap(self, edge_weights, vertex_weights, trials) 1000 return VertexClustering(self, membership, \ 1001 params={"codelength": codelength}, \ 1002 modularity_params={"weights": edge_weights} ) 1003
1004 - def community_leading_eigenvector_naive(self, clusters = None, \ 1005 return_merges = False):
1006 """community_leading_eigenvector_naive(clusters=None, 1007 return_merges=False) 1008 1009 A naive implementation of Newman's eigenvector community structure 1010 detection. This function splits the network into two components 1011 according to the leading eigenvector of the modularity matrix and 1012 then recursively takes the given number of steps by splitting the 1013 communities as individual networks. This is not the correct way, 1014 however, see the reference for explanation. Consider using the 1015 correct L{community_leading_eigenvector} method instead. 1016 1017 @param clusters: the desired number of communities. If C{None}, the 1018 algorithm tries to do as many splits as possible. Note that the 1019 algorithm won't split a community further if the signs of the leading 1020 eigenvector are all the same, so the actual number of discovered 1021 communities can be less than the desired one. 1022 @param return_merges: whether the returned object should be a 1023 dendrogram instead of a single clustering. 1024 @return: an appropriate L{VertexClustering} or L{VertexDendrogram} 1025 object. 1026 1027 @newfield ref: Reference 1028 @ref: MEJ Newman: Finding community structure in networks using the 1029 eigenvectors of matrices, arXiv:physics/0605087""" 1030 if clusters is None: 1031 clusters = -1 1032 cl, merges, q = GraphBase.community_leading_eigenvector_naive(self, \ 1033 clusters, return_merges) 1034 if merges is None: 1035 return VertexClustering(self, cl, modularity = q) 1036 else: 1037 return VertexDendrogram(self, merges, safemax(cl)+1) 1038 1039
1040 - def community_leading_eigenvector(self, clusters=None, weights=None, \ 1041 arpack_options=None):
1042 """community_leading_eigenvector(clusters=None, weights=None, 1043 arpack_options=None) 1044 1045 Newman's leading eigenvector method for detecting community structure. 1046 This is the proper implementation of the recursive, divisive algorithm: 1047 each split is done by maximizing the modularity regarding the 1048 original network. 1049 1050 @param clusters: the desired number of communities. If C{None}, the 1051 algorithm tries to do as many splits as possible. Note that the 1052 algorithm won't split a community further if the signs of the leading 1053 eigenvector are all the same, so the actual number of discovered 1054 communities can be less than the desired one. 1055 @param weights: name of an edge attribute or a list containing 1056 edge weights. 1057 @param arpack_options: an L{ARPACKOptions} object used to fine-tune 1058 the ARPACK eigenvector calculation. If omitted, the module-level 1059 variable called C{arpack_options} is used. 1060 @return: an appropriate L{VertexClustering} object. 1061 1062 @newfield ref: Reference 1063 @ref: MEJ Newman: Finding community structure in networks using the 1064 eigenvectors of matrices, arXiv:physics/0605087""" 1065 if clusters is None: 1066 clusters = -1 1067 1068 kwds = dict(weights=weights) 1069 if arpack_options is not None: 1070 kwds["arpack_options"] = arpack_options 1071 1072 membership, _, q = GraphBase.community_leading_eigenvector(self, clusters, **kwds) 1073 return VertexClustering(self, membership, modularity = q) 1074 1075
1076 - def community_label_propagation(self, weights = None, initial = None, \ 1077 fixed = None):
1078 """community_label_propagation(weights=None, initial=None, fixed=None) 1079 1080 Finds the community structure of the graph according to the label 1081 propagation method of Raghavan et al. 1082 Initially, each vertex is assigned a different label. After that, 1083 each vertex chooses the dominant label in its neighbourhood in each 1084 iteration. Ties are broken randomly and the order in which the 1085 vertices are updated is randomized before every iteration. The 1086 algorithm ends when vertices reach a consensus. 1087 Note that since ties are broken randomly, there is no guarantee that 1088 the algorithm returns the same community structure after each run. 1089 In fact, they frequently differ. See the paper of Raghavan et al 1090 on how to come up with an aggregated community structure. 1091 @param weights: name of an edge attribute or a list containing 1092 edge weights 1093 @param initial: name of a vertex attribute or a list containing 1094 the initial vertex labels. Labels are identified by integers from 1095 zero to M{n-1} where M{n} is the number of vertices. Negative 1096 numbers may also be present in this vector, they represent unlabeled 1097 vertices. 1098 @param fixed: a list of booleans for each vertex. C{True} corresponds 1099 to vertices whose labeling should not change during the algorithm. 1100 It only makes sense if initial labels are also given. Unlabeled 1101 vertices cannot be fixed. 1102 @return: an appropriate L{VertexClustering} object. 1103 1104 @newfield ref: Reference 1105 @ref: Raghavan, U.N. and Albert, R. and Kumara, S. Near linear 1106 time algorithm to detect community structures in large-scale 1107 networks. Phys Rev E 76:036106, 2007. 1108 U{http://arxiv.org/abs/0709.2938}. 1109 """ 1110 if isinstance(fixed, basestring): 1111 fixed = [bool(o) for o in g.vs[fixed]] 1112 cl = GraphBase.community_label_propagation(self, \ 1113 weights, initial, fixed) 1114 return VertexClustering(self, cl, 1115 modularity_params=dict(weights=weights)) 1116 1117
1118 - def community_multilevel(self, weights=None, return_levels=False):
1119 """Community structure based on the multilevel algorithm of 1120 Blondel et al. 1121 1122 This is a bottom-up algorithm: initially every vertex belongs to a 1123 separate community, and vertices are moved between communities 1124 iteratively in a way that maximizes the vertices' local contribution 1125 to the overall modularity score. When a consensus is reached (i.e. no 1126 single move would increase the modularity score), every community in 1127 the original graph is shrank to a single vertex (while keeping the 1128 total weight of the adjacent edges) and the process continues on the 1129 next level. The algorithm stops when it is not possible to increase 1130 the modularity any more after shrinking the communities to vertices. 1131 1132 This algorithm is said to run almost in linear time on sparse graphs. 1133 1134 @param weights: edge attribute name or a list containing edge 1135 weights 1136 @param return_levels: if C{True}, the communities at each level are 1137 returned in a list. If C{False}, only the community structure with 1138 the best modularity is returned. 1139 @return: a list of L{VertexClustering} objects, one corresponding to 1140 each level (if C{return_levels} is C{True}), or a L{VertexClustering} 1141 corresponding to the best modularity. 1142 1143 @newfield ref: Reference 1144 @ref: VD Blondel, J-L Guillaume, R Lambiotte and E Lefebvre: Fast 1145 unfolding of community hierarchies in large networks, J Stat Mech 1146 P10008 (2008), http://arxiv.org/abs/0803.0476 1147 """ 1148 if self.is_directed(): 1149 raise ValueError("input graph must be undirected") 1150 1151 if return_levels: 1152 levels, qs = GraphBase.community_multilevel(self, weights, True) 1153 result = [] 1154 for level, q in zip(levels, qs): 1155 result.append(VertexClustering(self, level, q, 1156 modularity_params=dict(weights=weights))) 1157 else: 1158 membership = GraphBase.community_multilevel(self, weights, False) 1159 result = VertexClustering(self, membership, 1160 modularity_params=dict(weights=weights)) 1161 return result 1162
1163 - def community_optimal_modularity(self, *args, **kwds):
1164 """Calculates the optimal modularity score of the graph and the 1165 corresponding community structure. 1166 1167 This function uses the GNU Linear Programming Kit to solve a large 1168 integer optimization problem in order to find the optimal modularity 1169 score and the corresponding community structure, therefore it is 1170 unlikely to work for graphs larger than a few (less than a hundred) 1171 vertices. Consider using one of the heuristic approaches instead if 1172 you have such a large graph. 1173 1174 @return: the calculated membership vector and the corresponding 1175 modularity in a tuple.""" 1176 membership, modularity = \ 1177 GraphBase.community_optimal_modularity(self, *args, **kwds) 1178 return VertexClustering(self, membership, modularity) 1179
1180 - def community_edge_betweenness(self, clusters=None, directed=True, 1181 weights=None):
1182 """Community structure based on the betweenness of the edges in the 1183 network. 1184 1185 The idea is that the betweenness of the edges connecting two 1186 communities is typically high, as many of the shortest paths between 1187 nodes in separate communities go through them. So we gradually remove 1188 the edge with the highest betweenness and recalculate the betweennesses 1189 after every removal. This way sooner or later the network falls of to 1190 separate components. The result of the clustering will be represented 1191 by a dendrogram. 1192 1193 @param clusters: the number of clusters we would like to see. This 1194 practically defines the "level" where we "cut" the dendrogram to 1195 get the membership vector of the vertices. If C{None}, the dendrogram 1196 is cut at the level which maximizes the modularity. 1197 @param directed: whether the directionality of the edges should be 1198 taken into account or not. 1199 @param weights: name of an edge attribute or a list containing 1200 edge weights. 1201 @return: a L{VertexDendrogram} object, initally cut at the maximum 1202 modularity or at the desired number of clusters. 1203 """ 1204 merges, qs = GraphBase.community_edge_betweenness(self, directed, weights) 1205 qs.reverse() 1206 if clusters is None: 1207 if qs: 1208 clusters = qs.index(max(qs))+1 1209 else: 1210 clusters = 1 1211 return VertexDendrogram(self, merges, clusters, 1212 modularity_params=dict(weights=weights)) 1213
1214 - def community_spinglass(self, *args, **kwds):
1215 """community_spinglass(weights=None, spins=25, parupdate=False, 1216 start_temp=1, stop_temp=0.01, cool_fact=0.99, update_rule="config", 1217 gamma=1, implementation="orig", lambda_=1) 1218 1219 Finds the community structure of the graph according to the 1220 spinglass community detection method of Reichardt & Bornholdt. 1221 1222 @keyword weights: edge weights to be used. Can be a sequence or 1223 iterable or even an edge attribute name. 1224 @keyword spins: integer, the number of spins to use. This is the 1225 upper limit for the number of communities. It is not a problem 1226 to supply a (reasonably) big number here, in which case some 1227 spin states will be unpopulated. 1228 @keyword parupdate: whether to update the spins of the vertices in 1229 parallel (synchronously) or not 1230 @keyword start_temp: the starting temperature 1231 @keyword stop_temp: the stop temperature 1232 @keyword cool_fact: cooling factor for the simulated annealing 1233 @keyword update_rule: specifies the null model of the simulation. 1234 Possible values are C{"config"} (a random graph with the same 1235 vertex degrees as the input graph) or C{"simple"} (a random 1236 graph with the same number of edges) 1237 @keyword gamma: the gamma argument of the algorithm, specifying the 1238 balance between the importance of present and missing edges 1239 within a community. The default value of 1.0 assigns equal 1240 importance to both of them. 1241 @keyword implementation: currently igraph contains two implementations 1242 of the spinglass community detection algorithm. The faster 1243 original implementation is the default. The other implementation 1244 is able to take into account negative weights, this can be 1245 chosen by setting C{implementation} to C{"neg"} 1246 @keyword lambda_: the lambda argument of the algorithm, which 1247 specifies the balance between the importance of present and missing 1248 negatively weighted edges within a community. Smaller values of 1249 lambda lead to communities with less negative intra-connectivity. 1250 If the argument is zero, the algorithm reduces to a graph coloring 1251 algorithm, using the number of spins as colors. This argument is 1252 ignored if the original implementation is used. Note the underscore 1253 at the end of the argument name; this is due to the fact that 1254 lambda is a reserved keyword in Python. 1255 @return: an appropriate L{VertexClustering} object. 1256 1257 @newfield ref: Reference 1258 @ref: Reichardt J and Bornholdt S: Statistical mechanics of 1259 community detection. Phys Rev E 74:016110 (2006). 1260 U{http://arxiv.org/abs/cond-mat/0603718}. 1261 @ref: Traag VA and Bruggeman J: Community detection in networks 1262 with positive and negative links. Phys Rev E 80:036115 (2009). 1263 U{http://arxiv.org/abs/0811.2329}. 1264 """ 1265 membership = GraphBase.community_spinglass(self, *args, **kwds) 1266 if "weights" in kwds: 1267 modularity_params=dict(weights=kwds["weights"]) 1268 else: 1269 modularity_params={} 1270 return VertexClustering(self, membership, 1271 modularity_params=modularity_params) 1272
1273 - def community_walktrap(self, weights=None, steps=4):
1274 """Community detection algorithm of Latapy & Pons, based on random 1275 walks. 1276 1277 The basic idea of the algorithm is that short random walks tend to stay 1278 in the same community. The result of the clustering will be represented 1279 as a dendrogram. 1280 1281 @param weights: name of an edge attribute or a list containing 1282 edge weights 1283 @param steps: length of random walks to perform 1284 1285 @return: a L{VertexDendrogram} object, initially cut at the maximum 1286 modularity. 1287 1288 @newfield ref: Reference 1289 @ref: Pascal Pons, Matthieu Latapy: Computing communities in large 1290 networks using random walks, U{http://arxiv.org/abs/physics/0512106}. 1291 """ 1292 merges, qs = GraphBase.community_walktrap(self, weights, steps) 1293 qs.reverse() 1294 if qs: 1295 optimal_count = qs.index(max(qs))+1 1296 else: 1297 optimal_count = 1 1298 return VertexDendrogram(self, merges, optimal_count, 1299 modularity_params=dict(weights=weights)) 1300
1301 - def k_core(self, *args):
1302 """Returns some k-cores of the graph. 1303 1304 The method accepts an arbitrary number of arguments representing 1305 the desired indices of the M{k}-cores to be returned. The arguments 1306 can also be lists or tuples. The result is a single L{Graph} object 1307 if an only integer argument was given, otherwise the result is a 1308 list of L{Graph} objects representing the desired k-cores in the 1309 order the arguments were specified. If no argument is given, returns 1310 all M{k}-cores in increasing order of M{k}. 1311 """ 1312 if len(args) == 0: 1313 indices = xrange(self.vcount()) 1314 return_single = False 1315 else: 1316 return_single = True 1317 indices = [] 1318 for arg in args: 1319 try: 1320 indices.extend(arg) 1321 except: 1322 indices.append(arg) 1323 1324 if len(indices)>1 or hasattr(args[0], "__iter__"): 1325 return_single = False 1326 1327 corenesses = self.coreness() 1328 result = [] 1329 vidxs = xrange(self.vcount()) 1330 for idx in indices: 1331 core_idxs = [vidx for vidx in vidxs if corenesses[vidx] >= idx] 1332 result.append(self.subgraph(core_idxs)) 1333 1334 if return_single: return result[0] 1335 return result 1336 1337
1338 - def layout(self, layout=None, *args, **kwds):
1339 """Returns the layout of the graph according to a layout algorithm. 1340 1341 Parameters and keyword arguments not specified here are passed to the 1342 layout algorithm directly. See the documentation of the layout 1343 algorithms for the explanation of these parameters. 1344 1345 Registered layout names understood by this method are: 1346 1347 - C{auto}, C{automatic}: automatic layout 1348 (see L{Graph.layout_auto}) 1349 1350 - C{bipartite}: bipartite layout (see L{Graph.layout_bipartite}) 1351 1352 - C{circle}, C{circular}: circular layout 1353 (see L{Graph.layout_circle}) 1354 1355 - C{drl}: DrL layout for large graphs (see L{Graph.layout_drl}) 1356 1357 - C{drl_3d}: 3D DrL layout for large graphs 1358 (see L{Graph.layout_drl}) 1359 1360 - C{fr}, C{fruchterman_reingold}: Fruchterman-Reingold layout 1361 (see L{Graph.layout_fruchterman_reingold}). 1362 1363 - C{fr_3d}, C{fr3d}, C{fruchterman_reingold_3d}: 3D Fruchterman- 1364 Reingold layout (see L{Graph.layout_fruchterman_reingold}). 1365 1366 - C{grid}: regular grid layout in 2D (see L{Graph.layout_grid}) 1367 1368 - C{grid_3d}: regular grid layout in 3D (see L{Graph.layout_grid_3d}) 1369 1370 - C{graphopt}: the graphopt algorithm (see L{Graph.layout_graphopt}) 1371 1372 - C{kk}, C{kamada_kawai}: Kamada-Kawai layout 1373 (see L{Graph.layout_kamada_kawai}) 1374 1375 - C{kk_3d}, C{kk3d}, C{kamada_kawai_3d}: 3D Kamada-Kawai layout 1376 (see L{Graph.layout_kamada_kawai}) 1377 1378 - C{lgl}, C{large}, C{large_graph}: Large Graph Layout 1379 (see L{Graph.layout_lgl}) 1380 1381 - C{mds}: multidimensional scaling layout (see L{Graph.layout_mds}) 1382 1383 - C{random}: random layout (see L{Graph.layout_random}) 1384 1385 - C{random_3d}: random 3D layout (see L{Graph.layout_random}) 1386 1387 - C{rt}, C{tree}, C{reingold_tilford}: Reingold-Tilford tree 1388 layout (see L{Graph.layout_reingold_tilford}) 1389 1390 - C{rt_circular}, C{reingold_tilford_circular}: circular 1391 Reingold-Tilford tree layout 1392 (see L{Graph.layout_reingold_tilford_circular}) 1393 1394 - C{sphere}, C{spherical}, C{circle_3d}, C{circular_3d}: spherical 1395 layout (see L{Graph.layout_circle}) 1396 1397 - C{star}: star layout (see L{Graph.layout_star}) 1398 1399 - C{sugiyama}: Sugiyama layout (see L{Graph.layout_sugiyama}) 1400 1401 @param layout: the layout to use. This can be one of the registered 1402 layout names or a callable which returns either a L{Layout} object or 1403 a list of lists containing the coordinates. If C{None}, uses the 1404 value of the C{plotting.layout} configuration key. 1405 @return: a L{Layout} object. 1406 """ 1407 if layout is None: 1408 layout = config["plotting.layout"] 1409 if hasattr(layout, "__call__"): 1410 method = layout 1411 else: 1412 layout = layout.lower() 1413 if layout[-3:] == "_3d": 1414 kwds["dim"] = 3 1415 layout = layout[:-3] 1416 elif layout[-2:] == "3d": 1417 kwds["dim"] = 3 1418 layout = layout[:-2] 1419 method = getattr(self.__class__, self._layout_mapping[layout]) 1420 if not hasattr(method, "__call__"): 1421 raise ValueError("layout method must be callable") 1422 l = method(self, *args, **kwds) 1423 if not isinstance(l, Layout): 1424 l = Layout(l) 1425 return l 1426
1427 - def layout_auto(self, *args, **kwds):
1428 """Chooses and runs a suitable layout function based on simple 1429 topological properties of the graph. 1430 1431 This function tries to choose an appropriate layout function for 1432 the graph using the following rules: 1433 1434 1. If the graph has an attribute called C{layout}, it will be 1435 used. It may either be a L{Layout} instance, a list of 1436 coordinate pairs, the name of a layout function, or a 1437 callable function which generates the layout when called 1438 with the graph as a parameter. 1439 1440 2. Otherwise, if the graph has vertex attributes called C{x} 1441 and C{y}, these will be used as coordinates in the layout. 1442 When a 3D layout is requested (by setting C{dim} to 3), 1443 a vertex attribute named C{z} will also be needed. 1444 1445 3. Otherwise, if the graph is connected and has at most 100 1446 vertices, the Kamada-Kawai layout will be used (see 1447 L{Graph.layout_kamada_kawai()}). 1448 1449 4. Otherwise, if the graph has at most 1000 vertices, the 1450 Fruchterman-Reingold layout will be used (see 1451 L{Graph.layout_fruchterman_reingold()}). 1452 1453 5. If everything else above failed, the DrL layout algorithm 1454 will be used (see L{Graph.layout_drl()}). 1455 1456 All the arguments of this function except C{dim} are passed on 1457 to the chosen layout function (in case we have to call some layout 1458 function). 1459 1460 @keyword dim: specifies whether we would like to obtain a 2D or a 1461 3D layout. 1462 @return: a L{Layout} object. 1463 """ 1464 if "layout" in self.attributes(): 1465 layout = self["layout"] 1466 if isinstance(layout, Layout): 1467 # Layouts are used intact 1468 return layout 1469 if isinstance(layout, (list, tuple)): 1470 # Lists/tuples are converted to layouts 1471 return Layout(layout) 1472 if hasattr(layout, "__call__"): 1473 # Callables are called 1474 return Layout(layout(*args, **kwds)) 1475 # Try Graph.layout() 1476 return self.layout(layout, *args, **kwds) 1477 1478 dim = kwds.get("dim", 2) 1479 vattrs = self.vertex_attributes() 1480 if "x" in vattrs and "y" in vattrs: 1481 if dim == 3 and "z" in vattrs: 1482 return Layout(zip(self.vs["x"], self.vs["y"], self.vs["z"])) 1483 else: 1484 return Layout(zip(self.vs["x"], self.vs["y"])) 1485 1486 if self.vcount() <= 100 and self.is_connected(): 1487 algo = "kk" 1488 elif self.vcount() <= 1000: 1489 algo = "fr" 1490 else: 1491 algo = "drl" 1492 return self.layout(algo, *args, **kwds) 1493
1494 - def layout_grid_fruchterman_reingold(self, *args, **kwds):
1495 """layout_grid_fruchterman_reingold(*args, **kwds) 1496 1497 Compatibility alias to the Fruchterman-Reingold layout with the grid 1498 option turned on. 1499 1500 @see: Graph.layout_fruchterman_reingold() 1501 """ 1502 deprecated("Graph.layout_grid_fruchterman_reingold() is deprecated since "\ 1503 "igraph 0.8, please use Graph.layout_fruchterman_reingold(grid=True) instead") 1504 kwds["grid"] = True 1505 return self.layout_fruchterman_reingold(*args, **kwds) 1506
1507 - def layout_sugiyama(self, layers=None, weights=None, hgap=1, vgap=1, 1508 maxiter=100, return_extended_graph=False):
1509 """layout_sugiyama(layers=None, weights=None, hgap=1, vgap=1, maxiter=100, 1510 return_extended_graph=False) 1511 1512 Places the vertices using a layered Sugiyama layout. 1513 1514 This is a layered layout that is most suitable for directed acyclic graphs, 1515 although it works on undirected or cyclic graphs as well. 1516 1517 Each vertex is assigned to a layer and each layer is placed on a horizontal 1518 line. Vertices within the same layer are then permuted using the barycenter 1519 heuristic that tries to minimize edge crossings. 1520 1521 Dummy vertices will be added on edges that span more than one layer. The 1522 returned layout therefore contains more rows than the number of nodes in 1523 the original graph; the extra rows correspond to the dummy vertices. 1524 1525 @param layers: a vector specifying a non-negative integer layer index for 1526 each vertex, or the name of a numeric vertex attribute that contains 1527 the layer indices. If C{None}, a layering will be determined 1528 automatically. For undirected graphs, a spanning tree will be extracted 1529 and vertices will be assigned to layers using a breadth first search from 1530 the node with the largest degree. For directed graphs, cycles are broken 1531 by reversing the direction of edges in an approximate feedback arc set 1532 using the heuristic of Eades, Lin and Smyth, and then using longest path 1533 layering to place the vertices in layers. 1534 @param weights: edge weights to be used. Can be a sequence or iterable or 1535 even an edge attribute name. 1536 @param hgap: minimum horizontal gap between vertices in the same layer. 1537 @param vgap: vertical gap between layers. The layer index will be 1538 multiplied by I{vgap} to obtain the Y coordinate. 1539 @param maxiter: maximum number of iterations to take in the crossing 1540 reduction step. Increase this if you feel that you are getting too many 1541 edge crossings. 1542 @param return_extended_graph: specifies that the extended graph with the 1543 added dummy vertices should also be returned. When this is C{True}, the 1544 result will be a tuple containing the layout and the extended graph. The 1545 first |V| nodes of the extended graph will correspond to the nodes of the 1546 original graph, the remaining ones are dummy nodes. Plotting the extended 1547 graph with the returned layout and hidden dummy nodes will produce a layout 1548 that is similar to the original graph, but with the added edge bends. 1549 The extended graph also contains an edge attribute called C{_original_eid} 1550 which specifies the ID of the edge in the original graph from which the 1551 edge of the extended graph was created. 1552 @return: the calculated layout, which may (and usually will) have more rows 1553 than the number of vertices; the remaining rows correspond to the dummy 1554 nodes introduced in the layering step. When C{return_extended_graph} is 1555 C{True}, it will also contain the extended graph. 1556 1557 @newfield ref: Reference 1558 @ref: K Sugiyama, S Tagawa, M Toda: Methods for visual understanding of 1559 hierarchical system structures. IEEE Systems, Man and Cybernetics\ 1560 11(2):109-125, 1981. 1561 @ref: P Eades, X Lin and WF Smyth: A fast effective heuristic for the 1562 feedback arc set problem. Information Processing Letters 47:319-323, 1993. 1563 """ 1564 if not return_extended_graph: 1565 return Layout(GraphBase._layout_sugiyama(self, layers, weights, hgap, 1566 vgap, maxiter, return_extended_graph)) 1567 1568 layout, extd_graph, extd_to_orig_eids = \ 1569 GraphBase._layout_sugiyama(self, layers, weights, hgap, 1570 vgap, maxiter, return_extended_graph) 1571 extd_graph.es["_original_eid"] = extd_to_orig_eids 1572 return Layout(layout), extd_graph 1573
1574 - def maximum_bipartite_matching(self, types="type", weights=None, eps=None):
1575 """Finds a maximum matching in a bipartite graph. 1576 1577 A maximum matching is a set of edges such that each vertex is incident on 1578 at most one matched edge and the number (or weight) of such edges in the 1579 set is as large as possible. 1580 1581 @param types: vertex types in a list or the name of a vertex attribute 1582 holding vertex types. Types should be denoted by zeros and ones (or 1583 C{False} and C{True}) for the two sides of the bipartite graph. 1584 If omitted, it defaults to C{type}, which is the default vertex type 1585 attribute for bipartite graphs. 1586 @param weights: edge weights to be used. Can be a sequence or iterable or 1587 even an edge attribute name. 1588 @param eps: a small real number used in equality tests in the weighted 1589 bipartite matching algorithm. Two real numbers are considered equal in 1590 the algorithm if their difference is smaller than this value. This 1591 is required to avoid the accumulation of numerical errors. If you 1592 pass C{None} here, igraph will try to determine an appropriate value 1593 automatically. 1594 @return: an instance of L{Matching}.""" 1595 if eps is None: 1596 eps = -1 1597 1598 matches = GraphBase._maximum_bipartite_matching(self, types, weights, eps) 1599 return Matching(self, matches, types=types) 1600 1601 ############################################# 1602 # Auxiliary I/O functions 1603
1604 - def write_adjacency(self, f, sep=" ", eol="\n", *args, **kwds):
1605 """Writes the adjacency matrix of the graph to the given file 1606 1607 All the remaining arguments not mentioned here are passed intact 1608 to L{Graph.get_adjacency}. 1609 1610 @param f: the name of the file to be written. 1611 @param sep: the string that separates the matrix elements in a row 1612 @param eol: the string that separates the rows of the matrix. Please 1613 note that igraph is able to read back the written adjacency matrix 1614 if and only if this is a single newline character 1615 """ 1616 if isinstance(f, basestring): 1617 f = open(f, "w") 1618 matrix = self.get_adjacency(*args, **kwds) 1619 for row in matrix: 1620 f.write(sep.join(map(str, row))) 1621 f.write(eol) 1622 f.close() 1623 1624 @classmethod
1625 - def Read_Adjacency(klass, f, sep=None, comment_char = "#", attribute=None, 1626 *args, **kwds):
1627 """Constructs a graph based on an adjacency matrix from the given file 1628 1629 Additional positional and keyword arguments not mentioned here are 1630 passed intact to L{Graph.Adjacency}. 1631 1632 @param f: the name of the file to be read or a file object 1633 @param sep: the string that separates the matrix elements in a row. 1634 C{None} means an arbitrary sequence of whitespace characters. 1635 @param comment_char: lines starting with this string are treated 1636 as comments. 1637 @param attribute: an edge attribute name where the edge weights are 1638 stored in the case of a weighted adjacency matrix. If C{None}, 1639 no weights are stored, values larger than 1 are considered as 1640 edge multiplicities. 1641 @return: the created graph""" 1642 if isinstance(f, basestring): 1643 f = open(f) 1644 matrix, ri, weights = [], 0, {} 1645 for line in f: 1646 line = line.strip() 1647 if len(line) == 0: continue 1648 if line.startswith(comment_char): continue 1649 row = [float(x) for x in line.split(sep)] 1650 matrix.append(row) 1651 ri += 1 1652 1653 f.close() 1654 1655 if attribute is None: 1656 graph=klass.Adjacency(matrix, *args, **kwds) 1657 else: 1658 kwds["attr"] = attribute 1659 graph=klass.Weighted_Adjacency(matrix, *args, **kwds) 1660 1661 return graph 1662
1663 - def write_dimacs(self, f, source=None, target=None, capacity="capacity"):
1664 """Writes the graph in DIMACS format to the given file. 1665 1666 @param f: the name of the file to be written or a Python file handle. 1667 @param source: the source vertex ID. If C{None}, igraph will try to 1668 infer it from the C{source} graph attribute. 1669 @param target: the target vertex ID. If C{None}, igraph will try to 1670 infer it from the C{target} graph attribute. 1671 @param capacity: the capacities of the edges in a list or the name of 1672 an edge attribute that holds the capacities. If there is no such 1673 edge attribute, every edge will have a capacity of 1. 1674 """ 1675 if source is None: 1676 source = self["source"] 1677 if target is None: 1678 target = self["target"] 1679 if isinstance(capacity, basestring) and \ 1680 capacity not in self.edge_attributes(): 1681 warn("'%s' edge attribute does not exist" % capacity) 1682 capacity = None 1683 return GraphBase.write_dimacs(self, f, source, target, capacity) 1684
1685 - def write_graphmlz(self, f, compresslevel=9):
1686 """Writes the graph to a zipped GraphML file. 1687 1688 The library uses the gzip compression algorithm, so the resulting 1689 file can be unzipped with regular gzip uncompression (like 1690 C{gunzip} or C{zcat} from Unix command line) or the Python C{gzip} 1691 module. 1692 1693 Uses a temporary file to store intermediate GraphML data, so 1694 make sure you have enough free space to store the unzipped 1695 GraphML file as well. 1696 1697 @param f: the name of the file to be written. 1698 @param compresslevel: the level of compression. 1 is fastest and 1699 produces the least compression, and 9 is slowest and produces 1700 the most compression.""" 1701 from igraph.utils import named_temporary_file 1702 with named_temporary_file() as tmpfile: 1703 self.write_graphml(tmpfile) 1704 outf = gzip.GzipFile(f, "wb", compresslevel) 1705 copyfileobj(open(tmpfile, "rb"), outf) 1706 outf.close() 1707 1708 @classmethod
1709 - def Read_DIMACS(cls, f, directed=False):
1710 """Read_DIMACS(f, directed=False) 1711 1712 Reads a graph from a file conforming to the DIMACS minimum-cost flow 1713 file format. 1714 1715 For the exact definition of the format, see 1716 U{http://lpsolve.sourceforge.net/5.5/DIMACS.htm}. 1717 1718 Restrictions compared to the official description of the format are 1719 as follows: 1720 1721 - igraph's DIMACS reader requires only three fields in an arc 1722 definition, describing the edge's source and target node and 1723 its capacity. 1724 - Source vertices are identified by 's' in the FLOW field, target 1725 vertices are identified by 't'. 1726 - Node indices start from 1. Only a single source and target node 1727 is allowed. 1728 1729 @param f: the name of the file or a Python file handle 1730 @param directed: whether the generated graph should be directed. 1731 @return: the generated graph. The indices of the source and target 1732 vertices are attached as graph attributes C{source} and C{target}, 1733 the edge capacities are stored in the C{capacity} edge attribute. 1734 """ 1735 graph, source, target, cap = super(Graph, cls).Read_DIMACS(f, directed) 1736 graph.es["capacity"] = cap 1737 graph["source"] = source 1738 graph["target"] = target 1739 return graph 1740 1741 @classmethod
1742 - def Read_GraphMLz(cls, f, *params, **kwds):
1743 """Read_GraphMLz(f, directed=True, index=0) 1744 1745 Reads a graph from a zipped GraphML file. 1746 1747 @param f: the name of the file 1748 @param index: if the GraphML file contains multiple graphs, 1749 specified the one that should be loaded. Graph indices 1750 start from zero, so if you want to load the first graph, 1751 specify 0 here. 1752 @return: the loaded graph object""" 1753 from igraph.utils import named_temporary_file 1754 with named_temporary_file() as tmpfile: 1755 outf = open(tmpfile, "wb") 1756 copyfileobj(gzip.GzipFile(f, "rb"), outf) 1757 outf.close() 1758 return cls.Read_GraphML(tmpfile) 1759
1760 - def write_pickle(self, fname=None, version=-1):
1761 """Saves the graph in Python pickled format 1762 1763 @param fname: the name of the file or a stream to save to. If 1764 C{None}, saves the graph to a string and returns the string. 1765 @param version: pickle protocol version to be used. If -1, uses 1766 the highest protocol available 1767 @return: C{None} if the graph was saved successfully to the 1768 given file, or a string if C{fname} was C{None}. 1769 """ 1770 import cPickle as pickle 1771 if fname is None: 1772 return pickle.dumps(self, version) 1773 if not hasattr(fname, "write"): 1774 file_was_opened = True 1775 fname = open(fname, 'wb') 1776 else: 1777 file_was_opened=False 1778 result=pickle.dump(self, fname, version) 1779 if file_was_opened: 1780 fname.close() 1781 return result 1782
1783 - def write_picklez(self, fname=None, version=-1):
1784 """Saves the graph in Python pickled format, compressed with 1785 gzip. 1786 1787 Saving in this format is a bit slower than saving in a Python pickle 1788 without compression, but the final file takes up much less space on 1789 the hard drive. 1790 1791 @param fname: the name of the file or a stream to save to. 1792 @param version: pickle protocol version to be used. If -1, uses 1793 the highest protocol available 1794 @return: C{None} if the graph was saved successfully to the 1795 given file. 1796 """ 1797 import cPickle as pickle 1798 if not hasattr(fname, "write"): 1799 file_was_opened = True 1800 fname = gzip.open(fname, "wb") 1801 elif not isinstance(fname, gzip.GzipFile): 1802 file_was_opened = True 1803 fname = gzip.GzipFile(mode="wb", fileobj=fname) 1804 else: 1805 file_Was_opened = False 1806 result = pickle.dump(self, fname, version) 1807 if file_was_opened: 1808 fname.close() 1809 return result 1810 1811 @classmethod
1812 - def Read_Pickle(klass, fname=None):
1813 """Reads a graph from Python pickled format 1814 1815 @param fname: the name of the file, a stream to read from, or 1816 a string containing the pickled data. The string is assumed to 1817 hold pickled data if it is longer than 40 characters and 1818 contains a substring that's peculiar to pickled versions 1819 of an C{igraph} Graph object. 1820 @return: the created graph object. 1821 """ 1822 import cPickle as pickle 1823 if hasattr(fname, "read"): 1824 # Probably a file or a file-like object 1825 result = pickle.load(fname) 1826 else: 1827 fp = None 1828 try: 1829 fp = open(fname, "rb") 1830 except IOError: 1831 # No file with the given name, try unpickling directly 1832 result = pickle.loads(fname) 1833 if fp is not None: 1834 result = pickle.load(fp) 1835 fp.close() 1836 return result 1837 1838 @classmethod
1839 - def Read_Picklez(klass, fname, *args, **kwds):
1840 """Reads a graph from compressed Python pickled format, uncompressing 1841 it on-the-fly. 1842 1843 @param fname: the name of the file or a stream to read from. 1844 @return: the created graph object. 1845 """ 1846 import cPickle as pickle 1847 if hasattr(fname, "read"): 1848 # Probably a file or a file-like object 1849 if isinstance(fname, gzip.GzipFile): 1850 result = pickle.load(fname) 1851 else: 1852 result = pickle.load(gzip.GzipFile(mode="rb", fileobj=fname)) 1853 else: 1854 result = pickle.load(gzip.open(fname, "rb")) 1855 return result 1856 1857 @classmethod
1858 - def Read_Picklez(klass, fname, *args, **kwds):
1859 """Reads a graph from compressed Python pickled format, uncompressing 1860 it on-the-fly. 1861 1862 @param fname: the name of the file or a stream to read from. 1863 @return: the created graph object. 1864 """ 1865 import cPickle as pickle 1866 if hasattr(fname, "read"): 1867 # Probably a file or a file-like object 1868 if isinstance(fname, gzip.GzipFile): 1869 result = pickle.load(fname) 1870 else: 1871 result = pickle.load(gzip.GzipFile(mode="rb", fileobj=fname)) 1872 else: 1873 result = pickle.load(gzip.open(fname, "rb")) 1874 if not isinstance(result, klass): 1875 raise TypeError("unpickled object is not a %s" % klass.__name__) 1876 return result 1877 1878 # pylint: disable-msg=C0301,C0323 1879 # C0301: line too long. 1880 # C0323: operator not followed by a space - well, print >>f looks OK
1881 - def write_svg(self, fname, layout="auto", width=None, height=None, \ 1882 labels="label", colors="color", shapes="shape", \ 1883 vertex_size=10, edge_colors="color", \ 1884 edge_stroke_widths="width", \ 1885 font_size=16, *args, **kwds):
1886 """Saves the graph as an SVG (Scalable Vector Graphics) file 1887 1888 The file will be Inkscape (http://inkscape.org) compatible. 1889 In Inkscape, as nodes are rearranged, the edges auto-update. 1890 1891 @param fname: the name of the file or a Python file handle 1892 @param layout: the layout of the graph. Can be either an 1893 explicitly specified layout (using a list of coordinate 1894 pairs) or the name of a layout algorithm (which should 1895 refer to a method in the L{Graph} object, but without 1896 the C{layout_} prefix. 1897 @param width: the preferred width in pixels (default: 400) 1898 @param height: the preferred height in pixels (default: 400) 1899 @param labels: the vertex labels. Either it is the name of 1900 a vertex attribute to use, or a list explicitly specifying 1901 the labels. It can also be C{None}. 1902 @param colors: the vertex colors. Either it is the name of 1903 a vertex attribute to use, or a list explicitly specifying 1904 the colors. A color can be anything acceptable in an SVG 1905 file. 1906 @param shapes: the vertex shapes. Either it is the name of 1907 a vertex attribute to use, or a list explicitly specifying 1908 the shapes as integers. Shape 0 means hidden (nothing is drawn), 1909 shape 1 is a circle, shape 2 is a rectangle and shape 3 is a 1910 rectangle that automatically sizes to the inner text. 1911 @param vertex_size: vertex size in pixels 1912 @param edge_colors: the edge colors. Either it is the name 1913 of an edge attribute to use, or a list explicitly specifying 1914 the colors. A color can be anything acceptable in an SVG 1915 file. 1916 @param edge_stroke_widths: the stroke widths of the edges. Either 1917 it is the name of an edge attribute to use, or a list explicitly 1918 specifying the stroke widths. The stroke width can be anything 1919 acceptable in an SVG file. 1920 @param font_size: font size. If it is a string, it is written into 1921 the SVG file as-is (so you can specify anything which is valid 1922 as the value of the C{font-size} style). If it is a number, it 1923 is interpreted as pixel size and converted to the proper attribute 1924 value accordingly. 1925 """ 1926 if width is None and height is None: 1927 width = 400 1928 height = 400 1929 elif width is None: 1930 width = height 1931 elif height is None: 1932 height = width 1933 1934 if width <= 0 or height <= 0: 1935 raise ValueError("width and height must be positive") 1936 1937 if isinstance(layout, str): 1938 layout = self.layout(layout, *args, **kwds) 1939 1940 if isinstance(labels, str): 1941 try: 1942 labels = self.vs.get_attribute_values(labels) 1943 except KeyError: 1944 labels = [x+1 for x in xrange(self.vcount())] 1945 elif labels is None: 1946 labels = [""] * self.vcount() 1947 1948 if isinstance(colors, str): 1949 try: 1950 colors = self.vs.get_attribute_values(colors) 1951 except KeyError: 1952 colors = ["red"] * self.vcount() 1953 1954 if isinstance(shapes, str): 1955 try: 1956 shapes = self.vs.get_attribute_values(shapes) 1957 except KeyError: 1958 shapes = [1] * self.vcount() 1959 1960 if isinstance(edge_colors, str): 1961 try: 1962 edge_colors = self.es.get_attribute_values(edge_colors) 1963 except KeyError: 1964 edge_colors = ["black"] * self.ecount() 1965 1966 if isinstance(edge_stroke_widths, str): 1967 try: 1968 edge_stroke_widths = self.es.get_attribute_values(edge_stroke_widths) 1969 except KeyError: 1970 edge_stroke_widths = [2] * self.ecount() 1971 1972 if not isinstance(font_size, str): 1973 font_size = "%spx" % str(font_size) 1974 else: 1975 if ";" in font_size: 1976 raise ValueError("font size can't contain a semicolon") 1977 1978 vcount = self.vcount() 1979 labels.extend(str(i+1) for i in xrange(len(labels), vcount)) 1980 colors.extend(["red"] * (vcount - len(colors))) 1981 1982 if isinstance(fname, basestring): 1983 f = open(fname, "w") 1984 our_file = True 1985 else: 1986 f = fname 1987 our_file = False 1988 1989 bbox = BoundingBox(layout.bounding_box()) 1990 1991 sizes = [width-2*vertex_size, height-2*vertex_size] 1992 w, h = bbox.width, bbox.height 1993 1994 ratios = [] 1995 if w == 0: 1996 ratios.append(1.0) 1997 else: 1998 ratios.append(sizes[0] / w) 1999 if h == 0: 2000 ratios.append(1.0) 2001 else: 2002 ratios.append(sizes[1] / h) 2003 2004 layout = [[(row[0] - bbox.left) * ratios[0] + vertex_size, \ 2005 (row[1] - bbox.top) * ratios[1] + vertex_size] \ 2006 for row in layout] 2007 2008 directed = self.is_directed() 2009 2010 print >> f, '<?xml version="1.0" encoding="UTF-8" standalone="no"?>' 2011 print >> f, '<!-- Created by igraph (http://igraph.org/) for use in Inkscape (http://www.inkscape.org/) -->' 2012 print >> f 2013 print >> f, '<svg xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://creativecommons.org/ns#" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:svg="http://www.w3.org/2000/svg" xmlns="http://www.w3.org/2000/svg" xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"' 2014 print >> f, 'width="{0}px" height="{1}px">'.format(width, height), 2015 2016 2017 edge_color_dict = {} 2018 print >> f, '<defs id="defs3">' 2019 for e_col in set(edge_colors): 2020 if e_col == "#000000": 2021 marker_index = "" 2022 else: 2023 marker_index = str(len(edge_color_dict)) 2024 # Print an arrow marker for each possible line color 2025 # This is a copy of Inkscape's standard Arrow 2 marker 2026 print >> f, '<marker' 2027 print >> f, ' inkscape:stockid="Arrow2Lend{0}"'.format(marker_index) 2028 print >> f, ' orient="auto"' 2029 print >> f, ' refY="0.0"' 2030 print >> f, ' refX="0.0"' 2031 print >> f, ' id="Arrow2Lend{0}"'.format(marker_index) 2032 print >> f, ' style="overflow:visible;">' 2033 print >> f, ' <path' 2034 print >> f, ' id="pathArrow{0}"'.format(marker_index) 2035 print >> f, ' style="font-size:12.0;fill-rule:evenodd;stroke-width:0.62500000;stroke-linejoin:round;fill:{0}"'.format(e_col) 2036 print >> f, ' d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.9730900,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z "' 2037 print >> f, ' transform="scale(1.1) rotate(180) translate(1,0)" />' 2038 print >> f, '</marker>' 2039 2040 edge_color_dict[e_col] = "Arrow2Lend{0}".format(marker_index) 2041 print >> f, '</defs>' 2042 print >> f, '<g inkscape:groupmode="layer" id="layer2" inkscape:label="Lines" sodipodi:insensitive="true">' 2043 2044 for eidx, edge in enumerate(self.es): 2045 vidxs = edge.tuple 2046 x1 = layout[vidxs[0]][0] 2047 y1 = layout[vidxs[0]][1] 2048 x2 = layout[vidxs[1]][0] 2049 y2 = layout[vidxs[1]][1] 2050 angle = math.atan2(y2 - y1, x2 - x1) 2051 x2 = x2 - vertex_size * math.cos(angle) 2052 y2 = y2 - vertex_size * math.sin(angle) 2053 2054 print >> f, '<path' 2055 print >> f, ' style="fill:none;stroke:{0};stroke-width:{2};stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none{1}"'\ 2056 .format(edge_colors[eidx], ";marker-end:url(#{0})".\ 2057 format(edge_color_dict[edge_colors[eidx]]) \ 2058 if directed else "", edge_stroke_widths[eidx]) 2059 print >> f, ' d="M {0},{1} {2},{3}"'.format(x1, y1, x2, y2) 2060 print >> f, ' id="path{0}"'.format(eidx) 2061 print >> f, ' inkscape:connector-type="polyline"' 2062 print >> f, ' inkscape:connector-curvature="0"' 2063 print >> f, ' inkscape:connection-start="#g{0}"'.format(edge.source) 2064 print >> f, ' inkscape:connection-start-point="d4"' 2065 print >> f, ' inkscape:connection-end="#g{0}"'.format(edge.target) 2066 print >> f, ' inkscape:connection-end-point="d4" />' 2067 2068 print >> f, " </g>" 2069 print >> f 2070 2071 print >> f, ' <g inkscape:label="Nodes" \ 2072 inkscape:groupmode="layer" id="layer1">' 2073 print >> f, ' <!-- Vertices -->' 2074 2075 if any(x == 3 for x in shapes): 2076 # Only import tkFont if we really need it. Unfortunately, this will 2077 # flash up an unneccesary Tk window in some cases 2078 import tkFont 2079 import Tkinter as tk 2080 # This allows us to dynamically size the width of the nodes 2081 font = tkFont.Font(root=tk.Tk(), font=("Sans", font_size, tkFont.NORMAL)) 2082 2083 for vidx in range(self.vcount()): 2084 print >> f, ' <g id="g{0}" transform="translate({1},{2})">'.\ 2085 format(vidx, layout[vidx][0], layout[vidx][1]) 2086 if shapes[vidx] == 1: 2087 # Undocumented feature: can handle two colors but only for circles 2088 c = str(colors[vidx]) 2089 if " " in c: 2090 c = c.split(" ") 2091 vs = str(vertex_size) 2092 print >> f, ' <path d="M -{0},0 A{0},{0} 0 0,0 {0},0 L \ 2093 -{0},0" fill="{1}"/>'.format(vs, c[0]) 2094 print >> f, ' <path d="M -{0},0 A{0},{0} 0 0,1 {0},0 L \ 2095 -{0},0" fill="{1}"/>'.format(vs, c[1]) 2096 print >> f, ' <circle cx="0" cy="0" r="{0}" fill="none"/>'\ 2097 .format(vs) 2098 else: 2099 print >> f, ' <circle cx="0" cy="0" r="{0}" fill="{1}"/>'.\ 2100 format(str(vertex_size), str(colors[vidx])) 2101 elif shapes[vidx] == 2: 2102 print >> f, ' <rect x="-{0}" y="-{0}" width="{1}" height="{1}" id="rect{2}" style="fill:{3};fill-opacity:1" />'.\ 2103 format(vertex_size, vertex_size * 2, vidx, colors[vidx]) 2104 elif shapes[vidx] == 3: 2105 (vertex_width, vertex_height) = (font.measure(str(labels[vidx])) + 2, font.metrics("linespace") + 2) 2106 print >> f, ' <rect ry="5" rx="5" x="-{0}" y="-{1}" width="{2}" height="{3}" id="rect{4}" style="fill:{5};fill-opacity:1" />'.\ 2107 format(vertex_width / 2., vertex_height / 2., vertex_width, vertex_height, vidx, colors[vidx]) 2108 2109 print >> f, ' <text sodipodi:linespacing="125%" y="{0}" x="0" id="text{1}" style="font-size:{2}px;font-style:normal;font-weight:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans">'.format(vertex_size / 2.,vidx, font_size) 2110 print >> f, '<tspan y="{0}" x="0" id="tspan{1}" sodipodi:role="line">{2}</tspan></text>'.format(vertex_size / 2.,vidx, str(labels[vidx])) 2111 print >> f, ' </g>' 2112 2113 print >> f, '</g>' 2114 print >> f 2115 print >> f, '</svg>' 2116 2117 if our_file: 2118 f.close() 2119 2120 2121 @classmethod
2122 - def _identify_format(klass, filename):
2123 """_identify_format(filename) 2124 2125 Tries to identify the format of the graph stored in the file with the 2126 given filename. It identifies most file formats based on the extension 2127 of the file (and not on syntactic evaluation). The only exception is 2128 the adjacency matrix format and the edge list format: the first few 2129 lines of the file are evaluated to decide between the two. 2130 2131 @note: Internal function, should not be called directly. 2132 2133 @param filename: the name of the file or a file object whose C{name} 2134 attribute is set. 2135 @return: the format of the file as a string. 2136 """ 2137 import os.path 2138 if hasattr(filename, "name") and hasattr(filename, "read"): 2139 # It is most likely a file 2140 try: 2141 filename=filename.name 2142 except: 2143 return None 2144 2145 root, ext = os.path.splitext(filename) 2146 ext = ext.lower() 2147 2148 if ext == ".gz": 2149 _, ext2 = os.path.splitext(root) 2150 ext2 = ext2.lower() 2151 if ext2 == ".pickle": 2152 return "picklez" 2153 elif ext2 == ".graphml": 2154 return "graphmlz" 2155 2156 if ext in [".graphml", ".graphmlz", ".lgl", ".ncol", ".pajek", 2157 ".gml", ".dimacs", ".edgelist", ".edges", ".edge", ".net", 2158 ".pickle", ".picklez", ".dot", ".gw", ".lgr", ".dl"]: 2159 return ext[1:] 2160 2161 if ext == ".txt" or ext == ".dat": 2162 # Most probably an adjacency matrix or an edge list 2163 f = open(filename, "r") 2164 line = f.readline() 2165 if line is None: 2166 return "edges" 2167 parts = line.strip().split() 2168 if len(parts) == 2: 2169 line = f.readline() 2170 if line is None: 2171 return "edges" 2172 parts = line.strip().split() 2173 if len(parts) == 2: 2174 line = f.readline() 2175 if line is None: 2176 # This is a 2x2 matrix, it can be a matrix or an edge 2177 # list as well and we cannot decide 2178 return None 2179 else: 2180 parts = line.strip().split() 2181 if len(parts) == 0: 2182 return None 2183 return "edges" 2184 else: 2185 # Not a matrix 2186 return None 2187 else: 2188 return "adjacency" 2189 2190 @classmethod
2191 - def Read(klass, f, format=None, *args, **kwds):
2192 """Unified reading function for graphs. 2193 2194 This method tries to identify the format of the graph given in 2195 the first parameter and calls the corresponding reader method. 2196 2197 The remaining arguments are passed to the reader method without 2198 any changes. 2199 2200 @param f: the file containing the graph to be loaded 2201 @param format: the format of the file (if known in advance). 2202 C{None} means auto-detection. Possible values are: C{"ncol"} 2203 (NCOL format), C{"lgl"} (LGL format), C{"graphdb"} (GraphDB 2204 format), C{"graphml"}, C{"graphmlz"} (GraphML and gzipped 2205 GraphML format), C{"gml"} (GML format), C{"net"}, C{"pajek"} 2206 (Pajek format), C{"dimacs"} (DIMACS format), C{"edgelist"}, 2207 C{"edges"} or C{"edge"} (edge list), C{"adjacency"} 2208 (adjacency matrix), C{"dl"} (DL format used by UCINET), 2209 C{"pickle"} (Python pickled format), 2210 C{"picklez"} (gzipped Python pickled format) 2211 @raises IOError: if the file format can't be identified and 2212 none was given. 2213 """ 2214 if format is None: 2215 format = klass._identify_format(f) 2216 try: 2217 reader = klass._format_mapping[format][0] 2218 except (KeyError, IndexError): 2219 raise IOError("unknown file format: %s" % str(format)) 2220 if reader is None: 2221 raise IOError("no reader method for file format: %s" % str(format)) 2222 reader = getattr(klass, reader) 2223 return reader(f, *args, **kwds) 2224 Load = Read 2225 2226
2227 - def write(self, f, format=None, *args, **kwds):
2228 """Unified writing function for graphs. 2229 2230 This method tries to identify the format of the graph given in 2231 the first parameter (based on extension) and calls the corresponding 2232 writer method. 2233 2234 The remaining arguments are passed to the writer method without 2235 any changes. 2236 2237 @param f: the file containing the graph to be saved 2238 @param format: the format of the file (if one wants to override the 2239 format determined from the filename extension, or the filename itself 2240 is a stream). C{None} means auto-detection. Possible values are: 2241 2242 - C{"adjacency"}: adjacency matrix format 2243 2244 - C{"dimacs"}: DIMACS format 2245 2246 - C{"dot"}, C{"graphviz"}: GraphViz DOT format 2247 2248 - C{"edgelist"}, C{"edges"} or C{"edge"}: numeric edge list format 2249 2250 - C{"gml"}: GML format 2251 2252 - C{"graphml"} and C{"graphmlz"}: standard and gzipped GraphML 2253 format 2254 2255 - C{"gw"}, C{"leda"}, C{"lgr"}: LEDA native format 2256 2257 - C{"lgl"}: LGL format 2258 2259 - C{"ncol"}: NCOL format 2260 2261 - C{"net"}, C{"pajek"}: Pajek format 2262 2263 - C{"pickle"}, C{"picklez"}: standard and gzipped Python pickled 2264 format 2265 2266 - C{"svg"}: SVG format 2267 2268 @raises IOError: if the file format can't be identified and 2269 none was given. 2270 """ 2271 if format is None: 2272 format = self._identify_format(f) 2273 try: 2274 writer = self._format_mapping[format][1] 2275 except (KeyError, IndexError): 2276 raise IOError("unknown file format: %s" % str(format)) 2277 if writer is None: 2278 raise IOError("no writer method for file format: %s" % str(format)) 2279 writer = getattr(self, writer) 2280 return writer(f, *args, **kwds) 2281 save = write 2282 2283 ##################################################### 2284 # Constructor for dict-like representation of graphs 2285 2286 @classmethod
2287 - def DictList(klass, vertices, edges, directed=False, \ 2288 vertex_name_attr="name", edge_foreign_keys=("source", "target"), \ 2289 iterative=False):
2290 """Constructs a graph from a list-of-dictionaries representation. 2291 2292 This representation assumes that vertices and edges are encoded in 2293 two lists, each list containing a Python dict for each vertex and 2294 each edge, respectively. A distinguished element of the vertex dicts 2295 contain a vertex ID which is used in the edge dicts to refer to 2296 source and target vertices. All the remaining elements of the dict 2297 are considered vertex and edge attributes. Note that the implementation 2298 does not assume that the objects passed to this method are indeed 2299 lists of dicts, but they should be iterable and they should yield 2300 objects that behave as dicts. So, for instance, a database query 2301 result is likely to be fit as long as it's iterable and yields 2302 dict-like objects with every iteration. 2303 2304 @param vertices: the data source for the vertices or C{None} if 2305 there are no special attributes assigned to vertices and we 2306 should simply use the edge list of dicts to infer vertex names. 2307 @param edges: the data source for the edges. 2308 @param directed: whether the constructed graph will be directed 2309 @param vertex_name_attr: the name of the distinguished key in the 2310 dicts in the vertex data source that contains the vertex names. 2311 Ignored if C{vertices} is C{None}. 2312 @param edge_foreign_keys: the name of the attributes in the dicts 2313 in the edge data source that contain the source and target 2314 vertex names. 2315 @param iterative: whether to add the edges to the graph one by one, 2316 iteratively, or to build a large edge list first and use that to 2317 construct the graph. The latter approach is faster but it may 2318 not be suitable if your dataset is large. The default is to 2319 add the edges in a batch from an edge list. 2320 @return: the graph that was constructed 2321 """ 2322 def create_list_from_indices(l, n): 2323 result = [None] * n 2324 for i, v in l: 2325 result[i] = v 2326 return result 2327 2328 # Construct the vertices 2329 vertex_attrs, n = {}, 0 2330 if vertices: 2331 for idx, vertex_data in enumerate(vertices): 2332 for k, v in vertex_data.iteritems(): 2333 try: 2334 vertex_attrs[k].append((idx, v)) 2335 except KeyError: 2336 vertex_attrs[k] = [(idx, v)] 2337 n += 1 2338 for k, v in vertex_attrs.iteritems(): 2339 vertex_attrs[k] = create_list_from_indices(v, n) 2340 else: 2341 vertex_attrs[vertex_name_attr] = [] 2342 2343 vertex_names = vertex_attrs[vertex_name_attr] 2344 # Check for duplicates in vertex_names 2345 if len(vertex_names) != len(set(vertex_names)): 2346 raise ValueError("vertex names are not unique") 2347 # Create a reverse mapping from vertex names to indices 2348 vertex_name_map = UniqueIdGenerator(initial = vertex_names) 2349 2350 # Construct the edges 2351 efk_src, efk_dest = edge_foreign_keys 2352 if iterative: 2353 g = klass(n, [], directed, {}, vertex_attrs) 2354 for idx, edge_data in enumerate(edges): 2355 src_name, dst_name = edge_data[efk_src], edge_data[efk_dest] 2356 v1 = vertex_name_map[src_name] 2357 if v1 == n: 2358 g.add_vertices(1) 2359 g.vs[n][vertex_name_attr] = src_name 2360 n += 1 2361 v2 = vertex_name_map[dst_name] 2362 if v2 == n: 2363 g.add_vertices(1) 2364 g.vs[n][vertex_name_attr] = dst_name 2365 n += 1 2366 g.add_edge(v1, v2) 2367 for k, v in edge_data.iteritems(): 2368 g.es[idx][k] = v 2369 2370 return g 2371 else: 2372 edge_list, edge_attrs, m = [], {}, 0 2373 for idx, edge_data in enumerate(edges): 2374 v1 = vertex_name_map[edge_data[efk_src]] 2375 v2 = vertex_name_map[edge_data[efk_dest]] 2376 2377 edge_list.append((v1, v2)) 2378 for k, v in edge_data.iteritems(): 2379 try: 2380 edge_attrs[k].append((idx, v)) 2381 except KeyError: 2382 edge_attrs[k] = [(idx, v)] 2383 m += 1 2384 for k, v in edge_attrs.iteritems(): 2385 edge_attrs[k] = create_list_from_indices(v, m) 2386 2387 # It may have happened that some vertices were added during 2388 # the process 2389 if len(vertex_name_map) > n: 2390 diff = len(vertex_name_map) - n 2391 more = [None] * diff 2392 for k, v in vertex_attrs.iteritems(): v.extend(more) 2393 vertex_attrs[vertex_name_attr] = vertex_name_map.values() 2394 n = len(vertex_name_map) 2395 2396 # Create the graph 2397 return klass(n, edge_list, directed, {}, vertex_attrs, edge_attrs) 2398 2399 ##################################################### 2400 # Constructor for tuple-like representation of graphs 2401 2402 @classmethod
2403 - def TupleList(klass, edges, directed=False, \ 2404 vertex_name_attr="name", edge_attrs=None, weights=False):
2405 """Constructs a graph from a list-of-tuples representation. 2406 2407 This representation assumes that the edges of the graph are encoded 2408 in a list of tuples (or lists). Each item in the list must have at least 2409 two elements, which specify the source and the target vertices of the edge. 2410 The remaining elements (if any) specify the edge attributes of that edge, 2411 where the names of the edge attributes originate from the C{edge_attrs} 2412 list. The names of the vertices will be stored in the vertex attribute 2413 given by C{vertex_name_attr}. 2414 2415 The default parameters of this function are suitable for creating 2416 unweighted graphs from lists where each item contains the source vertex 2417 and the target vertex. If you have a weighted graph, you can use items 2418 where the third item contains the weight of the edge by setting 2419 C{edge_attrs} to C{"weight"} or C{["weight"]}. If you have even more 2420 edge attributes, add them to the end of each item in the C{edges} 2421 list and also specify the corresponding edge attribute names in 2422 C{edge_attrs} as a list. 2423 2424 @param edges: the data source for the edges. This must be a list 2425 where each item is a tuple (or list) containing at least two 2426 items: the name of the source and the target vertex. Note that 2427 names will be assigned to the C{name} vertex attribute (or another 2428 vertex attribute if C{vertex_name_attr} is specified), even if 2429 all the vertex names in the list are in fact numbers. 2430 @param directed: whether the constructed graph will be directed 2431 @param vertex_name_attr: the name of the vertex attribute that will 2432 contain the vertex names. 2433 @param edge_attrs: the names of the edge attributes that are filled 2434 with the extra items in the edge list (starting from index 2, since 2435 the first two items are the source and target vertices). C{None} 2436 means that only the source and target vertices will be extracted 2437 from each item. If you pass a string here, it will be wrapped in 2438 a list for convenience. 2439 @param weights: alternative way to specify that the graph is 2440 weighted. If you set C{weights} to C{true} and C{edge_attrs} is 2441 not given, it will be assumed that C{edge_attrs} is C{["weight"]} 2442 and igraph will parse the third element from each item into an 2443 edge weight. If you set C{weights} to a string, it will be assumed 2444 that C{edge_attrs} contains that string only, and igraph will 2445 store the edge weights in that attribute. 2446 @return: the graph that was constructed 2447 """ 2448 if edge_attrs is None: 2449 if not weights: 2450 edge_attrs = () 2451 else: 2452 if not isinstance(weights, basestring): 2453 weights = "weight" 2454 edge_attrs = [weights] 2455 else: 2456 if weights: 2457 raise ValueError("`weights` must be False if `edge_attrs` is " 2458 "not None") 2459 2460 if isinstance(edge_attrs, basestring): 2461 edge_attrs = [edge_attrs] 2462 2463 # Set up a vertex ID generator 2464 idgen = UniqueIdGenerator() 2465 2466 # Construct the edges and the edge attributes 2467 edge_list = [] 2468 edge_attributes = {} 2469 for name in edge_attrs: 2470 edge_attributes[name] = [] 2471 2472 for item in edges: 2473 edge_list.append((idgen[item[0]], idgen[item[1]])) 2474 for index, name in enumerate(edge_attrs, 2): 2475 try: 2476 edge_attributes[name].append(item[index]) 2477 except IndexError: 2478 edge_attributes[name].append(None) 2479 2480 # Set up the "name" vertex attribute 2481 vertex_attributes = {} 2482 vertex_attributes[vertex_name_attr] = idgen.values() 2483 n = len(idgen) 2484 2485 # Construct the graph 2486 return klass(n, edge_list, directed, {}, vertex_attributes, edge_attributes) 2487 2488 ################################# 2489 # Constructor for graph formulae 2490 Formula=classmethod(construct_graph_from_formula) 2491 2492 ########################### 2493 # Vertex and edge sequence 2494 2495 @property
2496 - def vs(self):
2497 """The vertex sequence of the graph""" 2498 return VertexSeq(self) 2499 2500 @property
2501 - def es(self):
2502 """The edge sequence of the graph""" 2503 return EdgeSeq(self) 2504 2505 ############################################# 2506 # Friendlier interface for bipartite methods 2507 2508 @classmethod
2509 - def Bipartite(klass, types, *args, **kwds):
2510 """Bipartite(types, edges, directed=False) 2511 2512 Creates a bipartite graph with the given vertex types and edges. 2513 This is similar to the default constructor of the graph, the 2514 only difference is that it checks whether all the edges go 2515 between the two vertex classes and it assigns the type vector 2516 to a C{type} attribute afterwards. 2517 2518 Examples: 2519 2520 >>> g = Graph.Bipartite([0, 1, 0, 1], [(0, 1), (2, 3), (0, 3)]) 2521 >>> g.is_bipartite() 2522 True 2523 >>> g.vs["type"] 2524 [False, True, False, True] 2525 2526 @param types: the vertex types as a boolean list. Anything that 2527 evaluates to C{False} will denote a vertex of the first kind, 2528 anything that evaluates to C{True} will denote a vertex of the 2529 second kind. 2530 @param edges: the edges as a list of tuples. 2531 @param directed: whether to create a directed graph. Bipartite 2532 networks are usually undirected, so the default is C{False} 2533 2534 @return: the graph with a binary vertex attribute named C{"type"} that 2535 stores the vertex classes. 2536 """ 2537 result = klass._Bipartite(types, *args, **kwds) 2538 result.vs["type"] = [bool(x) for x in types] 2539 return result 2540 2541 @classmethod
2542 - def Full_Bipartite(klass, *args, **kwds):
2543 """Full_Bipartite(n1, n2, directed=False, mode=ALL) 2544 2545 Generates a full bipartite graph (directed or undirected, with or 2546 without loops). 2547 2548 >>> g = Graph.Full_Bipartite(2, 3) 2549 >>> g.is_bipartite() 2550 True 2551 >>> g.vs["type"] 2552 [False, False, True, True, True] 2553 2554 @param n1: the number of vertices of the first kind. 2555 @param n2: the number of vertices of the second kind. 2556 @param directed: whether tp generate a directed graph. 2557 @param mode: if C{OUT}, then all vertices of the first kind are 2558 connected to the others; C{IN} specifies the opposite direction, 2559 C{ALL} creates mutual edges. Ignored for undirected graphs. 2560 2561 @return: the graph with a binary vertex attribute named C{"type"} that 2562 stores the vertex classes. 2563 """ 2564 result, types = klass._Full_Bipartite(*args, **kwds) 2565 result.vs["type"] = types 2566 return result 2567 2568 @classmethod
2569 - def Random_Bipartite(klass, *args, **kwds):
2570 """Random_Bipartite(n1, n2, p=None, m=None, directed=False, neimode=ALL) 2571 2572 Generates a random bipartite graph with the given number of vertices and 2573 edges (if m is given), or with the given number of vertices and the given 2574 connection probability (if p is given). 2575 2576 If m is given but p is not, the generated graph will have n1 vertices of 2577 type 1, n2 vertices of type 2 and m randomly selected edges between them. If 2578 p is given but m is not, the generated graph will have n1 vertices of type 1 2579 and n2 vertices of type 2, and each edge will exist between them with 2580 probability p. 2581 2582 @param n1: the number of vertices of type 1. 2583 @param n2: the number of vertices of type 2. 2584 @param p: the probability of edges. If given, C{m} must be missing. 2585 @param m: the number of edges. If given, C{p} must be missing. 2586 @param directed: whether to generate a directed graph. 2587 @param neimode: if the graph is directed, specifies how the edges will be 2588 generated. If it is C{"all"}, edges will be generated in both directions 2589 (from type 1 to type 2 and vice versa) independently. If it is C{"out"} 2590 edges will always point from type 1 to type 2. If it is C{"in"}, edges 2591 will always point from type 2 to type 1. This argument is ignored for 2592 undirected graphs. 2593 """ 2594 result, types = klass._Random_Bipartite(*args, **kwds) 2595 result.vs["type"] = types 2596 return result 2597 2598 @classmethod
2599 - def GRG(klass, n, radius, torus=False):
2600 """GRG(n, radius, torus=False, return_coordinates=False) 2601 2602 Generates a random geometric graph. 2603 2604 The algorithm drops the vertices randomly on the 2D unit square and 2605 connects them if they are closer to each other than the given radius. 2606 The coordinates of the vertices are stored in the vertex attributes C{x} 2607 and C{y}. 2608 2609 @param n: The number of vertices in the graph 2610 @param radius: The given radius 2611 @param torus: This should be C{True} if we want to use a torus instead of a 2612 square. 2613 """ 2614 result, xs, ys = klass._GRG(n, radius, torus) 2615 result.vs["x"] = xs 2616 result.vs["y"] = ys 2617 return result 2618 2619 @classmethod
2620 - def Incidence(klass, *args, **kwds):
2621 """Incidence(matrix, directed=False, mode=ALL, multiple=False) 2622 2623 Creates a bipartite graph from an incidence matrix. 2624 2625 Example: 2626 2627 >>> g = Graph.Incidence([[0, 1, 1], [1, 1, 0]]) 2628 2629 @param matrix: the incidence matrix. 2630 @param directed: whether to create a directed graph. 2631 @param mode: defines the direction of edges in the graph. If 2632 C{OUT}, then edges go from vertices of the first kind 2633 (corresponding to rows of the matrix) to vertices of the 2634 second kind (the columns of the matrix). If C{IN}, the 2635 opposite direction is used. C{ALL} creates mutual edges. 2636 Ignored for undirected graphs. 2637 @param multiple: defines what to do with non-zero entries in the 2638 matrix. If C{False}, non-zero entries will create an edge no matter 2639 what the value is. If C{True}, non-zero entries are rounded up to 2640 the nearest integer and this will be the number of multiple edges 2641 created. 2642 2643 @return: the graph with a binary vertex attribute named C{"type"} that 2644 stores the vertex classes. 2645 """ 2646 result, types = klass._Incidence(*args, **kwds) 2647 result.vs["type"] = types 2648 return result 2649
2650 - def bipartite_projection(self, types="type", multiplicity=True, probe1=-1, 2651 which="both"):
2652 """Projects a bipartite graph into two one-mode graphs. Edge directions 2653 are ignored while projecting. 2654 2655 Examples: 2656 2657 >>> g = Graph.Full_Bipartite(10, 5) 2658 >>> g1, g2 = g.bipartite_projection() 2659 >>> g1.isomorphic(Graph.Full(10)) 2660 True 2661 >>> g2.isomorphic(Graph.Full(5)) 2662 True 2663 2664 @param types: an igraph vector containing the vertex types, or an 2665 attribute name. Anything that evalulates to C{False} corresponds to 2666 vertices of the first kind, everything else to the second kind. 2667 @param multiplicity: if C{True}, then igraph keeps the multiplicity of 2668 the edges in the projection in an edge attribute called C{"weight"}. 2669 E.g., if there is an A-C-B and an A-D-B triplet in the bipartite 2670 graph and there is no other X (apart from X=B and X=D) for which an 2671 A-X-B triplet would exist in the bipartite graph, the multiplicity 2672 of the A-B edge in the projection will be 2. 2673 @param probe1: this argument can be used to specify the order of the 2674 projections in the resulting list. If given and non-negative, then 2675 it is considered as a vertex ID; the projection containing the 2676 vertex will be the first one in the result. 2677 @param which: this argument can be used to specify which of the two 2678 projections should be returned if only one of them is needed. Passing 2679 0 here means that only the first projection is returned, while 1 means 2680 that only the second projection is returned. (Note that we use 0 and 1 2681 because Python indexing is zero-based). C{False} is equivalent to 0 and 2682 C{True} is equivalent to 1. Any other value means that both projections 2683 will be returned in a tuple. 2684 @return: a tuple containing the two projected one-mode graphs if C{which} 2685 is not 1 or 2, or the projected one-mode graph specified by the 2686 C{which} argument if its value is 0, 1, C{False} or C{True}. 2687 """ 2688 superclass_meth = super(Graph, self).bipartite_projection 2689 2690 if which == False: 2691 which = 0 2692 elif which == True: 2693 which = 1 2694 if which != 0 and which != 1: 2695 which = -1 2696 2697 if multiplicity: 2698 if which == 0: 2699 g1, w1 = superclass_meth(types, True, probe1, which) 2700 g2, w2 = None, None 2701 elif which == 1: 2702 g1, w1 = None, None 2703 g2, w2 = superclass_meth(types, True, probe1, which) 2704 else: 2705 g1, g2, w1, w2 = superclass_meth(types, True, probe1, which) 2706 2707 if g1 is not None: 2708 g1.es["weight"] = w1 2709 if g2 is not None: 2710 g2.es["weight"] = w2 2711 return g1, g2 2712 else: 2713 return g1 2714 else: 2715 g2.es["weight"] = w2 2716 return g2 2717 else: 2718 return superclass_meth(types, False, probe1, which) 2719
2720 - def bipartite_projection_size(self, types="type", *args, **kwds):
2721 """bipartite_projection(types="type") 2722 2723 Calculates the number of vertices and edges in the bipartite 2724 projections of this graph according to the specified vertex types. 2725 This is useful if you have a bipartite graph and you want to estimate 2726 the amount of memory you would need to calculate the projections 2727 themselves. 2728 2729 @param types: an igraph vector containing the vertex types, or an 2730 attribute name. Anything that evalulates to C{False} corresponds to 2731 vertices of the first kind, everything else to the second kind. 2732 @return: a 4-tuple containing the number of vertices and edges in the 2733 first projection, followed by the number of vertices and edges in the 2734 second projection. 2735 """ 2736 return super(Graph, self).bipartite_projection_size(types, \ 2737 *args, **kwds) 2738
2739 - def get_incidence(self, types="type", *args, **kwds):
2740 """get_incidence(self, types="type") 2741 2742 Returns the incidence matrix of a bipartite graph. The incidence matrix 2743 is an M{n} times M{m} matrix, where M{n} and M{m} are the number of 2744 vertices in the two vertex classes. 2745 2746 @param types: an igraph vector containing the vertex types, or an 2747 attribute name. Anything that evalulates to C{False} corresponds to 2748 vertices of the first kind, everything else to the second kind. 2749 @return: the incidence matrix and two lists in a triplet. The first 2750 list defines the mapping between row indices of the matrix and the 2751 original vertex IDs. The second list is the same for the column 2752 indices. 2753 """ 2754 return super(Graph, self).get_incidence(types, *args, **kwds) 2755 2756 ########################### 2757 # ctypes support 2758 2759 @property
2760 - def _as_parameter_(self):
2761 return self._raw_pointer() 2762 2763 ################### 2764 # Custom operators 2765
2766 - def __iadd__(self, other):
2767 """In-place addition (disjoint union). 2768 2769 @see: L{__add__} 2770 """ 2771 if isinstance(other, (int, basestring)): 2772 self.add_vertices(other) 2773 return self 2774 elif isinstance(other, tuple) and len(other) == 2: 2775 self.add_edges([other]) 2776 return self 2777 elif isinstance(other, list): 2778 if not other: 2779 return self 2780 if isinstance(other[0], tuple): 2781 self.add_edges(other) 2782 return self 2783 if isinstance(other[0], basestring): 2784 self.add_vertices(other) 2785 return self 2786 return NotImplemented 2787 2788
2789 - def __add__(self, other):
2790 """Copies the graph and extends the copy depending on the type of 2791 the other object given. 2792 2793 @param other: if it is an integer, the copy is extended by the given 2794 number of vertices. If it is a string, the copy is extended by a 2795 single vertex whose C{name} attribute will be equal to the given 2796 string. If it is a tuple with two elements, the copy 2797 is extended by a single edge. If it is a list of tuples, the copy 2798 is extended by multiple edges. If it is a L{Graph}, a disjoint 2799 union is performed. 2800 """ 2801 if isinstance(other, (int, basestring)): 2802 g = self.copy() 2803 g.add_vertices(other) 2804 elif isinstance(other, tuple) and len(other) == 2: 2805 g = self.copy() 2806 g.add_edges([other]) 2807 elif isinstance(other, list): 2808 if len(other)>0: 2809 if isinstance(other[0], tuple): 2810 g = self.copy() 2811 g.add_edges(other) 2812 elif isinstance(other[0], basestring): 2813 g = self.copy() 2814 g.add_vertices(other) 2815 elif isinstance(other[0], Graph): 2816 return self.disjoint_union(other) 2817 else: 2818 return NotImplemented 2819 else: 2820 return self.copy() 2821 2822 elif isinstance(other, Graph): 2823 return self.disjoint_union(other) 2824 else: 2825 return NotImplemented 2826 2827 return g 2828 2829
2830 - def __isub__(self, other):
2831 """In-place subtraction (difference). 2832 2833 @see: L{__sub__}""" 2834 if isinstance(other, int): 2835 self.delete_vertices([other]) 2836 elif isinstance(other, tuple) and len(other) == 2: 2837 self.delete_edges([other]) 2838 elif isinstance(other, list): 2839 if len(other)>0: 2840 if isinstance(other[0], tuple): 2841 self.delete_edges(other) 2842 elif isinstance(other[0], (int, long, basestring)): 2843 self.delete_vertices(other) 2844 else: 2845 return NotImplemented 2846 elif isinstance(other, _igraph.Vertex): 2847 self.delete_vertices(other) 2848 elif isinstance(other, _igraph.VertexSeq): 2849 self.delete_vertices(other) 2850 elif isinstance(other, _igraph.Edge): 2851 self.delete_edges(other) 2852 elif isinstance(other, _igraph.EdgeSeq): 2853 self.delete_edges(other) 2854 else: 2855 return NotImplemented 2856 return self 2857 2858
2859 - def __sub__(self, other):
2860 """Removes the given object(s) from the graph 2861 2862 @param other: if it is an integer, removes the vertex with the given 2863 ID from the graph (note that the remaining vertices will get 2864 re-indexed!). If it is a tuple, removes the given edge. If it is 2865 a graph, takes the difference of the two graphs. Accepts 2866 lists of integers or lists of tuples as well, but they can't be 2867 mixed! Also accepts L{Edge} and L{EdgeSeq} objects. 2868 """ 2869 if isinstance(other, Graph): 2870 return self.difference(other) 2871 2872 result = self.copy() 2873 if isinstance(other, (int, long, basestring)): 2874 result.delete_vertices([other]) 2875 elif isinstance(other, tuple) and len(other) == 2: 2876 result.delete_edges([other]) 2877 elif isinstance(other, list): 2878 if len(other)>0: 2879 if isinstance(other[0], tuple): 2880 result.delete_edges(other) 2881 elif isinstance(other[0], (int, long, basestring)): 2882 result.delete_vertices(other) 2883 else: 2884 return NotImplemented 2885 else: 2886 return result 2887 elif isinstance(other, _igraph.Vertex): 2888 result.delete_vertices(other) 2889 elif isinstance(other, _igraph.VertexSeq): 2890 result.delete_vertices(other) 2891 elif isinstance(other, _igraph.Edge): 2892 result.delete_edges(other) 2893 elif isinstance(other, _igraph.EdgeSeq): 2894 result.delete_edges(other) 2895 else: 2896 return NotImplemented 2897 2898 return result 2899
2900 - def __mul__(self, other):
2901 """Copies exact replicas of the original graph an arbitrary number of 2902 times. 2903 2904 @param other: if it is an integer, multiplies the graph by creating the 2905 given number of identical copies and taking the disjoint union of 2906 them. 2907 """ 2908 if isinstance(other, int): 2909 if other == 0: 2910 return Graph() 2911 elif other == 1: 2912 return self 2913 elif other > 1: 2914 return self.disjoint_union([self]*(other-1)) 2915 else: 2916 return NotImplemented 2917 2918 return NotImplemented 2919
2920 - def __nonzero__(self):
2921 """Returns True if the graph has at least one vertex, False otherwise. 2922 """ 2923 return self.vcount() > 0 2924
2925 - def __coerce__(self, other):
2926 """Coercion rules. 2927 2928 This method is needed to allow the graph to react to additions 2929 with lists, tuples, integers, strings, vertices, edges and so on. 2930 """ 2931 if isinstance(other, (int, tuple, list, basestring)): 2932 return self, other 2933 if isinstance(other, _igraph.Vertex): 2934 return self, other 2935 if isinstance(other, _igraph.VertexSeq): 2936 return self, other 2937 if isinstance(other, _igraph.Edge): 2938 return self, other 2939 if isinstance(other, _igraph.EdgeSeq): 2940 return self, other 2941 return NotImplemented 2942 2943 @classmethod
2944 - def _reconstruct(cls, attrs, *args, **kwds):
2945 """Reconstructs a Graph object from Python's pickled format. 2946 2947 This method is for internal use only, it should not be called 2948 directly.""" 2949 result = cls(*args, **kwds) 2950 result.__dict__.update(attrs) 2951 return result 2952
2953 - def __reduce__(self):
2954 """Support for pickling.""" 2955 constructor = self.__class__ 2956 gattrs, vattrs, eattrs = {}, {}, {} 2957 for attr in self.attributes(): 2958 gattrs[attr] = self[attr] 2959 for attr in self.vs.attribute_names(): 2960 vattrs[attr] = self.vs[attr] 2961 for attr in self.es.attribute_names(): 2962 eattrs[attr] = self.es[attr] 2963 parameters = (self.vcount(), self.get_edgelist(), \ 2964 self.is_directed(), gattrs, vattrs, eattrs) 2965 return (constructor, parameters, self.__dict__) 2966 2967
2968 - def __plot__(self, context, bbox, palette, *args, **kwds):
2969 """Plots the graph to the given Cairo context in the given bounding box 2970 2971 The visual style of vertices and edges can be modified at three 2972 places in the following order of precedence (lower indices override 2973 higher indices): 2974 2975 1. Keyword arguments of this function (or of L{plot()} which is 2976 passed intact to C{Graph.__plot__()}. 2977 2978 2. Vertex or edge attributes, specified later in the list of 2979 keyword arguments. 2980 2981 3. igraph-wide plotting defaults (see 2982 L{igraph.config.Configuration}) 2983 2984 4. Built-in defaults. 2985 2986 E.g., if the C{vertex_size} keyword attribute is not present, 2987 but there exists a vertex attribute named C{size}, the sizes of 2988 the vertices will be specified by that attribute. 2989 2990 Besides the usual self-explanatory plotting parameters (C{context}, 2991 C{bbox}, C{palette}), it accepts the following keyword arguments: 2992 2993 - C{autocurve}: whether to use curves instead of straight lines for 2994 multiple edges on the graph plot. This argument may be C{True} 2995 or C{False}; when omitted, C{True} is assumed for graphs with 2996 less than 10.000 edges and C{False} otherwise. 2997 2998 - C{drawer_factory}: a subclass of L{AbstractCairoGraphDrawer} 2999 which will be used to draw the graph. You may also provide 3000 a function here which takes two arguments: the Cairo context 3001 to draw on and a bounding box (an instance of L{BoundingBox}). 3002 If this keyword argument is missing, igraph will use the 3003 default graph drawer which should be suitable for most purposes. 3004 It is safe to omit this keyword argument unless you need to use 3005 a specific graph drawer. 3006 3007 - C{keep_aspect_ratio}: whether to keep the aspect ratio of the layout 3008 that igraph calculates to place the nodes. C{True} means that the 3009 layout will be scaled proportionally to fit into the bounding box 3010 where the graph is to be drawn but the aspect ratio will be kept 3011 the same (potentially leaving empty space next to, below or above 3012 the graph). C{False} means that the layout will be scaled independently 3013 along the X and Y axis in order to fill the entire bounding box. 3014 The default is C{False}. 3015 3016 - C{layout}: the layout to be used. If not an instance of 3017 L{Layout}, it will be passed to L{Graph.layout} to calculate 3018 the layout. Note that if you want a deterministic layout that 3019 does not change with every plot, you must either use a 3020 deterministic layout function (like L{Graph.layout_circle}) or 3021 calculate the layout in advance and pass a L{Layout} object here. 3022 3023 - C{margin}: the top, right, bottom, left margins as a 4-tuple. 3024 If it has less than 4 elements or is a single float, the elements 3025 will be re-used until the length is at least 4. 3026 3027 - C{mark_groups}: whether to highlight some of the vertex groups by 3028 colored polygons. This argument can be one of the following: 3029 3030 - C{False}: no groups will be highlighted 3031 3032 - A dict mapping tuples of vertex indices to color names. 3033 The given vertex groups will be highlighted by the given 3034 colors. 3035 3036 - A list containing pairs or an iterable yielding pairs, where 3037 the first element of each pair is a list of vertex indices and 3038 the second element is a color. 3039 3040 In place of lists of vertex indices, you may also use L{VertexSeq} 3041 instances. 3042 3043 In place of color names, you may also use color indices into the 3044 current palette. C{None} as a color name will mean that the 3045 corresponding group is ignored. 3046 3047 - C{vertex_size}: size of the vertices. The corresponding vertex 3048 attribute is called C{size}. The default is 10. Vertex sizes 3049 are measured in the unit of the Cairo context on which igraph 3050 is drawing. 3051 3052 - C{vertex_color}: color of the vertices. The corresponding vertex 3053 attribute is C{color}, the default is red. Colors can be 3054 specified either by common X11 color names (see the source 3055 code of L{igraph.drawing.colors} for a list of known colors), by 3056 3-tuples of floats (ranging between 0 and 255 for the R, G and 3057 B components), by CSS-style string specifications (C{#rrggbb}) 3058 or by integer color indices of the specified palette. 3059 3060 - C{vertex_frame_color}: color of the frame (i.e. stroke) of the 3061 vertices. The corresponding vertex attribute is C{frame_color}, 3062 the default is black. See C{vertex_color} for the possible ways 3063 of specifying a color. 3064 3065 - C{vertex_frame_width}: the width of the frame (i.e. stroke) of the 3066 vertices. The corresponding vertex attribute is C{frame_width}. 3067 The default is 1. Vertex frame widths are measured in the unit of the 3068 Cairo context on which igraph is drawing. 3069 3070 - C{vertex_shape}: shape of the vertices. Alternatively it can 3071 be specified by the C{shape} vertex attribute. Possibilities 3072 are: C{square}, {circle}, {triangle}, {triangle-down} or 3073 C{hidden}. See the source code of L{igraph.drawing} for a 3074 list of alternative shape names that are also accepted and 3075 mapped to these. 3076 3077 - C{vertex_label}: labels drawn next to the vertices. 3078 The corresponding vertex attribute is C{label}. 3079 3080 - C{vertex_label_dist}: distance of the midpoint of the vertex 3081 label from the center of the corresponding vertex. 3082 The corresponding vertex attribute is C{label_dist}. 3083 3084 - C{vertex_label_color}: color of the label. Corresponding 3085 vertex attribute: C{label_color}. See C{vertex_color} for 3086 color specification syntax. 3087 3088 - C{vertex_label_size}: font size of the label, specified 3089 in the unit of the Cairo context on which we are drawing. 3090 Corresponding vertex attribute: C{label_size}. 3091 3092 - C{vertex_label_angle}: the direction of the line connecting 3093 the midpoint of the vertex with the midpoint of the label. 3094 This can be used to position the labels relative to the 3095 vertices themselves in conjunction with C{vertex_label_dist}. 3096 Corresponding vertex attribute: C{label_angle}. The 3097 default is C{-math.pi/2}. 3098 3099 - C{vertex_order}: drawing order of the vertices. This must be 3100 a list or tuple containing vertex indices; vertices are then 3101 drawn according to this order. 3102 3103 - C{vertex_order_by}: an alternative way to specify the drawing 3104 order of the vertices; this attribute is interpreted as the name 3105 of a vertex attribute, and vertices are drawn such that those 3106 with a smaller attribute value are drawn first. You may also 3107 reverse the order by passing a tuple here; the first element of 3108 the tuple should be the name of the attribute, the second element 3109 specifies whether the order is reversed (C{True}, C{False}, 3110 C{"asc"} and C{"desc"} are accepted values). 3111 3112 - C{edge_color}: color of the edges. The corresponding edge 3113 attribute is C{color}, the default is red. See C{vertex_color} 3114 for color specification syntax. 3115 3116 - C{edge_curved}: whether the edges should be curved. Positive 3117 numbers correspond to edges curved in a counter-clockwise 3118 direction, negative numbers correspond to edges curved in a 3119 clockwise direction. Zero represents straight edges. C{True} 3120 is interpreted as 0.5, C{False} is interpreted as 0. The 3121 default is 0 which makes all the edges straight. 3122 3123 - C{edge_width}: width of the edges in the default unit of the 3124 Cairo context on which we are drawing. The corresponding 3125 edge attribute is C{width}, the default is 1. 3126 3127 - C{edge_arrow_size}: arrow size of the edges. The 3128 corresponding edge attribute is C{arrow_size}, the default 3129 is 1. 3130 3131 - C{edge_arrow_width}: width of the arrowhead on the edge. The 3132 corresponding edge attribute is C{arrow_width}, the default 3133 is 1. 3134 3135 - C{edge_order}: drawing order of the edges. This must be 3136 a list or tuple containing edge indices; edges are then 3137 drawn according to this order. 3138 3139 - C{edge_order_by}: an alternative way to specify the drawing 3140 order of the edges; this attribute is interpreted as the name 3141 of an edge attribute, and edges are drawn such that those 3142 with a smaller attribute value are drawn first. You may also 3143 reverse the order by passing a tuple here; the first element of 3144 the tuple should be the name of the attribute, the second element 3145 specifies whether the order is reversed (C{True}, C{False}, 3146 C{"asc"} and C{"desc"} are accepted values). 3147 """ 3148 drawer_factory = kwds.get("drawer_factory", DefaultGraphDrawer) 3149 if "drawer_factory" in kwds: 3150 del kwds["drawer_factory"] 3151 drawer = drawer_factory(context, bbox) 3152 drawer.draw(self, palette, *args, **kwds) 3153
3154 - def __str__(self):
3155 """Returns a string representation of the graph. 3156 3157 Behind the scenes, this method constructs a L{GraphSummary} 3158 instance and invokes its C{__str__} method with a verbosity of 1 3159 and attribute printing turned off. 3160 3161 See the documentation of L{GraphSummary} for more details about the 3162 output. 3163 """ 3164 params = dict( 3165 verbosity=1, 3166 width=78, 3167 print_graph_attributes=False, 3168 print_vertex_attributes=False, 3169 print_edge_attributes=False 3170 ) 3171 return self.summary(**params) 3172
3173 - def summary(self, verbosity=0, width=None, *args, **kwds):
3174 """Returns the summary of the graph. 3175 3176 The output of this method is similar to the output of the 3177 C{__str__} method. If I{verbosity} is zero, only the header line 3178 is returned (see C{__str__} for more details), otherwise the 3179 header line and the edge list is printed. 3180 3181 Behind the scenes, this method constructs a L{GraphSummary} 3182 object and invokes its C{__str__} method. 3183 3184 @param verbosity: if zero, only the header line is returned 3185 (see C{__str__} for more details), otherwise the header line 3186 and the full edge list is printed. 3187 @param width: the number of characters to use in one line. 3188 If C{None}, no limit will be enforced on the line lengths. 3189 @return: the summary of the graph. 3190 """ 3191 return str(GraphSummary(self, verbosity, width, *args, **kwds)) 3192 3193 _format_mapping = { 3194 "ncol": ("Read_Ncol", "write_ncol"), 3195 "lgl": ("Read_Lgl", "write_lgl"), 3196 "graphdb": ("Read_GraphDB", None), 3197 "graphmlz": ("Read_GraphMLz", "write_graphmlz"), 3198 "graphml": ("Read_GraphML", "write_graphml"), 3199 "gml": ("Read_GML", "write_gml"), 3200 "dot": (None, "write_dot"), 3201 "graphviz": (None, "write_dot"), 3202 "net": ("Read_Pajek", "write_pajek"), 3203 "pajek": ("Read_Pajek", "write_pajek"), 3204 "dimacs": ("Read_DIMACS", "write_dimacs"), 3205 "adjacency": ("Read_Adjacency", "write_adjacency"), 3206 "adj": ("Read_Adjacency", "write_adjacency"), 3207 "edgelist": ("Read_Edgelist", "write_edgelist"), 3208 "edge": ("Read_Edgelist", "write_edgelist"), 3209 "edges": ("Read_Edgelist", "write_edgelist"), 3210 "pickle": ("Read_Pickle", "write_pickle"), 3211 "picklez": ("Read_Picklez", "write_picklez"), 3212 "svg": (None, "write_svg"), 3213 "gw": (None, "write_leda"), 3214 "leda": (None, "write_leda"), 3215 "lgr": (None, "write_leda"), 3216 "dl": ("Read_DL", None) 3217 } 3218 3219 _layout_mapping = { 3220 "auto": "layout_auto", 3221 "automatic": "layout_auto", 3222 "bipartite": "layout_bipartite", 3223 "circle": "layout_circle", 3224 "circular": "layout_circle", 3225 "drl": "layout_drl", 3226 "fr": "layout_fruchterman_reingold", 3227 "fruchterman_reingold": "layout_fruchterman_reingold", 3228 "gfr": "layout_grid_fruchterman_reingold", 3229 "graphopt": "layout_graphopt", 3230 "grid": "layout_grid", 3231 "grid_fr": "layout_grid_fruchterman_reingold", 3232 "grid_fruchterman_reingold": "layout_grid_fruchterman_reingold", 3233 "kk": "layout_kamada_kawai", 3234 "kamada_kawai": "layout_kamada_kawai", 3235 "lgl": "layout_lgl", 3236 "large": "layout_lgl", 3237 "large_graph": "layout_lgl", 3238 "mds": "layout_mds", 3239 "random": "layout_random", 3240 "rt": "layout_reingold_tilford", 3241 "tree": "layout_reingold_tilford", 3242 "reingold_tilford": "layout_reingold_tilford", 3243 "rt_circular": "layout_reingold_tilford_circular", 3244 "reingold_tilford_circular": "layout_reingold_tilford_circular", 3245 "sphere": "layout_sphere", 3246 "spherical": "layout_sphere", 3247 "star": "layout_star", 3248 "sugiyama": "layout_sugiyama", 3249 } 3250
3251 # After adjusting something here, don't forget to update the docstring 3252 # of Graph.layout if necessary! 3253 3254 ############################################################## 3255 3256 -class VertexSeq(_igraph.VertexSeq):
3257 """Class representing a sequence of vertices in the graph. 3258 3259 This class is most easily accessed by the C{vs} field of the 3260 L{Graph} object, which returns an ordered sequence of all vertices in 3261 the graph. The vertex sequence can be refined by invoking the 3262 L{VertexSeq.select()} method. L{VertexSeq.select()} can also be 3263 accessed by simply calling the L{VertexSeq} object. 3264 3265 An alternative way to create a vertex sequence referring to a given 3266 graph is to use the constructor directly: 3267 3268 >>> g = Graph.Full(3) 3269 >>> vs = VertexSeq(g) 3270 >>> restricted_vs = VertexSeq(g, [0, 1]) 3271 3272 The individual vertices can be accessed by indexing the vertex sequence 3273 object. It can be used as an iterable as well, or even in a list 3274 comprehension: 3275 3276 >>> g=Graph.Full(3) 3277 >>> for v in g.vs: 3278 ... v["value"] = v.index ** 2 3279 ... 3280 >>> [v["value"] ** 0.5 for v in g.vs] 3281 [0.0, 1.0, 2.0] 3282 3283 The vertex set can also be used as a dictionary where the keys are the 3284 attribute names. The values corresponding to the keys are the values 3285 of the given attribute for every vertex selected by the sequence. 3286 3287 >>> g=Graph.Full(3) 3288 >>> for idx, v in enumerate(g.vs): 3289 ... v["weight"] = idx*(idx+1) 3290 ... 3291 >>> g.vs["weight"] 3292 [0, 2, 6] 3293 >>> g.vs.select(1,2)["weight"] = [10, 20] 3294 >>> g.vs["weight"] 3295 [0, 10, 20] 3296 3297 If you specify a sequence that is shorter than the number of vertices in 3298 the VertexSeq, the sequence is reused: 3299 3300 >>> g = Graph.Tree(7, 2) 3301 >>> g.vs["color"] = ["red", "green"] 3302 >>> g.vs["color"] 3303 ['red', 'green', 'red', 'green', 'red', 'green', 'red'] 3304 3305 You can even pass a single string or integer, it will be considered as a 3306 sequence of length 1: 3307 3308 >>> g.vs["color"] = "red" 3309 >>> g.vs["color"] 3310 ['red', 'red', 'red', 'red', 'red', 'red', 'red'] 3311 3312 Some methods of the vertex sequences are simply proxy methods to the 3313 corresponding methods in the L{Graph} object. One such example is 3314 L{VertexSeq.degree()}: 3315 3316 >>> g=Graph.Tree(7, 2) 3317 >>> g.vs.degree() 3318 [2, 3, 3, 1, 1, 1, 1] 3319 >>> g.vs.degree() == g.degree() 3320 True 3321 """ 3322
3323 - def attributes(self):
3324 """Returns the list of all the vertex attributes in the graph 3325 associated to this vertex sequence.""" 3326 return self.graph.vertex_attributes() 3327
3328 - def find(self, *args, **kwds):
3329 """Returns the first vertex of the vertex sequence that matches some 3330 criteria. 3331 3332 The selection criteria are equal to the ones allowed by L{VertexSeq.select}. 3333 See L{VertexSeq.select} for more details. 3334 3335 For instance, to find the first vertex with name C{foo} in graph C{g}: 3336 3337 >>> g.vs.find(name="foo") #doctest:+SKIP 3338 3339 To find an arbitrary isolated vertex: 3340 3341 >>> g.vs.find(_degree=0) #doctest:+SKIP 3342 """ 3343 # Shortcut: if "name" is in kwds, we try that first because that 3344 # attribute is indexed 3345 if "name" in kwds: 3346 name = kwds.pop("name") 3347 elif "name_eq" in kwds: 3348 name = kwds.pop("name_eq") 3349 else: 3350 name = None 3351 3352 if name is not None: 3353 if args: 3354 args.insert(0, name) 3355 else: 3356 args = [name] 3357 3358 if args: 3359 # Selecting first based on positional arguments, then checking 3360 # the criteria specified by the (remaining) keyword arguments 3361 vertex = _igraph.VertexSeq.find(self, *args) 3362 if not kwds: 3363 return vertex 3364 vs = self.graph.vs[vertex.index] 3365 else: 3366 vs = self 3367 3368 # Selecting based on keyword arguments 3369 vs = vs.select(**kwds) 3370 if vs: 3371 return vs[0] 3372 raise ValueError("no such vertex") 3373
3374 - def select(self, *args, **kwds):
3375 """Selects a subset of the vertex sequence based on some criteria 3376 3377 The selection criteria can be specified by the positional and the keyword 3378 arguments. Positional arguments are always processed before keyword 3379 arguments. 3380 3381 - If the first positional argument is C{None}, an empty sequence is 3382 returned. 3383 3384 - If the first positional argument is a callable object, the object 3385 will be called for every vertex in the sequence. If it returns 3386 C{True}, the vertex will be included, otherwise it will 3387 be excluded. 3388 3389 - If the first positional argument is an iterable, it must return 3390 integers and they will be considered as indices of the current 3391 vertex set (NOT the whole vertex set of the graph -- the 3392 difference matters when one filters a vertex set that has 3393 already been filtered by a previous invocation of 3394 L{VertexSeq.select()}. In this case, the indices do not refer 3395 directly to the vertices of the graph but to the elements of 3396 the filtered vertex sequence. 3397 3398 - If the first positional argument is an integer, all remaining 3399 arguments are expected to be integers. They are considered as 3400 indices of the current vertex set again. 3401 3402 Keyword arguments can be used to filter the vertices based on their 3403 attributes. The name of the keyword specifies the name of the attribute 3404 and the filtering operator, they should be concatenated by an 3405 underscore (C{_}) character. Attribute names can also contain 3406 underscores, but operator names don't, so the operator is always the 3407 largest trailing substring of the keyword name that does not contain 3408 an underscore. Possible operators are: 3409 3410 - C{eq}: equal to 3411 3412 - C{ne}: not equal to 3413 3414 - C{lt}: less than 3415 3416 - C{gt}: greater than 3417 3418 - C{le}: less than or equal to 3419 3420 - C{ge}: greater than or equal to 3421 3422 - C{in}: checks if the value of an attribute is in a given list 3423 3424 - C{notin}: checks if the value of an attribute is not in a given 3425 list 3426 3427 For instance, if you want to filter vertices with a numeric C{age} 3428 property larger than 200, you have to write: 3429 3430 >>> g.vs.select(age_gt=200) #doctest: +SKIP 3431 3432 Similarly, to filter vertices whose C{type} is in a list of predefined 3433 types: 3434 3435 >>> list_of_types = ["HR", "Finance", "Management"] 3436 >>> g.vs.select(type_in=list_of_types) #doctest: +SKIP 3437 3438 If the operator is omitted, it defaults to C{eq}. For instance, the 3439 following selector selects vertices whose C{cluster} property equals 3440 to 2: 3441 3442 >>> g.vs.select(cluster=2) #doctest: +SKIP 3443 3444 In the case of an unknown operator, it is assumed that the 3445 recognized operator is part of the attribute name and the actual 3446 operator is C{eq}. 3447 3448 Attribute names inferred from keyword arguments are treated specially 3449 if they start with an underscore (C{_}). These are not real attributes 3450 but refer to specific properties of the vertices, e.g., its degree. 3451 The rule is as follows: if an attribute name starts with an underscore, 3452 the rest of the name is interpreted as a method of the L{Graph} object. 3453 This method is called with the vertex sequence as its first argument 3454 (all others left at default values) and vertices are filtered 3455 according to the value returned by the method. For instance, if you 3456 want to exclude isolated vertices: 3457 3458 >>> g = Graph.Famous("zachary") 3459 >>> non_isolated = g.vs.select(_degree_gt=0) 3460 3461 For properties that take a long time to be computed (e.g., betweenness 3462 centrality for large graphs), it is advised to calculate the values 3463 in advance and store it in a graph attribute. The same applies when 3464 you are selecting based on the same property more than once in the 3465 same C{select()} call to avoid calculating it twice unnecessarily. 3466 For instance, the following would calculate betweenness centralities 3467 twice: 3468 3469 >>> edges = g.vs.select(_betweenness_gt=10, _betweenness_lt=30) 3470 3471 It is advised to use this instead: 3472 3473 >>> g.vs["bs"] = g.betweenness() 3474 >>> edges = g.vs.select(bs_gt=10, bs_lt=30) 3475 3476 @return: the new, filtered vertex sequence""" 3477 vs = _igraph.VertexSeq.select(self, *args) 3478 3479 operators = { 3480 "lt": operator.lt, \ 3481 "gt": operator.gt, \ 3482 "le": operator.le, \ 3483 "ge": operator.ge, \ 3484 "eq": operator.eq, \ 3485 "ne": operator.ne, \ 3486 "in": lambda a, b: a in b, \ 3487 "notin": lambda a, b: a not in b } 3488 for keyword, value in kwds.iteritems(): 3489 if "_" not in keyword or keyword.rindex("_") == 0: 3490 keyword = keyword+"_eq" 3491 attr, _, op = keyword.rpartition("_") 3492 try: 3493 func = operators[op] 3494 except KeyError: 3495 # No such operator, assume that it's part of the attribute name 3496 attr, func = keyword, operators["eq"] 3497 3498 if attr[0] == '_': 3499 # Method call, not an attribute 3500 values = getattr(vs.graph, attr[1:])(vs) 3501 else: 3502 values = vs[attr] 3503 filtered_idxs=[i for i, v in enumerate(values) if func(v, value)] 3504 vs = vs.select(filtered_idxs) 3505 3506 return vs 3507
3508 - def __call__(self, *args, **kwds):
3509 """Shorthand notation to select() 3510 3511 This method simply passes all its arguments to L{VertexSeq.select()}. 3512 """ 3513 return self.select(*args, **kwds)
3514
3515 ############################################################## 3516 3517 -class EdgeSeq(_igraph.EdgeSeq):
3518 """Class representing a sequence of edges in the graph. 3519 3520 This class is most easily accessed by the C{es} field of the 3521 L{Graph} object, which returns an ordered sequence of all edges in 3522 the graph. The edge sequence can be refined by invoking the 3523 L{EdgeSeq.select()} method. L{EdgeSeq.select()} can also be 3524 accessed by simply calling the L{EdgeSeq} object. 3525 3526 An alternative way to create an edge sequence referring to a given 3527 graph is to use the constructor directly: 3528 3529 >>> g = Graph.Full(3) 3530 >>> es = EdgeSeq(g) 3531 >>> restricted_es = EdgeSeq(g, [0, 1]) 3532 3533 The individual edges can be accessed by indexing the edge sequence 3534 object. It can be used as an iterable as well, or even in a list 3535 comprehension: 3536 3537 >>> g=Graph.Full(3) 3538 >>> for e in g.es: 3539 ... print e.tuple 3540 ... 3541 (0, 1) 3542 (0, 2) 3543 (1, 2) 3544 >>> [max(e.tuple) for e in g.es] 3545 [1, 2, 2] 3546 3547 The edge sequence can also be used as a dictionary where the keys are the 3548 attribute names. The values corresponding to the keys are the values 3549 of the given attribute of every edge in the graph: 3550 3551 >>> g=Graph.Full(3) 3552 >>> for idx, e in enumerate(g.es): 3553 ... e["weight"] = idx*(idx+1) 3554 ... 3555 >>> g.es["weight"] 3556 [0, 2, 6] 3557 >>> g.es["weight"] = range(3) 3558 >>> g.es["weight"] 3559 [0, 1, 2] 3560 3561 If you specify a sequence that is shorter than the number of edges in 3562 the EdgeSeq, the sequence is reused: 3563 3564 >>> g = Graph.Tree(7, 2) 3565 >>> g.es["color"] = ["red", "green"] 3566 >>> g.es["color"] 3567 ['red', 'green', 'red', 'green', 'red', 'green'] 3568 3569 You can even pass a single string or integer, it will be considered as a 3570 sequence of length 1: 3571 3572 >>> g.es["color"] = "red" 3573 >>> g.es["color"] 3574 ['red', 'red', 'red', 'red', 'red', 'red'] 3575 3576 Some methods of the edge sequences are simply proxy methods to the 3577 corresponding methods in the L{Graph} object. One such example is 3578 L{EdgeSeq.is_multiple()}: 3579 3580 >>> g=Graph(3, [(0,1), (1,0), (1,2)]) 3581 >>> g.es.is_multiple() 3582 [False, True, False] 3583 >>> g.es.is_multiple() == g.is_multiple() 3584 True 3585 """ 3586
3587 - def attributes(self):
3588 """Returns the list of all the edge attributes in the graph 3589 associated to this edge sequence.""" 3590 return self.graph.edge_attributes() 3591
3592 - def find(self, *args, **kwds):
3593 """Returns the first edge of the edge sequence that matches some 3594 criteria. 3595 3596 The selection criteria are equal to the ones allowed by L{VertexSeq.select}. 3597 See L{VertexSeq.select} for more details. 3598 3599 For instance, to find the first edge with weight larger than 5 in graph C{g}: 3600 3601 >>> g.es.find(weight_gt=5) #doctest:+SKIP 3602 """ 3603 if args: 3604 # Selecting first based on positional arguments, then checking 3605 # the criteria specified by the keyword arguments 3606 edge = _igraph.EdgeSeq.find(self, *args) 3607 if not kwds: 3608 return edge 3609 es = self.graph.es[edge.index] 3610 else: 3611 es = self 3612 3613 # Selecting based on positional arguments 3614 es = es.select(**kwds) 3615 if es: 3616 return es[0] 3617 raise ValueError("no such edge") 3618
3619 - def select(self, *args, **kwds):
3620 """Selects a subset of the edge sequence based on some criteria 3621 3622 The selection criteria can be specified by the positional and the 3623 keyword arguments. Positional arguments are always processed before 3624 keyword arguments. 3625 3626 - If the first positional argument is C{None}, an empty sequence is 3627 returned. 3628 3629 - If the first positional argument is a callable object, the object 3630 will be called for every edge in the sequence. If it returns 3631 C{True}, the edge will be included, otherwise it will 3632 be excluded. 3633 3634 - If the first positional argument is an iterable, it must return 3635 integers and they will be considered as indices of the current 3636 edge set (NOT the whole edge set of the graph -- the 3637 difference matters when one filters an edge set that has 3638 already been filtered by a previous invocation of 3639 L{EdgeSeq.select()}. In this case, the indices do not refer 3640 directly to the edges of the graph but to the elements of 3641 the filtered edge sequence. 3642 3643 - If the first positional argument is an integer, all remaining 3644 arguments are expected to be integers. They are considered as 3645 indices of the current edge set again. 3646 3647 Keyword arguments can be used to filter the edges based on their 3648 attributes and properties. The name of the keyword specifies the name 3649 of the attribute and the filtering operator, they should be 3650 concatenated by an underscore (C{_}) character. Attribute names can 3651 also contain underscores, but operator names don't, so the operator is 3652 always the largest trailing substring of the keyword name that does not 3653 contain an underscore. Possible operators are: 3654 3655 - C{eq}: equal to 3656 3657 - C{ne}: not equal to 3658 3659 - C{lt}: less than 3660 3661 - C{gt}: greater than 3662 3663 - C{le}: less than or equal to 3664 3665 - C{ge}: greater than or equal to 3666 3667 - C{in}: checks if the value of an attribute is in a given list 3668 3669 - C{notin}: checks if the value of an attribute is not in a given 3670 list 3671 3672 For instance, if you want to filter edges with a numeric C{weight} 3673 property larger than 50, you have to write: 3674 3675 >>> g.es.select(weight_gt=50) #doctest: +SKIP 3676 3677 Similarly, to filter edges whose C{type} is in a list of predefined 3678 types: 3679 3680 >>> list_of_types = ["inhibitory", "excitatory"] 3681 >>> g.es.select(type_in=list_of_types) #doctest: +SKIP 3682 3683 If the operator is omitted, it defaults to C{eq}. For instance, the 3684 following selector selects edges whose C{type} property is 3685 C{intracluster}: 3686 3687 >>> g.es.select(type="intracluster") #doctest: +SKIP 3688 3689 In the case of an unknown operator, it is assumed that the 3690 recognized operator is part of the attribute name and the actual 3691 operator is C{eq}. 3692 3693 Keyword arguments are treated specially if they start with an 3694 underscore (C{_}). These are not real attributes but refer to specific 3695 properties of the edges, e.g., their centrality. The rules are as 3696 follows: 3697 3698 1. C{_source} or {_from} means the source vertex of an edge. 3699 3700 2. C{_target} or {_to} means the target vertex of an edge. 3701 3702 3. C{_within} ignores the operator and checks whether both endpoints 3703 of the edge lie within a specified set. 3704 3705 4. C{_between} ignores the operator and checks whether I{one} 3706 endpoint of the edge lies within a specified set and the I{other} 3707 endpoint lies within another specified set. The two sets must be 3708 given as a tuple. 3709 3710 5. Otherwise, the rest of the name is interpreted as a method of the 3711 L{Graph} object. This method is called with the edge sequence as 3712 its first argument (all others left at default values) and edges 3713 are filtered according to the value returned by the method. 3714 3715 For instance, if you want to exclude edges with a betweenness 3716 centrality less than 2: 3717 3718 >>> g = Graph.Famous("zachary") 3719 >>> excl = g.es.select(_edge_betweenness_ge = 2) 3720 3721 To select edges originating from vertices 2 and 4: 3722 3723 >>> edges = g.es.select(_source_in = [2, 4]) 3724 3725 To select edges lying entirely within the subgraph spanned by vertices 3726 2, 3, 4 and 7: 3727 3728 >>> edges = g.es.select(_within = [2, 3, 4, 7]) 3729 3730 To select edges with one endpoint in the vertex set containing vertices 3731 2, 3, 4 and 7 and the other endpoint in the vertex set containing 3732 vertices 8 and 9: 3733 3734 >>> edges = g.es.select(_between = ([2, 3, 4, 7], [8, 9])) 3735 3736 For properties that take a long time to be computed (e.g., betweenness 3737 centrality for large graphs), it is advised to calculate the values 3738 in advance and store it in a graph attribute. The same applies when 3739 you are selecting based on the same property more than once in the 3740 same C{select()} call to avoid calculating it twice unnecessarily. 3741 For instance, the following would calculate betweenness centralities 3742 twice: 3743 3744 >>> edges = g.es.select(_edge_betweenness_gt=10, # doctest:+SKIP 3745 ... _edge_betweenness_lt=30) 3746 3747 It is advised to use this instead: 3748 3749 >>> g.es["bs"] = g.edge_betweenness() 3750 >>> edges = g.es.select(bs_gt=10, bs_lt=30) 3751 3752 @return: the new, filtered edge sequence""" 3753 es = _igraph.EdgeSeq.select(self, *args) 3754 3755 def _ensure_set(value): 3756 if isinstance(value, VertexSeq): 3757 value = set(v.index for v in value) 3758 elif not isinstance(value, (set, frozenset)): 3759 value = set(value) 3760 return value 3761 3762 operators = { 3763 "lt": operator.lt, \ 3764 "gt": operator.gt, \ 3765 "le": operator.le, \ 3766 "ge": operator.ge, \ 3767 "eq": operator.eq, \ 3768 "ne": operator.ne, \ 3769 "in": lambda a, b: a in b, \ 3770 "notin": lambda a, b: a not in b } 3771 for keyword, value in kwds.iteritems(): 3772 if "_" not in keyword or keyword.rindex("_") == 0: 3773 keyword = keyword+"_eq" 3774 pos = keyword.rindex("_") 3775 attr, op = keyword[0:pos], keyword[pos+1:] 3776 try: 3777 func = operators[op] 3778 except KeyError: 3779 # No such operator, assume that it's part of the attribute name 3780 attr = "%s_%s" % (attr,op) 3781 func = operators["eq"] 3782 3783 if attr[0] == '_': 3784 if attr == "_source" or attr == "_from": 3785 values = [e.source for e in es] 3786 if op == "in" or op == "notin": 3787 value = _ensure_set(value) 3788 elif attr == "_target" or attr == "_to": 3789 values = [e.target for e in es] 3790 if op == "in" or op == "notin": 3791 value = _ensure_set(value) 3792 elif attr == "_within": 3793 func = None # ignoring function, filtering here 3794 value = _ensure_set(value) 3795 3796 # Fetch all the edges that are incident on at least one of 3797 # the vertices specified 3798 candidates = set() 3799 for v in value: 3800 candidates.update(es.graph.incident(v)) 3801 3802 if not es.is_all(): 3803 # Find those where both endpoints are OK 3804 filtered_idxs = [i for i, e in enumerate(es) if e.index in candidates 3805 and e.source in value and e.target in value] 3806 else: 3807 # Optimized version when the edge sequence contains all the edges 3808 # exactly once in increasing order of edge IDs 3809 filtered_idxs = [i for i in candidates 3810 if es[i].source in value and es[i].target in value] 3811 elif attr == "_between": 3812 if len(value) != 2: 3813 raise ValueError("_between selector requires two vertex ID lists") 3814 func = None # ignoring function, filtering here 3815 set1 = _ensure_set(value[0]) 3816 set2 = _ensure_set(value[1]) 3817 3818 # Fetch all the edges that are incident on at least one of 3819 # the vertices specified 3820 candidates = set() 3821 for v in set1: 3822 candidates.update(es.graph.incident(v)) 3823 for v in set2: 3824 candidates.update(es.graph.incident(v)) 3825 3826 if not es.is_all(): 3827 # Find those where both endpoints are OK 3828 filtered_idxs = [i for i, e in enumerate(es) 3829 if (e.source in set1 and e.target in set2) or 3830 (e.target in set1 and e.source in set2)] 3831 else: 3832 # Optimized version when the edge sequence contains all the edges 3833 # exactly once in increasing order of edge IDs 3834 filtered_idxs = [i for i in candidates 3835 if (es[i].source in set1 and es[i].target in set2) or 3836 (es[i].target in set1 and es[i].source in set2)] 3837 else: 3838 # Method call, not an attribute 3839 values = getattr(es.graph, attr[1:])(es) 3840 else: 3841 values = es[attr] 3842 3843 # If we have a function to apply on the values, do that; otherwise 3844 # we assume that filtered_idxs has already been calculated. 3845 if func is not None: 3846 filtered_idxs=[i for i, v in enumerate(values) \ 3847 if func(v, value)] 3848 3849 es = es.select(filtered_idxs) 3850 3851 return es 3852 3853
3854 - def __call__(self, *args, **kwds):
3855 """Shorthand notation to select() 3856 3857 This method simply passes all its arguments to L{EdgeSeq.select()}. 3858 """ 3859 return self.select(*args, **kwds)
3860
3861 ############################################################## 3862 # Additional methods of VertexSeq and EdgeSeq that call Graph methods 3863 3864 -def _graphmethod(func=None, name=None):
3865 """Auxiliary decorator 3866 3867 This decorator allows some methods of L{VertexSeq} and L{EdgeSeq} to 3868 call their respective counterparts in L{Graph} to avoid code duplication. 3869 3870 @param func: the function being decorated. This function will be 3871 called on the results of the original L{Graph} method. 3872 If C{None}, defaults to the identity function. 3873 @param name: the name of the corresponding method in L{Graph}. If 3874 C{None}, it defaults to the name of the decorated function. 3875 @return: the decorated function 3876 """ 3877 if name is None: 3878 name = func.__name__ 3879 method = getattr(Graph, name) 3880 3881 if hasattr(func, "__call__"): 3882 def decorated(*args, **kwds): 3883 self = args[0].graph 3884 return func(args[0], method(self, *args, **kwds)) 3885 else: 3886 def decorated(*args, **kwds): 3887 self = args[0].graph 3888 return method(self, *args, **