networkx.xgraph

1 """ 2 Base class for XGraph. 3 4 XGraph allows self-loops and multiple edges 5 with arbitrary (hashable) objects as 6 nodes and arbitrary objects associated with edges. 7 8 Examples 9 ======== 10 11 Create an empty graph structure (a "null graph") with no nodes and no edges 12 13 >>> from networkx import * 14 >>> G=XGraph() # default no self-loops, no multiple edges 15 16 You can add nodes in the same way as the simple Graph class 17 >>> G.add_nodes_from(xrange(100,110)) 18 19 You can add edges as for simple Graph class, but with optional edge 20 data/labels/objects. 21 22 >>> G.add_edges_from([(1,2,0.776),(1,3,0.535)]) 23 24 For graph coloring problems, one could use 25 >>> G.add_edges_from([(1,2,"blue"),(1,3,"red")]) 26 27 """ 28 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)""" 29 30 # Copyright (C) 2004-2006 by 31 # Aric Hagberg <hagberg@lanl.gov> 32 # Dan Schult <dschult@colgate.edu> 33 # Pieter Swart <swart@lanl.gov> 34 # Distributed under the terms of the GNU Lesser General Public License 35 # http://www.gnu.org/copyleft/lesser.html 36 # 37 38 39 from networkx.graph import Graph 40 from networkx.exception import NetworkXException, NetworkXError 41 import networkx.convert as convert 42

43 -class XGraph(Graph):

44 """A class implementing general undirected graphs, allowing 45 (optional) self-loops, multiple edges, arbitrary (hashable) 46 objects as nodes and arbitrary objects associated with 47 edges. 48 49 An XGraph edge is specified by a 3-tuple e=(n1,n2,x), 50 where n1 and n2 are nodes (hashable objects) and x is an 51 arbitrary (and not necessarily unique) object associated with that 52 edge. 53 54 >>> G=XGraph() 55 56 creates an empty simple and undirected graph (no self-loops or 57 multiple edges allowed). It is equivalent to the expression: 58 59 >>> G=XGraph(name='',selfloops=False,multiedges=False) 60 61 >>> G=XGraph(name="empty",multiedges=True) 62 63 creates an empty graph with G.name="empty", that does not allow 64 the addition of self-loops but does allow for multiple edges. 65 66 See also the XDiGraph class. 67 68 69 XGraph inherits from Graph, overriding the following methods: 70 71 - __init__ 72 - add_edge 73 - add_edges_from 74 - has_edge, has_neighbor 75 - get_edge 76 - edges_iter 77 - delete_edge 78 - delete_edges_from 79 - degree_iter 80 - to_directed 81 - copy 82 - subgraph 83 84 XGraph adds the following methods to those of Graph: 85 86 - delete_multiedge 87 - nodes_with_selfloops 88 - selfloop_edges 89 - number_of_selfloops 90 - allow_selfloops 91 - remove_all_selfloops 92 - ban_selfloops 93 - allow_multiedges 94 - remove_all_multiedges 95 - ban_multiedges 96 97 """ 98 99

100 - def __init__(self, data=None, name='', selfloops=False, multiedges=False):

101 """Initialize XGraph. 102 103 Optional arguments:: 104 name: graph name (default='') 105 selfloops: if True selfloops are allowed (default=False) 106 multiedges: if True multiple edges are allowed (default=False) 107 108 """ 109 self.adj={} # adjacency list 110 self.selfloops=selfloops 111 self.multiedges=multiedges 112 if data is not None: 113 self=convert.from_whatever(data,create_using=self) 114 self.name=name

115

116 - def __getitem__(self,n):

117 """Return the neighbors of node n as a list. 118 119 This provides graph G the natural property that G[n] returns 120 the neighbors of G. 121 122 """ 123 return list(self.neighbors_iter(n))

124

125 - def add_edge(self, n1, n2=None, x=None):

126 """Add a single edge to the graph. 127 128 Can be called as G.add_edge(n1,n2,x) or as 129 G.add_edge(e), where e=(n1,n2,x). 130 131 n1,n2 are node objects, and are added to the Graph if not already 132 present. Nodes must be hashable Python objects (except None). 133 134 x is an arbitrary (not necessarily hashable) object associated 135 with this edge. It can be used to associate one or more: 136 labels, data records, weights or any arbirary objects to 137 edges. The default is the Python None. 138 139 For example, if the graph G was created with 140 141 >>> G=XGraph() 142 143 then G.add_edge(1,2,"blue") will add the edge (1,2,"blue"). 144 145 If G.multiedges=False, then a subsequent G.add_edge(1,2,"red") 146 will change the above edge (1,2,"blue") into the edge (1,2,"red"). 147 148 149 If G.multiedges=True, then two successive calls to 150 G.add_edge(1,2,"red") will result in 2 edges of the form 151 (1,2,"red") that can not be distinguished from one another. 152 153 G.add_edge(1,2,"green") will add both edges (1,2,X) and (2,1,X). 154 155 If self.selfloops=False, then calling add_edge(n1,n1,x) will have no 156 effect on the Graph. 157 158 Objects associated to an edge can be retrieved using edges(), 159 edge_iter(), or get_edge(). 160 161 """ 162 if n2 is None: # add_edge was called as add_edge(e), with e=(n1,n2,x) 163 if len(n1)==3: # case e=(n1,n2,x) 164 n1,n2,x=n1 165 else: # assume e=(n1,n2) 166 n1,n2=n1 # x=None 167 168 # if edge exists, quietly return if multiple edges are not allowed 169 if not self.multiedges and self.has_edge(n1,n2,x): 170 return 171 172 # add nodes 173 if n1 not in self.adj: 174 self.adj[n1]={} 175 if n2 not in self.adj: 176 self.adj[n2]={} 177 178 # self loop? quietly return if not allowed 179 if not self.selfloops and n1==n2: 180 return 181 182 if self.multiedges: # add x to the end of the list of objects 183 # that defines the edges between n1 and n2 184 self.adj[n1][n2]=self.adj[n1].get(n2,[])+ [x] 185 if n1!=n2: 186 self.adj[n2][n1]=self.adj[n2].get(n1,[])+ [x] 187 else: # x is the new object assigned to single edge between n1 and n2 188 self.adj[n1][n2]=x 189 if n1!=n2: 190 self.adj[n2][n1]=x # a copy would be required to avoid

191 # modifying both at the same time 192 # when doing a delete_edge 193

194 - def add_edges_from(self, ebunch):

195 """Add multiple edges to the graph. 196 197 ebunch: Container of edges. Each edge must be a 3-tuple 198 (n1,n2,x) or a 2-tuple (n1,n2). See add_edge documentation. 199 200 The container must be iterable or an iterator. It is iterated 201 over once. 202 203 """ 204 for e in ebunch: 205 self.add_edge(e) 206

207 - def has_edge(self, n1, n2=None, x=None):

208 """Return True if graph contains edge (n1,n2,x). 209 210 Can be called as G.has_edge(n1,n2,x) 211 or as G.has_edge(e), where e=(n1,n2,x). 212 213 If x is unspecified or None, i.e. if called with an edge of the form 214 e=(n1,n2), then return True if there exists ANY edge between 215 n1 and n2 (equivalent to has_neighbor(n1,n2)) 216 217 """ 218 if n2 is None: 219 # has_edge was called as has_edge(e) 220 if len(n1)==3: #case e=(n1,n2,x) 221 n1,n2,x=n1 222 else: # assume e=(n1,n2) 223 n1,n2=n1 224 return self.has_neighbor(n1,n2) 225 else: 226 if x is None: 227 # has_edge was called as has_edge(n1,n2) 228 # return True if there exists ANY 229 # edge between n1 and n2 230 return self.has_neighbor(n1,n2) 231 # case where x is specified 232 if self.multiedges: 233 return (self.adj.has_key(n1) and 234 self.adj[n1].has_key(n2) and 235 x in self.adj[n1][n2]) 236 else: 237 return (self.adj.has_key(n1) and 238 self.adj[n1].has_key(n2) and 239 x==self.adj[n1][n2])

240 241

242 - def has_neighbor(self, n1, n2):

243 """Return True if node n1 has neighbor n2. 244 245 Note that this returns True if there exists ANY edge (n1,n2,x) 246 for some x. 247 248 """ 249 return (self.adj.has_key(n1) and 250 self.adj[n1].has_key(n2))

251

252 - def neighbors_iter(self, n):

253 """Return an iterator of nodes connected to node n. 254 255 Returns the same data as edges(n) but in a different format. 256 257 """ 258 if not self.multiedges: 259 try: 260 for nbr in self.adj[n].iterkeys(): 261 yield nbr 262 except KeyError: 263 raise NetworkXError, "node %s not in graph"%(n,) 264 else: 265 if n not in self: 266 raise NetworkXError, "node %s not in graph"%(n,) 267 for (u,v,d) in self.edges_iter(n): 268 yield v

269

270 - def neighbors(self, n):

271 """Return a list of nodes connected to node n. """ 272 return list(self.neighbors_iter(n))

273

274 - def get_edge_iter(self, u, v):

275 """Return an iterator over the objects associated with each edge 276 from node u to node v. 277 278 """ 279 try: 280 data = self.adj[u][v] # raises KeyError if edge not found 281 except KeyError: 282 raise NetworkXError, "Edge (%s,%s) requested via get_edge_iter does not exist."%(u,v) 283 if self.multiedges: 284 for d in data: 285 yield d 286 else: 287 yield data

288

289 - def get_edge(self, u, v):

290 """Return the objects associated with each edge from node u to node v. 291 292 If multiedges=False, a single object is returned. 293 If multiedges=True, a list of objects is returned. 294 If no edge exists, None is returned. 295 296 """ 297 try: 298 data=self.adj[u][v] 299 except KeyError: 300 raise NetworkXError, "Edge (%s,%s) requested via get_edge does not exist."%(u,v) 301 if self.multiedges: 302 return data[:] # copy of the list 303 return data

304

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

306 """Return iterator that iterates once over each edge adjacent 307 to nodes in nbunch, or over all nodes in graph if nbunch=None. 308 309 If nbunch is None return all edges in the graph. 310 The argument nbunch can be any single node, or 311 any sequence or iterator of nodes. 312 Nodes in nbunch that are not in the graph will be (quietly) ignored. 313 314 """ 315 # prepare nbunch 316 if nbunch is None: # include all nodes via iterator 317 bunch=self.nodes_iter() 318 elif nbunch in self: # if nbunch is a single node 319 bunch=[nbunch] 320 else: # if nbunch is a sequence of nodes 321 try: bunch=[n for n in nbunch if n in self] 322 except TypeError: 323 bunch=[] 324 # nbunch ready 325 seen={} # helper dict used to avoid duplicate edges 326 if self.multiedges: 327 for n1 in bunch: 328 for n2,elist in self.adj[n1].iteritems(): 329 if n2 not in seen: 330 for data in elist: 331 yield (n1,n2,data) 332 seen[n1]=1 333 else: 334 for n1 in bunch: 335 for n2,data in self.adj[n1].iteritems(): 336 if n2 not in seen: 337 yield (n1,n2,data) 338 seen[n1]=1 339 del(seen) # clear copy of temp dictionary

340 # iterators can remain after they finish returning values. 341

342 - def delete_multiedge(self, n1, n2):

343 """ Delete all edges between nodes n1 and n2. 344 345 When there is only a single edge allowed between nodes 346 (multiedges=False), this just calls delete_edge(n1,n2) 347 otherwise (multiedges=True) all edges between n1 and n2 are deleted. 348 """ 349 if self.multiedges: 350 for x in self.get_edge(n1, n2): 351 self.delete_edge(n1, n2, x) 352 else: 353 self.delete_edge(n1, n2) 354 return

355

356 - def delete_edge(self, n1, n2=None, x=None):

357 """Delete the edge (n1,n2,x) from the graph. 358 359 Can be called either as 360 361 >>> G.delete_edge(n1,n2,x) 362 or 363 >>> G.delete_edge(e) 364 365 where e=(n1,n2,x). 366 367 The default edge data is x=None 368 369 If called with an edge e=(n1,n2), or as G.delete_edge(n1,n2) 370 then the edge (n1,n2,None) will be deleted. 371 372 If the edge does not exist, do nothing. 373 374 To delete *all* edges between n1 and n2 use 375 >>> G.delete_multiedges(n1,n2) 376 377 """ 378 if n2 is None: # was called as delete_edge(e) 379 if len(n1)==3: # case e=(n1,n2,x) 380 n1,n2,x=n1 381 else: # assume e=(n1,n2), x unspecified, set to None 382 n1,n2=n1 # x=None 383 384 if self.multiedges: 385 if (self.adj.has_key(n1) 386 and self.adj[n1].has_key(n2) 387 and x in self.adj[n1][n2]): # if (n1,n2,x) is an edge; 388 self.adj[n1][n2].remove(x) # remove the edge item from list 389 if n1!=n2: # and if not self loop 390 self.adj[n2][n1].remove(x) # remove n2->n1 entry 391 if len(self.adj[n1][n2])==0: # if last edge between n1 and n2 392 del self.adj[n1][n2] # was deleted, remove all trace 393 if n1!=n2: # and if not self loop 394 del self.adj[n2][n1] # remove n2->n1 entry 395 else: # delete single edge 396 if self.has_neighbor(n1,n2): 397 del self.adj[n1][n2] 398 if n1!=n2: 399 del self.adj[n2][n1] 400 return 401

402 - def delete_edges_from(self, ebunch):

403 """Delete edges in ebunch from the graph. 404 405 ebunch: Container of edges. Each edge must be a 3-tuple 406 (n1,n2,x) or a 2-tuple (n1,n2). In the latter case all edges 407 between n1 and n2 will be deleted. See delete_edge. 408 409 The container must be iterable or an iterator, and 410 is iterated over once. Edges that are not in the graph are ignored. 411 412 """ 413 for e in ebunch: 414 # the function-call-in-a-loop cost can be avoided by pasting 415 # in the code from delete_edge, do we have a good reason ? 416 self.delete_edge(e) 417

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

419 """This is the degree() method returned in iterator form. 420 If with_labels=True, iterator yields 2-tuples of form (n,degree(n)) 421 (like iteritems() on a dict.) 422 """ 423 # prepare nbunch 424 if nbunch is None: # include all nodes via iterator 425 bunch=self.nodes_iter() 426 elif nbunch in self: # if nbunch is a single node 427 bunch=[nbunch] 428 else: # if nbunch is a sequence of nodes 429 try: bunch=[n for n in nbunch if n in self] 430 except TypeError: 431 bunch=[] 432 # nbunch ready 433 if self.multiedges: 434 for n in bunch: 435 deg = sum([len(e) for e in self.adj[n].itervalues()]) 436 if self.selfloops and self.adj[n].has_key(n): 437 deg+= len(self.adj[n][n]) # double count self-loops 438 if with_labels: 439 yield (n,deg) # tuple (n,degree) 440 else: 441 yield deg 442 else: 443 for n in bunch: 444 deg=len(self.adj[n]) 445 deg+= self.adj[n].has_key(n) # double count self-loop 446 if with_labels: 447 yield (n,deg) # tuple (n,degree) 448 else: 449 yield deg

450

451 - def copy(self):

452 """Return a (shallow) copy of the graph. 453 454 Return a new XGraph with same name and same attributes for 455 selfloop and multiededges. Each node and each edge in original 456 graph are added to the copy. 457 458 """ 459 H=self.__class__(multiedges=self.multiedges,selfloops=self.selfloops) 460 H.name=self.name 461 for n in self: 462 H.add_node(n) 463 for e in self.edges_iter(): 464 H.add_edge(e) 465 return H

466

467 - def to_directed(self):

468 """Return a directed representation of the XGraph G. 469 470 A new XDigraph is returned with the same name, same nodes and 471 with each edge (u,v,x) replaced by two directed edges 472 (u,v,x) and (v,u,x). 473 474 """ 475 from networkx.xdigraph import XDiGraph 476 H=XDiGraph(selfloops=self.selfloops,multiedges=self.multiedges) 477 H.name=self.name 478 for n in self: 479 H.add_node(n) 480 for e in self.edges_iter(): 481 H.add_edge(e[0],e[1],e[2]) 482 H.add_edge(e[1],e[0],e[2]) 483 return H

484

485 - def nodes_with_selfloops(self):

486 """Return list of all nodes having self-loops.""" 487 if not self.selfloops: 488 return [] 489 else: 490 return [n for n in self if self.adj[n].has_key(n)]

491

492 - def selfloop_edges(self):

493 """Return all edges that are self-loops.""" 494 nlist=self.nodes_with_selfloops() 495 if self.multiedges: 496 return [ (n,n,x) for n in nlist for x in self.adj[n][n]] 497 else: 498 return [ (n,n,self.adj[n][n]) for n in nlist ]

499

500 - def number_of_selfloops(self):

501 """Return number of self-loops in graph.""" 502 nlist=self.nodes_with_selfloops() 503 if self.multiedges: 504 return sum([ len(self.adj[n][n]) for n in nlist]) 505 else: 506 return len(nlist)

507

508 - def allow_selfloops(self):

509 """Henceforth allow addition of self-loops 510 (edges from a node to itself). 511 512 This doesn't change the graph structure, only what you can do to it. 513 """ 514 self.selfloops=True

515

516 - def remove_all_selfloops(self):

517 """Remove self-loops from the graph (edges from a node to itself).""" 518 if not self.selfloops: 519 # nothing to do 520 return 521 for n in self.adj: 522 if self.adj[n].has_key(n): 523 del self.adj[n][n]

524

525 - def ban_selfloops(self):

526 """Remove self-loops from the graph and henceforth do not allow 527 their creation. 528 """ 529 self.remove_all_selfloops() 530 self.selfloops=False

531 532

533 - def allow_multiedges(self):

534 """Henceforth allow addition of multiedges (more than one 535 edge between two nodes). 536 537 Warning: This causes all edge data to be converted to lists. 538 """ 539 if self.multiedges: return # already multiedges 540 self.multiedges=True 541 for v in self.adj: 542 for (u,edgedata) in self.adj[v].iteritems(): 543 self.adj[v][u]=[edgedata]

544

545 - def remove_all_multiedges(self):

546 # FIXME, write tests 547 """Remove multiedges retaining the data from the first edge""" 548 if not self.multiedges: # nothing to do 549 return 550 for v in self.adj: 551 for (u,edgedata) in self.adj[v].iteritems(): 552 if len(edgedata)>1: 553 self.adj[v][u]=[edgedata[0]]

554

555 - def ban_multiedges(self):

556 """Remove multiedges retaining the data from the first edge. 557 Henceforth do not allow multiedges. 558 """ 559 if not self.multiedges: # nothing to do 560 return 561 self.multiedges=False 562 for v in self.adj: 563 for (u,edgedata) in self.adj[v].iteritems(): 564 self.adj[v][u]=edgedata[0]

565

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

567 """Return the subgraph induced on nodes in nbunch. 568 569 nbunch: can be a single node or any iterable container of 570 of nodes. (It can be an iterable or an iterator, e.g. a list, 571 set, graph, file, numeric array, etc.) 572 573 Setting inplace=True will return induced subgraph in original 574 graph by deleting nodes not in nbunch. It overrides any setting 575 of create_using. 576 577 WARNING: specifying inplace=True makes it easy to destroy the graph. 578 579 Unless otherwise specified, return a new graph of the same 580 type as self. Use (optional) create_using=R to return the 581 resulting subgraph in R. R can be an existing graph-like 582 object (to be emptied) or R can be a call to a graph object, 583 e.g. create_using=DiGraph(). See documentation for 584 empty_graph() 585 586 Note: use subgraph(G) rather than G.subgraph() to access the more 587 general subgraph() function from the operators module. 588 589 """ 590 bunch=self.prepare_nbunch(nbunch) 591 592 # WARNING: setting inplace=True destroys the graph. 593 if inplace: # demolish all nodes (and attached edges) not in nbunch 594 # override any setting of create_using 595 bunch=dict.fromkeys(bunch) # make a dict 596 self.delete_nodes_from([n for n in self if n not in bunch]) 597 self.name="Subgraph of (%s)"%(self.name) 598 return self 599 600 # Create new graph 601 if create_using is None: 602 # return a Graph object of the same type as current graph 603 # subgraph inherits multiedges and selfloops settings 604 H=self.__class__(multiedges=self.multiedges, 605 selfloops=self.selfloops) 606 else: 607 # Recreate subgraph with create_using. 608 # Currently create_using must be an XGraph type object 609 # or a multi-edge list will be copied as a single edge 610 H=create_using 611 H.clear() 612 H.name="Subgraph of (%s)"%(self.name) 613 H.add_nodes_from(bunch) 614 615 # add edges 616 H_adj=H.adj # store in local variables 617 self_adj=self.adj 618 if self.multiedges: 619 for n in H: # create neighbor dict with copy of data list from self 620 H_adj[n]=dict([(u,d[:]) for u,d in self_adj[n].iteritems() if u in H_adj]) 621 else: # no multiedges 622 for n in H: # create neighbor dict with edge data from self 623 H_adj[n]=dict([(u,d) for u,d in self_adj[n].iteritems() if u in H_adj]) 624 return H

625 626

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

628 """Return the number of edges between nodes u and v. 629 630 If u and v are not specified return the number of edges in the 631 entire graph. 632 633 The edge argument e=(u,v) can be specified as 634 G.number_of_edges(u,v) or G.number_of_edges(e) 635 636 """ 637 if u is None: return self.size() 638 if v is None: 639 if len(u)==3: # e=(u,v,x) 640 (u,v,x)=u 641 else: # assume e=(u,v), x=None 642 (u,v)=u 643 644 if self.has_edge(u,v,x): 645 if self.multiedges: 646 if x is None: # return all edges 647 return len(self.get_edge(u,v)) 648 else: # only edges matching (u,v,x) 649 return len([d for d in self.get_edge(u,v) if d is x]) 650 else: 651 return 1 652 else: 653 return 0

654 655 656

657 -def _test_suite():

658 import doctest 659 suite = doctest.DocFileSuite( 660 'tests/xgraph_XGraph.txt', 661 'tests/xgraph_XGraph_multiedges_selfloops.txt', 662 package='networkx') 663 return suite

664 665 666 if __name__ == "__main__": 667 import os 668 import sys 669 import unittest 670 if sys.version_info[:2] < (2, 4): 671 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2] 672 sys.exit(-1) 673 # directory of networkx package (relative to this) 674 nxbase=sys.path[0]+os.sep+os.pardir 675 sys.path.insert(0,nxbase) # prepend to search path 676 unittest.TextTestRunner().run(_test_suite()) 677

Source Code for Module networkx.xgraph