networkx.graph

1 """ 2 Base class for graphs. 3 4 Examples 5 ======== 6 7 Create an empty graph structure (a "null graph") with 8 zero nodes and zero edges. 9 10 >>> from networkx import * 11 >>> G=Graph() 12 13 G can be grown in several ways. 14 By adding one node at a time: 15 16 >>> G.add_node(1) 17 18 by adding a list of nodes: 19 20 >>> G.add_nodes_from([2,3]) 21 22 by using an iterator: 23 24 >>> G.add_nodes_from(xrange(100,110)) 25 26 or by adding any container of nodes 27 28 >>> H=path_graph(10) 29 >>> G.add_nodes_from(H) 30 31 H can be another graph, or dict, or set, or even a file. 32 Any hashable object (except None) can represent a node, e.g. a Graph, 33 a customized node object, etc. 34 35 >>> G.add_node(H) 36 37 G can also be grown by adding one edge at a time: 38 39 >>> G.add_edge( (1,2) ) 40 41 by adding a list of edges: 42 43 >>> G.add_edges_from([(1,2),(1,3)]) 44 45 or by adding any ebunch of edges (see above definition of an ebunch): 46 47 >>> G.add_edges_from(H.edges()) 48 49 There are no complaints when adding existing nodes or edges: 50 51 >>> G=Graph() 52 >>> G.add_edge([(1,2),(1,3)]) 53 54 will add new nodes as required. 55 56 57 """ 58 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)""" 59 # Copyright (C) 2004-206 by 60 # Aric Hagberg <hagberg@lanl.gov> 61 # Dan Schult <dschult@colgate.edu> 62 # Pieter Swart <swart@lanl.gov> 63 # Distributed under the terms of the GNU Lesser General Public License 64 # http://www.gnu.org/copyleft/lesser.html 65 # 66 from networkx.exception import NetworkXException, NetworkXError 67 import networkx.convert as convert 68

69 -class Graph(object):

70 """Graph is a simple graph without any multiple (parallel) edges 71 or self-loops. Attempting to add either will not change 72 the graph and will not report an error. 73 74 """

75 - def __init__(self, data=None, name=''):

76 """Initialize Graph. 77 78 >>> G=Graph(name="empty") 79 80 creates empty graph G with G.name="empty" 81 82 """ 83 self.adj={} # empty adjacency hash 84 # attempt to load graph with data 85 if data is not None: 86 convert.from_whatever(data,create_using=self) 87 self.name=name

88

89 - def __str__(self):

90 return self.name

91

92 - def __iter__(self):

93 """Return an iterator over the nodes in G. 94 95 This is the iterator for the underlying adjacency dict. 96 (Allows the expression 'for n in G') 97 """ 98 return self.adj.iterkeys()

99

100 - def __contains__(self,n):

101 """Return True if n is a node in graph. 102 103 Allows the expression 'n in G'. 104 105 Testing whether an unhashable object, such as a list, is in the 106 dict datastructure (self.adj) will raise a TypeError. 107 Rather than propagate this to the calling method, just 108 return False. 109 110 """ 111 try: 112 return n in self.adj 113 except TypeError: 114 return False

115

116 - def __len__(self):

117 """Return the number of nodes in graph.""" 118 return len(self.adj)

119

120 - def __getitem__(self,n):

121 """Return the neighbors of node n as a list. 122 123 This provides graph G the natural property that G[n] returns 124 the neighbors of G. 125 126 """ 127 try: 128 return self.adj[n].keys() 129 except KeyError: 130 raise NetworkXError, "node %s not in graph"%(n,)

131

132 - def prepare_nbunch(self,nbunch=None):

133 """ 134 Return a sequence (or iterator) of nodes contained 135 in nbunch which are also in the graph. 136 137 The input nbunch can be a single node, a sequence or 138 iterator of nodes or None (omitted). If None, all 139 nodes in the graph are returned. 140 141 Note: This routine exhausts any iterator nbunch. 142 143 Note: To test whether nbunch is a single node, 144 one can use "if nbunch in self:", even after processing 145 with this routine. 146 147 Note: This routine returns an empty list if 148 nbunch is not either a node, sequence, iterator, or None. 149 You can catch this exception if you want to change this 150 behavior. 151 """ 152 if nbunch is None: # include all nodes via iterator 153 bunch=self.nodes_iter() 154 elif nbunch in self: # if nbunch is a single node 155 bunch=[nbunch] 156 else: # if nbunch is a sequence of nodes 157 try: # capture error for nonsequence/iterator entries. 158 bunch=[n for n in nbunch if n in self] 159 # bunch=(n for n in nbunch if n in self) # need python 2.4 160 except TypeError: 161 bunch=[] 162 return bunch

163

164 - def info(self, n=None):

165 """Print short info for graph G or node n.""" 166 import textwrap 167 width_left = 18 168 169 if n is None: 170 print ("Name:").ljust(width_left), self.name 171 type_name = [type(self).__name__] 172 try: 173 if self.selfloops: 174 type_name.append("self-loops") 175 except: 176 pass 177 try: 178 if self.multiedges: 179 type_name.append("multi-edges") 180 except: 181 pass 182 183 print ("Type:").ljust(width_left), ",".join(type_name) 184 print ("Number of nodes:").ljust(width_left), self.number_of_nodes() 185 print ("Number of edges:").ljust(width_left), self.number_of_edges() 186 if len(self) > 0: 187 print ("Average degree:").ljust(width_left), \ 188 round( 2*self.size()/float(len(self)), 4) 189 else: 190 try: 191 list_neighbors = self.neighbors(n) 192 print "\nNode", n, "has the following properties:" 193 print ("Degree:").ljust(width_left), self.degree(n) 194 str_neighbors = str(list_neighbors) 195 str_neighbors = str_neighbors[1:len(str_neighbors)-1] 196 wrapped_neighbors = textwrap.wrap(str_neighbors, 50) 197 num_line = 0 198 for i in wrapped_neighbors: 199 if num_line == 0: 200 print ("Neighbors:").ljust(width_left), i 201 else: 202 print "".ljust(width_left), i 203 num_line += 1 204 except (KeyError, TypeError): 205 raise NetworkXError, "node %s not in graph"%(n,)

206 207

208 - def add_node(self, n):

209 """ 210 Add a single node n to the graph. 211 212 The node n can be any hashable object except None. 213 214 A hashable object is one that can be used as a key in a Python 215 dictionary. This includes strings, numbers, tuples of strings 216 and numbers, etc. On many platforms this also includes 217 mutables such as Graphs e.g., though one should be careful the 218 hash doesn't change on mutables. 219 220 Example: 221 222 >>> from networkx import * 223 >>> G=Graph() 224 >>> K3=complete_graph(3) 225 >>> G.add_node(1) 226 >>> G.add_node('Hello') 227 >>> G.add_node(K3) 228 >>> G.number_of_nodes() 229 3 230 231 """ 232 if n not in self.adj: 233 self.adj[n]={}

234 235

236 - def add_nodes_from(self, nlist):

237 """Add multiple nodes to the graph. 238 239 nlist: 240 A container of nodes that will be iterated through once 241 (thus it should be an iterator or be iterable). 242 Each element of the container should be a valid node type: 243 any hashable type except None. See add_node for details. 244 245 Examples: 246 247 >>> from networkx import * 248 >>> G=Graph() 249 >>> K3=complete_graph(3) 250 >>> G.add_nodes_from('Hello') 251 >>> G.add_nodes_from(K3) 252 >>> sorted(G.nodes()) 253 [0, 1, 2, 'H', 'e', 'l', 'o'] 254 255 """ 256 for n in nlist: 257 if n not in self.adj: 258 self.adj[n]={}

259 260

261 - def delete_node(self,n):

262 """Delete node n from graph. 263 Attempting to delete a non-existent node will raise an exception. 264 265 """ 266 try: 267 for u in self.adj[n].keys(): 268 del self.adj[u][n] # (faster) remove all edges n-u in graph 269 # self.delete_edge(n,u)# remove all edges n-u in graph 270 del self.adj[n] # now remove node 271 except KeyError: # NetworkXError if n not in self 272 raise NetworkXError, "node %s not in graph"%(n,)

273

274 - def delete_nodes_from(self,nlist):

275 """Remove nodes in nlist from graph. 276 277 nlist: 278 an iterable or iterator containing valid node names. 279 280 Attempting to delete a non-existent node will raise an exception. 281 This could mean some nodes got deleted and other valid nodes did 282 not. 283 284 """ 285 for n in nlist: 286 try: 287 for u in self.adj[n].keys(): 288 del self.adj[u][n] # (faster) remove all edges n-u in graph 289 # self.delete_edge(n,u)# remove all edges n-u in graph 290 del self.adj[n] # now remove node 291 except KeyError: # NetworkXError if n not in self 292 raise NetworkXError, "node %s not in graph"%(n,)

293 294

295 - def nodes_iter(self):

296 """Return an iterator over the graph nodes.""" 297 return self.adj.iterkeys()

298

299 - def nodes(self):

300 """Return a copy of the graph nodes in a list.""" 301 return self.adj.keys()

302

303 - def number_of_nodes(self):

304 """Return number of nodes.""" 305 return len(self.adj)

306

307 - def has_node(self,n):

308 """Return True if graph has node n. 309 310 (duplicates self.__contains__) 311 "n in G" is a more readable version of "G.has_node(n)"? 312 313 """ 314 try: 315 return n in self.adj 316 except TypeError: 317 return False

318

319 - def order(self):

320 """Return the order of a graph = number of nodes.""" 321 return len(self.adj)

322 323

324 - def add_edge(self, u, v=None):

325 """Add a single edge (u,v) to the graph. 326 327 >> G.add_edge(u,v) 328 and 329 >>> G.add_edge( (u,v) ) 330 are equivalent forms of adding a single edge between nodes u and v. 331 The nodes u and v will be automatically added if not already in 332 the graph. They must be a hashable (except None) Python object. 333 334 The following examples all add the edge (1,2) to graph G. 335 336 >>> G=Graph() 337 >>> G.add_edge( 1, 2 ) # explicit two node form 338 >>> G.add_edge( (1,2) ) # single edge as tuple of two nodes 339 >>> G.add_edges_from( [(1,2)] ) # add edges from iterable container 340 341 """ 342 if v is None: 343 (u,v)=u # no v given, assume u is an edge tuple 344 # add nodes 345 if u not in self.adj: 346 self.adj[u]={} 347 if v not in self.adj: 348 self.adj[v]={} 349 # don't create self loops, fail silently, nodes are still added 350 if u==v: 351 return 352 self.adj[u][v]=None 353 self.adj[v][u]=None

354 355

356 - def add_edges_from(self, ebunch):

357 """Add all the edges in ebunch to the graph. 358 359 ebunch: Container of 2-tuples (u,v). The container must be 360 iterable or an iterator. It is iterated over once. Adding the 361 same edge twice has no effect and does not raise an exception. 362 363 """ 364 for e in ebunch: 365 (u,v)=e 366 # add nodes 367 if u not in self.adj: 368 self.adj[u]={} 369 if v not in self.adj: 370 self.adj[v]={} 371 # don't create self loops, fail silently, nodes are still added 372 if u==v: 373 continue 374 self.adj[u][v]=None 375 self.adj[v][u]=None # add both u-v and v-u 376 377

378 - def delete_edge(self, u, v=None):

379 """Delete the single edge (u,v). 380 381 Can be used in two basic forms: 382 >>> G.delete_edge(u,v) 383 and 384 >> G.delete_edge( (u,v) ) 385 are equivalent ways of deleting a single edge between nodes u and v. 386 387 Return without complaining if the nodes or the edge do not exist. 388 389 """ 390 if v is None: 391 (u,v)=u 392 if self.adj.has_key(u) and self.adj[u].has_key(v): 393 del self.adj[u][v] 394 del self.adj[v][u] 395

396 - def delete_edges_from(self, ebunch):

397 """Delete the edges in ebunch from the graph. 398 399 ebunch: an iterator or iterable of 2-tuples (u,v). 400 401 Edges that are not in the graph are ignored. 402 403 """ 404 for (u,v) in ebunch: 405 if self.adj.has_key(u) and self.adj[u].has_key(v): 406 del self.adj[u][v] 407 del self.adj[v][u] 408

409 - def has_edge(self, u, v=None):

410 """Return True if graph contains the edge u-v, return False otherwise.""" 411 if v is None: 412 (u,v)=u # split tuple in first position 413 return self.adj.has_key(u) and self.adj[u].has_key(v)

414

415 - def has_neighbor(self, u, v):

416 """Return True if node u has neighbor v. 417 418 This is equivalent to has_edge(u,v). 419 420 """ 421 return self.adj.has_key(u) and self.adj[u].has_key(v)

422 423

424 - def get_edge(self, u, v=None):

425 """Return 1 if graph contains the edge u-v. 426 Raise an exception otherwise. 427 428 """ 429 # useful for helping build adjacency matrix representation 430 if v is None: 431 (u,v)=u 432 433 if self.has_edge(u,v): 434 return 1 435 else: 436 return None

437 438 439

440 - def neighbors_iter(self,n):

441 """Return an iterator over all neighbors of node n. """ 442 try: 443 return self.adj[n].iterkeys() 444 except KeyError: 445 raise NetworkXError, "node %s not in graph"%(n,)

446

447 - def neighbors(self, n):

448 """Return a list of nodes connected to node n. """ 449 # return lists now, was dictionary for with_labels=True 450 try: 451 return self.adj[n].keys() 452 except KeyError: 453 raise NetworkXError, "node %s not in graph"%(n,)

454

455 - def edges_iter(self, nbunch=None):

456 """Return iterator that iterates once over each edge adjacent 457 to nodes in nbunch, or over all edges in graph if no 458 nodes are specified. 459 460 If nbunch is None return all edges in the graph. 461 The argument nbunch can be any single node, or 462 any sequence or iterator of nodes. 463 Nodes in nbunch that are not in the graph will be (quietly) ignored. 464 465 """ 466 # prepare nbunch 467 if nbunch is None: # include all nodes via iterator 468 bunch=self.nodes_iter() 469 elif nbunch in self: # if nbunch is a single node 470 bunch=[nbunch] 471 else: # if nbunch is a sequence of nodes 472 try: bunch=[n for n in nbunch if n in self] 473 except TypeError: 474 bunch=[] 475 # nbunch ready 476 seen={} # helper dict to keep track of multiply stored edges 477 for n1 in bunch: 478 for n2 in self.adj[n1]: 479 if n2 not in seen: 480 yield (n1,n2) 481 seen[n1]=1 482 del(seen) # clear copy of temp dictionary

483 # iterators can remain after they finish returning values. 484 485

486 - def edges(self, nbunch=None):

487 """Return list of all edges that are adjacent to a node in nbunch, 488 or a list of all edges in graph if no nodes are specified. 489 490 If nbunch is None return all edges in the graph. 491 The argument nbunch can be any single node, or 492 any sequence or iterator of nodes. 493 Nodes in nbunch that are not in the graph will be (quietly) ignored. 494 495 For digraphs, edges=out_edges 496 497 """ 498 return list(self.edges_iter(nbunch))

499

500 - def edge_boundary(self, nbunch1, nbunch2=None):

501 """Return list of edges (n1,n2) with n1 in nbunch1 and n2 in 502 nbunch2. If nbunch2 is omitted or nbunch2=None, then nbunch2 503 is all nodes not in nbunch1. 504 505 Nodes in nbunch1 and nbunch2 that are not in the graph are 506 ignored. 507 508 nbunch1 and nbunch2 are usually meant to be disjoint, 509 but in the interest of speed and generality, that is 510 not required here. 511 512 This routine is faster if nbunch1 is smaller than nbunch2. 513 514 """ 515 if nbunch2 is None: # Then nbunch2 is complement of nbunch1 516 ndict1=dict.fromkeys([n for n in nbunch1 if n in self]) 517 return [(n1,n2) for n1 in ndict1 for n2 in self.adj[n1] \ 518 if n2 not in ndict1] 519 520 ndict2=dict.fromkeys(nbunch2) 521 return [(n1,n2) for n1 in nbunch1 if n1 in self for n2 in self.adj[n1] \ 522 if n2 in ndict2]

523

524 - def node_boundary(self, nbunch1, nbunch2=None):

525 """Return list of all nodes on external boundary of nbunch1 that are 526 in nbunch2. If nbunch2 is omitted or nbunch2=None, then nbunch2 527 is all nodes not in nbunch1. 528 529 Note that by definition the node_boundary is external to nbunch1. 530 531 Nodes in nbunch1 and nbunch2 that are not in the graph are 532 ignored. 533 534 nbunch1 and nbunch2 are usually meant to be disjoint, 535 but in the interest of speed and generality, that is 536 not required here. 537 538 This routine is faster if nbunch1 is smaller than nbunch2. 539 540 """ 541 if nbunch2 is None: # Then nbunch2 is complement of nbunch1 542 ndict1=dict.fromkeys([n for n in nbunch1 if n in self]) 543 bdy={} 544 for n1 in ndict1: 545 for n2 in self.adj[n1]: 546 if n2 not in ndict1: 547 bdy[n2]=1 # make dict to avoid duplicates 548 return bdy.keys() 549 550 ndict2=dict.fromkeys(nbunch2) 551 bdy=[] 552 for n1 in [n for n in nbunch1 if n in self]: 553 for n2 in self.adj[n1]: 554 if n2 in ndict2: 555 bdy.append(n2) 556 del ndict2[n2] # avoid duplicates 557 return bdy

558

559 - def degree(self, nbunch=None, with_labels=False):

560 """Return degree of single node or of nbunch of nodes. 561 If nbunch is omitted or nbunch=None, then return 562 degrees of *all* nodes. 563 564 The degree of a node is the number of edges attached to that 565 node. 566 567 Can be called in three ways: 568 569 G.degree(n): return the degree of node n 570 G.degree(nbunch): return a list of values, one for each n in nbunch 571 (nbunch is any iterable container of nodes.) 572 G.degree(): same as nbunch = all nodes in graph. 573 574 If with_labels==True, then return a dict that maps each n 575 in nbunch to degree(n). 576 577 Any nodes in nbunch that are not in the graph are 578 (quietly) ignored. 579 580 """ 581 if with_labels: # return a dict 582 return dict(self.degree_iter(nbunch,with_labels)) 583 elif nbunch in self: # return a single node 584 return self.degree_iter(nbunch,with_labels).next() 585 else: # return a list 586 return list(self.degree_iter(nbunch,with_labels))

587

588 - def degree_iter(self,nbunch=None,with_labels=False):

589 """Return iterator that return degree(n) or (n,degree(n)) 590 for all n in nbunch. If nbunch is ommitted, then iterate 591 over all nodes. 592 593 Can be called in three ways: 594 G.degree_iter(n): return iterator the degree of node n 595 G.degree_iter(nbunch): return a list of values, 596 one for each n in nbunch (nbunch is any iterable container of nodes.) 597 G.degree_iter(): same as nbunch = all nodes in graph. 598 599 If with_labels==True, iterator will return an (n,degree(n)) tuple of 600 node and degree. 601 602 Any nodes in nbunch that are not in the graph are 603 (quietly) ignored. 604 605 """ 606 # prepare nbunch 607 if nbunch is None: # include all nodes via iterator 608 bunch=self.nodes_iter() 609 elif nbunch in self: # if nbunch is a single node 610 bunch=[nbunch] 611 else: # if nbunch is a sequence of nodes 612 try: bunch=[n for n in nbunch if n in self] 613 except TypeError: 614 bunch=[] 615 # nbunch ready 616 if with_labels: 617 for n in bunch: 618 yield (n,len(self.adj[n])) # tuple (n,degree) 619 else: 620 for n in bunch: 621 yield len(self.adj[n]) # just degree

622

623 - def clear(self):

624 """Remove name and delete all nodes and edges from graph.""" 625 self.name='' 626 self.adj.clear()

627

628 - def copy(self):

629 """Return a (shallow) copy of the graph. 630 631 Identical to dict.copy() of adjacency dict adj, with name 632 copied as well. 633 634 """ 635 H=self.__class__() 636 H.name=self.name 637 H.adj=self.adj.copy() 638 for v in H.adj: 639 H.adj[v]=self.adj[v].copy() 640 return H

641

642 - def to_undirected(self):

643 """Return the undirected representation of the graph G. 644 645 This graph is undirected, so merely return a copy. 646 647 """ 648 return self.copy()

649 650

651 - def to_directed(self):

652 """Return a directed representation of the graph G. 653 654 A new digraph is returned with the same name, same nodes and 655 with each edge u-v represented by two directed edges 656 u->v and v->u. 657 658 """ 659 from networkx.digraph import DiGraph 660 H=DiGraph() 661 H.name=self.name 662 H.adj=self.adj.copy() # copy nodes 663 H.succ=H.adj # fix pointer again 664 for v in H.adj: 665 H.pred[v]=self.adj[v].copy() # copy adj list to predecessor 666 H.succ[v]=self.adj[v].copy() # copy adj list to successor 667 return H

668 669

670 - def subgraph(self, nbunch, inplace=False, create_using=None):

671 """ 672 Return the subgraph induced on nodes in nbunch. 673 674 nbunch: can be a single node or any iterable container of 675 of nodes. (It can be an iterable or an iterator, e.g. a list, 676 set, graph, file, numeric array, etc.) 677 678 Setting inplace=True will return the induced subgraph in the 679 original graph by deleting nodes not in nbunch. This overrides 680 create_using. Warning: this can destroy the graph. 681 682 Unless otherwise specified, return a new graph of the same 683 type as self. Use (optional) create_using=R to return the 684 resulting subgraph in R. R can be an existing graph-like 685 object (to be emptied) or R can be a call to a graph object, 686 e.g. create_using=DiGraph(). See documentation for empty_graph() 687 688 Note: use subgraph(G) rather than G.subgraph() to access the more 689 general subgraph() function from the operators module. 690 691 """ 692 bunch=self.prepare_nbunch(nbunch) 693 694 if inplace: # demolish all nodes (and attached edges) not in nbunch 695 # override any setting of create_using 696 bunch=dict.fromkeys(bunch) # make a dict 697 self.delete_nodes_from([n for n in self if n not in bunch]) 698 self.name="Subgraph of (%s)"%(self.name) 699 return self 700 701 # create new graph 702 if create_using is None: # Graph object of the same type as current graph 703 H=self.__class__() 704 else: # user specified graph 705 H=create_using 706 H.clear() 707 H.name="Subgraph of (%s)"%(self.name) 708 H.add_nodes_from(bunch) 709 710 # add edges 711 H_adj=H.adj # cache 712 self_adj=self.adj # cache 713 dict_fromkeys=dict.fromkeys 714 for n in H: 715 H_adj[n]=dict_fromkeys([u for u in self_adj[n] if u in H_adj], None) 716 return H

717 718 719 720 721 # End of basic operations (under the hood and close to the datastructure) 722 # The following remaining Graph methods use the above methods and not the 723 # datastructure directly 724

725 - def add_path(self, nlist):

726 """Add the path through the nodes in nlist to graph""" 727 fromv = nlist[0] 728 for tov in nlist[1:]: 729 self.add_edge(fromv,tov) 730 fromv=tov

731

732 - def add_cycle(self, nlist):

733 """Add the cycle of nodes in nlist to graph""" 734 self.add_path(nlist) 735 self.add_edge(nlist[-1],nlist[0]) # wrap first element

736

737 - def is_directed(self):

738 """ Return True if graph is directed.""" 739 return False

740

741 - def size(self):

742 """Return the size of a graph = number of edges. """ 743 return sum(self.degree_iter())/2

744

745 - def number_of_edges(self, u=None, v=None):

746 """Return the number of edges between nodes u and v. 747 748 If u and v are not specified return the number of edges in the 749 entire graph. 750 751 The edge argument e=(u,v) can be specified as 752 G.number_of_edges(u,v) or G.number_of_edges(e) 753 754 """ 755 if u is None: return self.size() 756 if v is None: (u,v)=u 757 if self.has_edge(u,v): 758 return 1 759 else: 760 return 0

761

762 -def _test_suite():

763 import doctest 764 suite = doctest.DocFileSuite('tests/graph_Graph.txt', 765 package='networkx') 766 return suite

767 768 769 if __name__ == "__main__": 770 import os 771 import sys 772 import unittest 773 if sys.version_info[:2] < (2, 4): 774 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2] 775 sys.exit(-1) 776 # directory of networkx package (relative to this) 777 nxbase=sys.path[0]+os.sep+os.pardir 778 sys.path.insert(0,nxbase) # prepend to search path 779 unittest.TextTestRunner().run(_test_suite()) 780

Source Code for Module networkx.graph