networkx.xdigraph

1 """ 2 Base class for XDiGraph. 3 4 XDiGraph allows directed graphs with self-loops, multiple edges, 5 arbitrary (hashable) objects as nodes, and arbitrary objects 6 associated with edges. 7 8 9 """ 10 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)""" 11 12 # Copyright (C) 2004-2006 by 13 # Aric Hagberg <hagberg@lanl.gov> 14 # Dan Schult <dschult@colgate.edu> 15 # Pieter Swart <swart@lanl.gov> 16 # Distributed under the terms of the GNU Lesser General Public License 17 # http://www.gnu.org/copyleft/lesser.html 18 # 19 20 from networkx.digraph import DiGraph 21 from networkx.exception import NetworkXException, NetworkXError 22 import networkx.convert as convert 23

24 -class XDiGraph(DiGraph):

25 """ 26 Digraphs with (optional) self-loops, (optional) multiple edges, 27 arbitrary (hashable) objects as nodes, and arbitrary 28 objects associated with edges. 29 30 An XDiGraph edge is uniquely specified by a 3-tuple 31 e=(n1,n2,x), where n1 and n2 are (hashable) objects (nodes) and x 32 is an arbitrary (and not necessarily unique) object associated with 33 that edge. 34 35 See the documentation of XGraph for the use of the optional 36 parameters selfloops (defaults is False) and multiedges 37 (default is False). 38 39 XDiGraph inherits from DiGraph, with all purely node-specific methods 40 identical to those of DiGraph. XDiGraph edges are identical to XGraph 41 edges, except that they are directed rather than undirected. 42 XDiGraph replaces the following DiGraph methods: 43 44 - __init__: read multiedges and selfloops optional args. 45 - add_edge 46 - add_edges_from 47 - delete_edge 48 - delete_edges_from 49 - has_edge 50 - has_predecessor 51 - has_successor 52 - get_edge 53 - edges_iter 54 - in_edges_iter 55 - out_edges_iter 56 - neighbors_iter 57 - successors_iter 58 - predecessors_iter 59 - degree_iter 60 - out_degree_iter 61 - in_degree_iter 62 - subgraph 63 - copy 64 - to_undirected 65 - reverse 66 67 XDiGraph also adds the following methods to those of DiGraph: 68 69 - allow_selfloops 70 - remove_all_selfloops 71 - ban_selfloops 72 - nodes_with_selfloops 73 - self_loop_edges 74 - number_of_selfloops 75 76 - delete_multiedge 77 - allow_multiedges 78 - ban_multiedges 79 - remove_all_multiedges 80 81 While XDiGraph does not inherit from XGraph, we compare them here. 82 XDigraph adds the following methods to those of XGraph: 83 84 - has_successor 85 - successors 86 - successors_iter 87 - has_predecessor 88 - predecessors 89 - predecessors_iter 90 - out_degree 91 - out_degree_iter 92 - in_degree 93 - in_degree_iter 94 - reverse 95 96 """ 97 # XDiGraph, like DiGraph, uses two adjacency lists: 98 # predecessors of node n are stored in the dict 99 # self.pred successors of node n are stored in the 100 # dict self.succ=self.adj 101 # 102 # For each edge (n1,n2,x) in self.succ there exists a corresponding edge 103 # (n2,n1,x) in self.pred 104

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

106 """Initialize XDiGraph. 107 108 Optional arguments:: 109 name: digraph name (default="No Name") 110 selfloops: if True then selfloops are allowed (default=False) 111 multiedges: if True then multiple edges are allowed (default=False) 112 113 """ 114 self.adj={} # adjacency list 115 self.pred={} # predecessor 116 self.succ=self.adj # successor is same as adj 117 self.selfloops=selfloops 118 self.multiedges=multiedges 119 if data is not None: 120 convert.from_whatever(data,create_using=self) 121 self.name=name

122 123

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

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

197 # from both succ and pred 198

199 - def add_edges_from(self, ebunch):

200 """Add multiple directed edges to the digraph. 201 ebunch: Container of edges. Each edge e in container will be added 202 using add_edge(e). See add_edge documentation. 203 The container must be iterable or an iterator. 204 It is iterated over once. 205 """ 206 for e in ebunch: 207 # the function-call-in-a-loop cost can be avoided by pasting 208 # in the code from add_edge, do we have a good reason ? 209 self.add_edge(e) 210

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

212 """Return True if digraph contains directed edge (n1,n2,x). 213 214 Can be called as G.has_edge(n1,n2,x) 215 or as G.has_edge(e), where e=(n1,n2,x). 216 217 If x is unspecified, i.e. if called with an edge of the form 218 e=(n1,n2), then return True if there exists ANY edge from n1 219 to n2 (equivalent to has_successor(n1,n2)). 220 221 """ 222 # parse args 223 if n2 is None: 224 # has_edge was called as has_edge(e) 225 if len(n1)==3: # case e=(n1,n2,x) 226 n1,n2,x=n1 227 else: # case=(n1,n2) 228 n1,n2=n1 # return True if there exists ANY edge n1->n2 229 return self.has_successor(n1,n2) 230 else: 231 if x is None: 232 # has_edge was called as has_edge(n1,n2) 233 # return True if there exists ANY edge n1->n2 234 return self.has_successor(n1,n2) 235 # case where x is specified 236 if self.multiedges: 237 return (self.succ.has_key(n1) and 238 self.succ[n1].has_key(n2) and 239 x in self.succ[n1][n2]) 240 else: 241 return (self.succ.has_key(n1) and 242 self.succ[n1].has_key(n2) and 243 x==self.succ[n1][n2])

244

245 - def has_successor(self, n1, n2):

246 """Return True if node n1 has a successor n2. 247 248 Return True if there exists ANY edge (n1,n2,x) for some x. 249 250 """ 251 return (self.succ.has_key(n1) and 252 self.succ[n1].has_key(n2))

253

254 - def has_predecessor(self, n1, n2):

255 """Return True if node n1 has a predecessor n2. 256 257 Return True if there exists ANY edge (n2,n1,x) for some x. 258 259 """ 260 return (self.pred.has_key(n1) and 261 self.pred[n1].has_key(n2))

262 263

264 - def get_edge_iter(self, u, v=None):

265 """Return an iterator over the objects associated with each edge 266 from node u to node v. 267 268 """ 269 if v is None: 270 (u,v)=u 271 try: 272 data = self.adj[u][v] # raises KeyError if edge not found 273 except KeyError: 274 raise NetworkXError, "Edge (%s,%s) requested via get_edge_iter does not exist."%(u,v) 275 if self.multiedges: 276 for d in data: 277 yield d 278 else: 279 yield data

280

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

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

298

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

300 """ Delete all edges between nodes n1 and n2. 301 302 When there is only a single edge allowed between nodes 303 (multiedges=False), this just calls delete_edge(n1,n2), 304 otherwise (multiedges=True) all edges between n1 and n2 are deleted. 305 """ 306 if self.multiedges: 307 for x in self.get_edge(n1,n2): 308 self.delete_edge(n1,n2,x) 309 else: 310 self.delete_edge(n1,n2) 311 return

312 313

314 - def delete_edge(self, n1, n2=None, x=None, all=False):

315 """Delete the directed edge (n1,n2,x) from the graph. 316 317 Can be called either as 318 >>> G.delete_edge(n1,n2,x) 319 or as 320 >>> G.delete_edge(e) 321 where e=(n1,n2,x). 322 323 If called with an edge e=(n1,n2), or as G.delete_edge(n1,n2) 324 then the edge (n1,n2,None) will be deleted. 325 326 If the edge does not exist, do nothing. 327 328 To delete *all* edges between n1 and n2 use 329 >>> G.delete_multiedges(n1,n2) 330 331 """ 332 if n2 is None: # was called as delete_edge(e) 333 if len(n1)==3: #case e=(n1,n2,x) 334 n1,n2,x=n1 335 else: # assume e=(n1,n2) 336 n1,n2=n1 # x=None 337 338 if self.multiedges: # multiedges are stored as a list 339 if (self.succ.has_key(n1) 340 and self.succ[n1].has_key(n2) 341 and x in self.succ[n1][n2]): 342 self.succ[n1][n2].remove(x) # remove the edge item from list 343 self.pred[n2][n1].remove(x) 344 if len(self.succ[n1][n2])==0: # if last edge between n1 and n2 345 del self.succ[n1][n2] # was deleted, remove all trace 346 del self.pred[n2][n1] 347 else: # delete single edge 348 if self.has_successor(n1,n2): 349 del self.succ[n1][n2] 350 del self.pred[n2][n1] 351 return 352

353 - def delete_edges_from(self, ebunch):

354 """Delete edges in ebunch from the graph. 355 356 ebunch: Container of edges. Each edge must be a 3-tuple 357 (n1,n2,x) or a 2-tuple (n1,n2). The container must be 358 iterable or an iterator, and is iterated over once. 359 360 Edges that are not in the graph are ignored. 361 362 """ 363 for e in ebunch: 364 self.delete_edge(e) 365

366 - def out_edges_iter(self, nbunch=None):

367 """Return iterator that iterates once over each edge pointing 368 out of nodes in nbunch, or over all edges in digraph if no 369 nodes are specified. 370 371 See edges() for definition of nbunch. 372 373 Nodes in nbunch that are not in the graph will be (quietly) ignored. 374 375 """ 376 # prepare nbunch 377 if nbunch is None: # include all nodes via iterator 378 bunch=self.nodes_iter() 379 elif nbunch in self: # if nbunch is a single node 380 bunch=[nbunch] 381 else: # if nbunch is a sequence of nodes 382 try: bunch=[n for n in nbunch if n in self] 383 except TypeError: 384 bunch=[] 385 # nbunch ready 386 if self.multiedges: 387 for n1 in bunch: 388 for n2,elist in self.succ[n1].iteritems(): 389 for data in elist: 390 yield (n1,n2,data) 391 else: 392 for n1 in bunch: 393 for n2,data in self.succ[n1].iteritems(): 394 yield (n1,n2,data)

395

396 - def in_edges_iter(self, nbunch=None):

397 """Return iterator that iterates once over each edge pointing in 398 to nodes in nbunch, or over all edges in digraph if no 399 nodes are specified. 400 401 See edges() for definition of nbunch. 402 403 Nodes in nbunch that are not in the graph will be (quietly) ignored. 404 405 """ 406 # prepare nbunch 407 if nbunch is None: # include all nodes via iterator 408 bunch=self.nodes_iter() 409 elif nbunch in self: # if nbunch is a single node 410 bunch=[nbunch] 411 else: # if nbunch is a sequence of nodes 412 try: bunch=[n for n in nbunch if n in self] 413 except TypeError: 414 bunch=[] 415 # nbunch ready 416 if self.multiedges: 417 for n1 in bunch: 418 for n2,elist in self.pred[n1].iteritems(): 419 for data in elist: 420 yield (n2,n1,data) 421 else: 422 for n1 in bunch: 423 for n2,data in self.pred[n1].iteritems(): 424 yield (n2,n1,data)

425

426 - def successors_iter(self, n):

427 """Return an iterator of nodes pointing out of node n. 428 429 Returns the same data as out_edges(n) but in a different format. 430 431 """ 432 try: 433 if self.multiedges: 434 for nbr,elist in self.succ[n].iteritems(): 435 for data in elist: 436 yield nbr 437 else: 438 for nbr in self.succ[n].iterkeys(): 439 yield nbr 440 except KeyError: 441 raise NetworkXError, "node %s not in graph"%(n,)

442

443 - def predecessors_iter(self, n):

444 """Return an iterator of nodes pointing in to node n. 445 446 Returns the same data as in_edges(n) but in a different format. 447 448 """ 449 try: 450 if self.multiedges: 451 for nbr,elist in self.pred[n].iteritems(): 452 for data in elist: 453 yield nbr 454 else: 455 for nbr in self.pred[n].iterkeys(): 456 yield nbr 457 except KeyError: 458 raise NetworkXError, "node %s not in graph"%(n,)

459 460 edges_iter=out_edges_iter 461 neighbors_iter=successors_iter 462

463 - def predecessors(self, n):

464 """Return predecessor nodes of n.""" 465 return list(self.predecessors_iter(n))

466

467 - def successors(self, n):

468 """Return sucessor nodes of n.""" 469 return list(self.successors_iter(n))

470 471 neighbors=successors 472

473 - def in_degree_iter(self, nbunch=None, with_labels=False):

474 """Return iterator for in_degree(n) or (n,in_degree(n)) 475 for all n in nbunch. 476 477 If nbunch is ommitted, then iterate over *all* nodes. 478 479 See degree_iter method for more details. 480 """ 481 # prepare nbunch 482 if nbunch is None: # include all nodes via iterator 483 bunch=self.nodes_iter() 484 elif nbunch in self: # if nbunch is a single node 485 bunch=[nbunch] 486 else: # if nbunch is a sequence of nodes 487 try: bunch=[n for n in nbunch if n in self] 488 except TypeError: 489 bunch=[] 490 # nbunch ready 491 if self.multiedges: 492 if with_labels: # yield tuple (n,in_degree) 493 for n in bunch: 494 yield (n,sum([len(edge) for edge in self.pred[n].itervalues()])) 495 else: 496 for n in bunch: 497 yield sum([len(edge) for edge in self.pred[n].itervalues()]) 498 else: 499 if with_labels: # yield tuple (n,in_degree) 500 for n in bunch: 501 yield (n,len(self.pred[n])) 502 else: 503 for n in bunch: 504 yield len(self.pred[n])

505

506 - def out_degree_iter(self, nbunch=None, with_labels=False):

507 """Return iterator for out_degree(n) or (n,out_degree(n)) 508 for all n in nbunch. 509 510 If nbunch is ommitted, then iterate over *all* nodes. 511 512 See degree_iter method for more details. 513 """ 514 # prepare nbunch 515 if nbunch is None: # include all nodes via iterator 516 bunch=self.nodes_iter() 517 elif nbunch in self: # if nbunch is a single node 518 bunch=[nbunch] 519 else: # if nbunch is a sequence of nodes 520 try: bunch=[n for n in nbunch if n in self] 521 except TypeError: 522 bunch=[] 523 # nbunch ready 524 if self.multiedges: 525 if with_labels: 526 for n in bunch: 527 yield (n,sum([len(edge) for edge in self.succ[n].itervalues()])) 528 else: 529 for n in bunch: 530 yield sum([len(edge) for edge in self.succ[n].itervalues()]) 531 else: 532 if with_labels: 533 for n in bunch: 534 yield (n,len(self.succ[n])) 535 else: 536 for n in bunch: 537 yield len(self.succ[n])

538

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

540 """Return iterator that returns in_degree(n)+out_degree(n) 541 or (n,in_degree(n)+out_degree(n)) for all n in nbunch. 542 If nbunch is ommitted, then iterate over *all* nodes. 543 544 Can be called in three ways: 545 G.degree_iter(n): return iterator the degree of node n 546 G.degree_iter(nbunch): return a list of values, 547 one for each n in nbunch (nbunch is any iterable container of nodes.) 548 G.degree_iter(): same as nbunch = all nodes in graph. 549 550 If with_labels=True, iterator will return an 551 (n,in_degree(n)+out_degree(n)) tuple of node and degree. 552 553 Any nodes in nbunch but not in the graph will be (quietly) ignored. 554 555 """ 556 # prepare nbunch 557 if nbunch is None: # include all nodes via iterator 558 bunch=self.nodes_iter() 559 elif nbunch in self: # if nbunch is a single node 560 bunch=[nbunch] 561 else: # if nbunch is a sequence of nodes 562 try: bunch=[n for n in nbunch if n in self] 563 except TypeError: 564 bunch=[] 565 # nbunch ready 566 if self.multiedges: 567 for n in bunch: 568 d=sum([len(e) for e in self.succ[n].itervalues()]) + \ 569 sum([len(e) for e in self.pred[n].itervalues()]) 570 if with_labels: 571 yield (n,d) 572 else: 573 yield d 574 else: 575 for n in bunch: 576 d=len(self.succ[n])+len(self.pred[n]) 577 if with_labels: 578 yield (n,d) 579 else: 580 yield d

581

582 - def nodes_with_selfloops(self):

583 """Return list of all nodes having self-loops.""" 584 if not self.selfloops: 585 return [] 586 else: 587 # only need to do this for succ 588 return [n for n in self if self.succ[n].has_key(n)]

589

590 - def selfloop_edges(self):

591 """Return all edges that are self-loops.""" 592 nlist=self.nodes_with_selfloops() 593 if self.multiedges: 594 return [ (n,n,x) for n in nlist for x in self.adj[n][n]] 595 else: 596 return [ (n,n,self.adj[n][n]) for n in nlist ]

597

598 - def number_of_selfloops(self):

599 """Return number of self-loops in graph.""" 600 nlist=self.nodes_with_selfloops() 601 if self.multiedges: 602 return sum([ len(self.adj[n][n]) for n in nlist]) 603 else: 604 return len(nlist)

605

606 - def allow_selfloops(self):

607 """Henceforth allow addition of self-loops 608 (edges from a node to itself). 609 610 This doesn't change the graph structure, only what you can do to it. 611 """ 612 self.selfloops=True

613

614 - def remove_all_selfloops(self):

615 """Remove self-loops from the graph (edges from a node to itself).""" 616 for n in self.succ: 617 if self.succ[n].has_key(n): 618 del self.succ[n][n] 619 del self.pred[n][n]

620

621 - def ban_selfloops(self):

622 """Remove self-loops from the graph and henceforth do not allow 623 their creation. 624 """ 625 self.remove_all_selfloops() 626 self.selfloops=False

627 628

629 - def allow_multiedges(self):

630 """Henceforth allow addition of multiedges (more than one 631 edge between two nodes). 632 633 Warning: This causes all edge data to be converted to lists. 634 """ 635 if self.multiedges: return # already multiedges 636 self.multiedges=True 637 for v in self.succ: 638 for (u,edgedata) in self.succ[v].iteritems(): 639 self.succ[v][u]=[edgedata] 640 self.pred[u][v]=[edgedata]

641

642 - def remove_all_multiedges(self):

643 # FIXME, write tests 644 """Remove multiedges retaining the data from the first edge""" 645 if not self.multiedges: # nothing to do 646 return 647 for v in self.succ: 648 for (u,edgedata) in self.succ[v].iteritems(): 649 if len(edgedata)>1: 650 self.succ[v][u]=[edgedata[0]] 651 self.pred[u][v]=[edgedata[0]]

652

653 - def ban_multiedges(self):

654 """Remove multiedges retaining the data from the first edge. 655 Henceforth do not allow multiedges. 656 """ 657 if not self.multiedges: # nothing to do 658 return 659 self.multiedges=False 660 for v in self.succ: 661 for (u,edgedata) in self.succ[v].iteritems(): 662 self.succ[v][u]=edgedata[0] 663 self.pred[u][v]=edgedata[0]

664

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

666 """Return the subgraph induced on nodes in nbunch. 667 668 nbunch: can be a single node or any iterable container of 669 of nodes. (It can be an iterable or an iterator, e.g. a list, 670 set, graph, file, numeric array, etc.) 671 672 Setting inplace=True will return induced subgraph in original 673 graph by deleting nodes not in nbunch. It overrides any setting 674 of create_using. 675 676 WARNING: specifying inplace=True makes it easy to destroy the graph. 677 678 Unless otherwise specified, return a new graph of the same 679 type as self. Use (optional) create_using=R to return the 680 resulting subgraph in R. R can be an existing graph-like 681 object (to be emptied) or R can be a call to a graph object, 682 e.g. create_using=DiGraph(). See documentation for 683 empty_graph() 684 685 Note: use subgraph(G) rather than G.subgraph() to access the more 686 general subgraph() function from the operators module. 687 688 """ 689 bunch=self.prepare_nbunch(nbunch) 690 691 # WARNING: setting inplace=True destroys the graph. 692 if inplace: # demolish all nodes (and attached edges) not in nbunch 693 # override any setting of create_using 694 bunch=dict.fromkeys(bunch) # make a dict 695 self.delete_nodes_from([n for n in self if n not in bunch]) 696 self.name="Subgraph of (%s)"%(self.name) 697 return self 698 699 # create new graph 700 if create_using is None: 701 # return a Graph object of the same type as current graph 702 # subgraph inherits multiedges and selfloops settings 703 H=self.__class__(multiedges=self.multiedges, 704 selfloops=self.selfloops) 705 else: 706 # Recreate subgraph with create_using. 707 # Currently create_using must be an XGraph type object 708 # or a multi-edge list will be copied as a single edge 709 H=create_using 710 H.clear() 711 H.name="Subgraph of (%s)"%(self.name) 712 H.add_nodes_from(bunch) 713 714 # add edges 715 H_succ=H.succ # store in local variables 716 H_pred=H.pred 717 self_succ=self.succ 718 self_pred=self.pred 719 if self.multiedges: 720 for n in H: # create dicts with copies of edge data list from self 721 H_succ[n]=dict([(u,d[:]) for u,d in self_succ[n].iteritems() if u in H_succ]) 722 H_pred[n]=dict([(u,d[:]) for u,d in self_pred[n].iteritems() if u in H_pred]) 723 else: # no multiedges 724 for n in H: # create dicts with edge data from self 725 H_succ[n]=dict([(u,d) for u,d in self_succ[n].iteritems() if u in H_succ]) 726 H_pred[n]=dict([(u,d) for u,d in self_pred[n].iteritems() if u in H_pred]) 727 return H

728

729 - def copy(self):

730 """Return a (shallow) copy of the digraph. 731 732 Return a new XDiGraph with same name and same attributes for 733 selfloop and multiededges. Each node and each edge in original 734 graph are added to the copy. 735 736 """ 737 H=self.__class__(name=self.name, multiedges=self.multiedges, selfloops=self.selfloops) 738 H.add_nodes_from(self) 739 H.add_edges_from(self.edges_iter()) 740 return H

741

742 - def to_undirected(self):

743 """Return the underlying graph of G. 744 745 The underlying graph is its undirected representation: each directed 746 edge is replaced with an undirected edge. 747 748 If multiedges=True, then an XDiGraph with only two directed 749 edges (1,2,"red") and (2,1,"blue") will be converted into an 750 XGraph with two undirected edges (1,2,"red") and (1,2,"blue"). 751 Two directed edges (1,2,"red") and (2,1,"red") will result in 752 in two undirected edges (1,2,"red") and (1,2,"red"). 753 754 If multiedges=False, then two directed edges (1,2,"red") and 755 (2,1,"blue") can only result in one undirected edge, and there 756 is no guarantee which one it is. 757 758 """ 759 from networkx.xgraph import XGraph 760 H=XGraph(name=self.name, multiedges=self.multiedges, selfloops=self.selfloops) 761 H.add_nodes_from(self) 762 H.add_edges_from(self.edges_iter()) 763 return H

764

765 - def reverse(self):

766 """ 767 Return a new digraph with the same vertices and edges 768 as self but with the directions of the edges reversed. 769 """ 770 H=self.__class__(name="Reverse of (%s)"%self.name,\ 771 multiedges=self.multiedges, selfloops=self.selfloops) 772 H.add_nodes_from(self) 773 H.add_edges_from( [ (v,u,d) for (u,v,d) in self.edges_iter() ] ) 774 return H

775

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

777 """Return the number of edges between nodes u and v. 778 779 If u and v are not specified return the number of edges in the 780 entire graph. 781 782 The edge argument e=(u,v) can be specified as 783 G.number_of_edges(u,v) or G.number_of_edges(e) 784 785 """ 786 if u is None: return self.size() 787 if v is None: 788 if len(u)==3: # e=(u,v,x) 789 (u,v,x)=u 790 else: # assume e=(u,v), x=None 791 (u,v)=u 792 793 if self.has_edge(u,v,x): 794 if self.multiedges: 795 if x is None: # return all edges 796 return len(self.get_edge(u,v)) 797 else: # only edges matching (u,v,x) 798 return len([d for d in self.get_edge(u,v) if d is x]) 799 else: 800 return 1 801 else: 802 return 0

803 804 805 806

807 -def _test_suite():

808 import doctest 809 suite = doctest.DocFileSuite( 810 'tests/xdigraph_XDiGraph.txt', 811 package='networkx') 812 return suite

813 814 815 if __name__ == "__main__": 816 import os 817 import sys 818 import unittest 819 if sys.version_info[:2] < (2, 4): 820 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2] 821 sys.exit(-1) 822 # directory of networkx package (relative to this) 823 nxbase=sys.path[0]+os.sep+os.pardir 824 sys.path.insert(0,nxbase) # prepend to search path 825 unittest.TextTestRunner().run(_test_suite()) 826

Source Code for Module networkx.xdigraph