networkx.digraph

1 """ 2 Base class for digraphs. 3 4 5 """ 6 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)\nDan Schult(dschult@colgate.edu)""" 7 # Copyright (C) 2004-2006 by 8 # Aric Hagberg <hagberg@lanl.gov> 9 # Dan Schult <dschult@colgate.edu> 10 # Pieter Swart <swart@lanl.gov> 11 # Distributed under the terms of the GNU Lesser General Public License 12 # http://www.gnu.org/copyleft/lesser.html 13 # 14 15 from graph import Graph 16 from networkx.exception import NetworkXException, NetworkXError 17 import networkx.convert as convert 18

19 -class DiGraph(Graph):

20 """ A graph with directed edges. Subclass of Graph. 21 22 DiGraph inherits from Graph, overriding the following methods: 23 24 - __init__: replaces self.adj with the dicts self.pred and self.succ 25 - add_node 26 - delete_node 27 - add_edge 28 - delete_edge 29 - add_nodes_from 30 - delete_nodes_from 31 - add_edges_from 32 - delete_edges_from 33 - edges_iter 34 - degree_iter 35 - copy 36 - clear 37 - subgraph 38 - is_directed 39 - to_directed 40 - to_undirected 41 42 Digraph adds the following methods to those of Graph: 43 44 - successors 45 - successors_iter 46 - predecessors 47 - predecessors_iter 48 - out_degree 49 - out_degree_iter 50 - in_degree 51 - in_degree_iter 52 53 """ 54 # we store two adjacency lists: 55 # the predecessors of node n are stored in the dict self.pred 56 # the successors of node n are stored in the dict self.succ=self.adj

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

58 self.adj={} # empty adjacency hash 59 self.pred={} # predecessor 60 self.succ=self.adj # successor 61 if data is not None: 62 convert.from_whatever(data,create_using=self) 63 self.name=name

64

65 - def add_node(self, n):

66 """Add a single node to the digraph. 67 68 The node n can be any hashable object except None. 69 70 A hashable object is one that can be used as a key in a Python 71 dictionary. This includes strings, numbers, tuples of strings 72 and numbers, etc. On many platforms this also includes 73 mutables such as Graphs, though one should be careful that the 74 hash doesn't change on mutables. 75 76 >>> from networkx import * 77 >>> G=DiGraph() 78 >>> K3=complete_graph(3) 79 >>> G.add_nodes_from(K3) # add the nodes from K3 to G 80 >>> G.nodes() 81 [0, 1, 2] 82 >>> G.clear() 83 >>> G.add_node(K3) # add the graph K3 as a node in G. 84 >>> G.number_of_nodes() 85 1 86 87 """ 88 if n not in self.succ: 89 self.succ[n]={} 90 if n not in self.pred: 91 self.pred[n]={}

92

93 - def add_nodes_from(self, nlist):

94 """Add multiple nodes to the digraph. 95 96 nlist: 97 A container of nodes that will be iterated through once 98 (thus it should be an iterator or be iterable). 99 Each element of the container should be a valid node type: 100 any hashable type except None. See add_node for details. 101 102 """ 103 for n in nlist: 104 if n not in self.succ: 105 self.succ[n]={} 106 if n not in self.pred: 107 self.pred[n]={}

108

109 - def delete_node(self,n):

110 """Delete node n from the digraph. 111 Attempting to delete a non-existent node will raise a NetworkXError. 112 113 """ 114 try: 115 for u in self.succ[n].keys(): 116 del self.pred[u][n] # remove all edges n-u in graph 117 del self.succ[n] # remove node from succ 118 for u in self.pred[n].keys(): 119 del self.succ[u][n] # remove all edges n-u in graph 120 del self.pred[n] # remove node from pred 121 except KeyError: # NetworkXError if n not in self 122 raise NetworkXError, "node %s not in graph"%(n,)

123

124 - def delete_nodes_from(self,nlist):

125 """Remove nodes in nlist from the digraph. 126 127 nlist: an iterable or iterator containing valid node names. 128 129 Attempting to delete a non-existent node will raise an exception. 130 This could mean some nodes in nlist were deleted and some valid 131 nodes were not! 132 133 """ 134 for n in nlist: 135 try: 136 for u in self.succ[n].keys(): 137 # self.delete_edge(n,u)# remove all edges n-u in graph 138 del self.pred[u][n] # remove all edges n-u in graph 139 del self.succ[n] # now remove node 140 for u in self.pred[n].keys(): 141 # self.delete_edge(u,n)# remove all edges u-n in graph 142 del self.succ[u][n] # remove all edges n-u in graph 143 del self.pred[n] # now remove node 144 except KeyError: # NetworkXError if n not in self 145 raise NetworkXError, "node %s not in graph"%(n,)

146 147

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

149 """Add a single directed edge (u,v) to the digraph. 150 151 >> G.add_edge(u,v) 152 and 153 >>> G.add_edge( (u,v) ) 154 are equivalent forms of adding a single edge between nodes u and v. 155 The nodes u and v will be automatically added if not already in 156 the graph. They must be a hashable (except None) Python object. 157 158 For example, the following examples all add the edge (1,2) to 159 the digraph G. 160 161 >>> G=DiGraph() 162 >>> G.add_edge( 1, 2 ) # explicit two node form 163 >>> G.add_edge( (1,2) ) # single edge as tuple of two nodes 164 >>> G.add_edges_from( [(1,2)] ) # list of edges form 165 166 """ 167 if v is None: 168 (u,v)=u # no v given, assume u is an edge tuple 169 # add nodes 170 if u not in self.succ: 171 self.succ[u]={} 172 if u not in self.pred: 173 self.pred[u]={} 174 if v not in self.succ: 175 self.succ[v]={} 176 if v not in self.pred: 177 self.pred[v]={} 178 179 # don't create self loops, fail silently, nodes are still added 180 if u==v: 181 return 182 self.succ[u][v]=None 183 self.pred[v][u]=None

184

185 - def add_edges_from(self, ebunch):

186 """Add all the edges in ebunch to the graph. 187 188 ebunch: Container of 2-tuples (u,v). The container must be 189 iterable or an iterator. It is iterated over once. Adding the 190 same edge twice has no effect and does not raise an exception. 191 192 See add_edge for an example. 193 194 """ 195 for e in ebunch: 196 (u,v)=e 197 # add nodes 198 if u not in self.succ: 199 self.succ[u]={} 200 if u not in self.pred: 201 self.pred[u]={} 202 if v not in self.succ: 203 self.succ[v]={} 204 if v not in self.pred: 205 self.pred[v]={} 206 207 # don't create self loops, fail silently, nodes are still added 208 if u==v: 209 continue 210 self.succ[u][v]=None 211 self.pred[v][u]=None 212 213

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

215 """Delete the single directed edge (u,v) from the digraph. 216 217 Can be used in two basic forms 218 >>> G.delete_edge(u,v) 219 and 220 G.delete_edge( (u,v) ) 221 are equivalent ways of deleting a directed edge u->v. 222 223 If the edge does not exist return without complaining. 224 225 """ 226 if v is None: 227 (u,v)=u 228 if u in self.pred[v] and v in self.succ[u]: 229 del self.succ[u][v] 230 del self.pred[v][u] 231

232 - def delete_edges_from(self, ebunch):

233 """Delete the directed edges in ebunch from the digraph. 234 235 ebunch: Container of 2-tuples (u,v). The container must be 236 iterable or an iterator. It is iterated over once. 237 238 Edges that are not in the digraph are ignored. 239 240 """ 241 for (u,v) in ebunch: 242 if u in self.pred[v] and v in self.succ[u]: 243 del self.succ[u][v] 244 del self.pred[v][u] 245

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

247 """Return iterator that iterates once over each edge pointing out 248 of nodes in nbunch, or over all edges in digraph if no 249 nodes are specified. 250 251 See edges() for definition of nbunch. 252 253 Nodes in nbunch that are not in the graph will be (quietly) ignored. 254 255 """ 256 # prepare nbunch 257 if nbunch is None: # include all nodes via iterator 258 bunch=self.nodes_iter() 259 elif nbunch in self: # if nbunch is a single node 260 bunch=[nbunch] 261 else: # if nbunch is a sequence of nodes 262 try: bunch=[n for n in nbunch if n in self] 263 except TypeError: 264 bunch=[] 265 # nbunch ready 266 for n in bunch: 267 for u in self.succ[n]: 268 yield (n,u)

269

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

271 """Return iterator that iterates once over each edge adjacent 272 to nodes in nbunch, or over all edges in digraph if no 273 nodes are specified. 274 275 See edges() for definition of nbunch. 276 277 Nodes in nbunch that are not in the graph will be (quietly) ignored. 278 279 """ 280 # prepare nbunch 281 if nbunch is None: # include all nodes via iterator 282 bunch=self.nodes_iter() 283 elif nbunch in self: # if nbunch is a single node 284 bunch=[nbunch] 285 else: # if nbunch is a sequence of nodes 286 try: bunch=[n for n in nbunch if n in self] 287 except TypeError: 288 bunch=[] 289 # nbunch ready 290 for n in bunch: 291 for u in self.pred[n]: 292 yield (u,n)

293 294 295 # define edges to be out_edges implicitly since edges uses edges_iter 296 edges_iter=out_edges_iter 297

298 - def out_edges(self, nbunch=None):

299 """Return list of all edges that point out of nodes in nbunch, 300 or a list of all edges in graph if no nodes are specified. 301 302 See edges() for definition of nbunch. 303 304 Nodes in nbunch that are not in the graph will be (quietly) ignored. 305 306 """ 307 return list(self.out_edges_iter(nbunch))

308

309 - def in_edges(self, nbunch=None):

310 """Return list of all edges that point in to nodes in nbunch, 311 or a list of all edges in graph if no nodes are specified. 312 313 See edges() for definition of nbunch. 314 315 Nodes in nbunch that are not in the graph will be (quietly) ignored. 316 317 """ 318 return list(self.in_edges_iter(nbunch))

319 320

321 - def successors_iter(self,n):

322 """Return an iterator for successor nodes of n.""" 323 try: 324 return self.succ[n].iterkeys() 325 except KeyError: 326 raise NetworkXError, "node %s not in graph"%(n,)

327

328 - def predecessors_iter(self,n):

329 """Return an iterator for predecessor nodes of n.""" 330 try: 331 return self.pred[n].iterkeys() 332 except KeyError: 333 raise NetworkXError, "node %s not in graph"%(n,)

334

335 - def successors(self, n):

336 """Return sucessor nodes of n.""" 337 try: 338 return self.succ[n].keys() 339 except KeyError: 340 raise NetworkXError, "node %s not in graph"%(n,)

341

342 - def predecessors(self, n):

343 """Return predecessor nodes of n.""" 344 try: 345 return self.pred[n].keys() 346 except KeyError: 347 raise NetworkXError, "node %s not in graph"%(n,)

348 349 # digraph definintions 350 out_neighbors=successors 351 in_neighbors=predecessors 352 neighbors=successors 353 neighbors_iter=successors_iter 354

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

356 """Return iterator that returns in_degree(n)+out_degree(n) 357 or (n,in_degree(n)+out_degree(n)) for all n in nbunch. 358 If nbunch is ommitted, then iterate over *all* nodes. 359 360 Can be called in three ways: 361 G.degree_iter(n): return iterator the degree of node n 362 G.degree_iter(nbunch): return a list of values, 363 one for each n in nbunch (nbunch is any iterable container of nodes.) 364 G.degree_iter(): same as nbunch = all nodes in graph. 365 366 If with_labels=True, iterator will return an 367 (n,in_degree(n)+out_degree(n)) tuple of node and degree. 368 369 Any nodes in nbunch but not in the graph will be (quietly) ignored. 370 371 """ 372 # prepare nbunch 373 if nbunch is None: # include all nodes via iterator 374 bunch=self.nodes_iter() 375 elif nbunch in self: # if nbunch is a single node 376 bunch=[nbunch] 377 else: # if nbunch is a sequence of nodes 378 try: bunch=[n for n in nbunch if n in self] 379 except TypeError: 380 bunch=[] 381 # nbunch ready 382 if with_labels: # yield tuple (n,degree) 383 for n in bunch: 384 yield (n,len(self.succ[n])+len(self.pred[n])) 385 else: 386 for n in bunch: 387 yield len(self.succ[n])+len(self.pred[n])

388

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

390 """Return iterator for in_degree(n) or (n,in_degree(n)) 391 for all n in nbunch. 392 393 If nbunch is ommitted, then iterate over *all* nodes. 394 395 See degree_iter method for more details. 396 """ 397 # prepare nbunch 398 if nbunch is None: # include all nodes via iterator 399 bunch=self.nodes_iter() 400 elif nbunch in self: # if nbunch is a single node 401 bunch=[nbunch] 402 else: # if nbunch is a sequence of nodes 403 try: bunch=[n for n in nbunch if n in self] 404 except TypeError: 405 bunch=[] 406 # nbunch ready 407 if with_labels: # yield tuple (n,degree) 408 for n in bunch: 409 yield (n,len(self.pred[n])) 410 else: 411 for n in bunch: 412 yield len(self.pred[n])

413

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

415 """Return iterator for out_degree(n) or (n,out_degree(n)) 416 for all n in nbunch. 417 418 If nbunch is ommitted, then iterate over *all* nodes. 419 420 See degree_iter method for more details. 421 """ 422 # prepare nbunch 423 if nbunch is None: # include all nodes via iterator 424 bunch=self.nodes_iter() 425 elif nbunch in self: # if nbunch is a single node 426 bunch=[nbunch] 427 else: # if nbunch is a sequence of nodes 428 try: bunch=[n for n in nbunch if n in self] 429 except TypeError: 430 bunch=[] 431 # nbunch ready 432 if with_labels: # yield tuple (n,degree) 433 for n in bunch: 434 yield (n,len(self.succ[n])) 435 else: 436 for n in bunch: 437 yield len(self.succ[n])

438

439 - def out_degree(self, nbunch=None, with_labels=False):

440 """Return out-degree of single node or of nbunch of nodes. 441 442 If nbunch is omitted or nbunch=None, then return 443 out-degrees of *all* nodes. 444 445 """ 446 if with_labels: # return a dict 447 return dict(self.out_degree_iter(nbunch,with_labels)) 448 elif nbunch in self: # return a single node 449 return self.out_degree_iter(nbunch,with_labels).next() 450 else: # return a list 451 return list(self.out_degree_iter(nbunch,with_labels))

452

453 - def in_degree(self, nbunch=None, with_labels=False):

454 """Return in-degree of single node or of nbunch of nodes. 455 456 If nbunch is omitted or nbunch=None, then return 457 in-degrees of *all* nodes. 458 459 """ 460 if with_labels: # return a dict 461 return dict(self.in_degree_iter(nbunch,with_labels)) 462 elif nbunch in self: # return a single node 463 return self.in_degree_iter(nbunch,with_labels).next() 464 else: # return a list 465 return list(self.in_degree_iter(nbunch,with_labels))

466

467 - def clear(self):

468 """Remove name and delete all nodes and edges from digraph.""" 469 self.name='' 470 self.succ.clear() 471 self.pred.clear()

472

473 - def copy(self):

474 """Return a (shallow) copy of the digraph. 475 476 Identical to dict.copy() of adjacency dicts pred and succ, 477 with name copied as well. 478 479 """ 480 H=self.__class__() 481 H.name=self.name 482 H.adj=self.adj.copy() 483 H.succ=H.adj # fix pointer again 484 for v in H.adj: 485 H.pred[v]=self.pred[v].copy() 486 H.succ[v]=self.succ[v].copy() 487 return H

488 489

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

491 """ 492 Return the subgraph induced on nodes in nbunch. 493 494 nbunch: can be a single node or any iterable container of 495 of nodes. (It can be an iterable or an iterator, e.g. a list, 496 set, graph, file, numeric array, etc.) 497 498 Setting inplace=True will return the induced subgraph in original graph 499 by deleting nodes not in nbunch. This overrides create_using. 500 Warning: this can destroy the graph. 501 502 Unless otherwise specified, return a new graph of the same 503 type as self. Use (optional) create_using=R to return the 504 resulting subgraph in R. R can be an existing graph-like 505 object (to be emptied) or R can be a call to a graph object, 506 e.g. create_using=DiGraph(). See documentation for empty_graph() 507 508 Note: use subgraph(G) rather than G.subgraph() to access the more 509 general subgraph() function from the operators module. 510 511 """ 512 bunch=self.prepare_nbunch(nbunch) 513 514 if inplace: # demolish all nodes (and attached edges) not in nbunch 515 # override any setting of create_using 516 bunch=dict.fromkeys(bunch) # make a dict 517 self.delete_nodes_from([n for n in self if n not in bunch]) 518 self.name="Subgraph of (%s)"%(self.name) 519 return self 520 521 # create new graph 522 if create_using is None: # Graph object of the same type as current graph 523 H=self.__class__() 524 else: # user specified graph 525 H=create_using 526 H.clear() 527 H.name="Subgraph of (%s)"%(self.name) 528 H.add_nodes_from(bunch) 529 530 # add edges 531 H_succ=H.succ # cache 532 H_pred=H.pred 533 self_succ=self.succ 534 self_pred=self.pred 535 dict_fromkeys=dict.fromkeys 536 for n in H: 537 H_succ[n]=dict_fromkeys([u for u in self_succ[n] if u in H_succ], None) 538 H_pred[n]=dict_fromkeys([u for u in self_pred[n] if u in H_succ], None) 539 return H

540

541 - def is_directed(self):

542 """ Return True if a directed graph.""" 543 return True

544

545 - def to_undirected(self):

546 """Return the undirected representation of the digraph. 547 548 A new graph is returned (the underlying graph). The edge u-v 549 is in the underlying graph if either u->v or v->u is in the 550 digraph. 551 552 """ 553 H=Graph() 554 H.name=self.name 555 H.adj=self.succ.copy() # copy nodes 556 for u in H.adj: 557 H.adj[u]=self.succ[u].copy() # copy successors 558 for v in self.pred[u]: # now add predecessors to adj too 559 H.adj[u][v]=None 560 return H

561

562 - def to_directed(self):

563 """Return a directed representation of the digraph. 564 565 This is already directed, so merely return a copy. 566 567 """ 568 return self.copy()

569

570 - def reverse(self):

571 """ 572 Return a new digraph with the same vertices and edges 573 as G but with the directions of the edges reversed. 574 """ 575 H=self.__class__() # new empty DiGraph 576 577 H.name="Reverse of (%s)"%(self.name) 578 579 H.add_nodes_from(self) 580 H.add_edges_from([(v,u) for (u,v) in self.edges_iter()]) 581 return H

582

583 -def _test_suite():

584 import doctest 585 suite = doctest.DocFileSuite('tests/digraph_DiGraph.txt', 586 package='networkx') 587 return suite

588 589 590 if __name__ == "__main__": 591 import os 592 import sys 593 import unittest 594 if sys.version_info[:2] < (2, 4): 595 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2] 596 sys.exit(-1) 597 # directory of networkx package (relative to this) 598 nxbase=sys.path[0]+os.sep+os.pardir 599 sys.path.insert(0,nxbase) # prepend to search path 600 unittest.TextTestRunner().run(_test_suite()) 601

Source Code for Module networkx.digraph