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
8
9
10
11
12
13
14
15 from graph import Graph
16 from networkx.exception import NetworkXException, NetworkXError
17 import networkx.convert as convert
18
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
55
56
58 self.adj={}
59 self.pred={}
60 self.succ=self.adj
61 if data is not None:
62 convert.from_whatever(data,create_using=self)
63 self.name=name
64
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
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
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]
117 del self.succ[n]
118 for u in self.pred[n].keys():
119 del self.succ[u][n]
120 del self.pred[n]
121 except KeyError:
122 raise NetworkXError, "node %s not in graph"%(n,)
123
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
138 del self.pred[u][n]
139 del self.succ[n]
140 for u in self.pred[n].keys():
141
142 del self.succ[u][n]
143 del self.pred[n]
144 except KeyError:
145 raise NetworkXError, "node %s not in graph"%(n,)
146
147
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
169
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
180 if u==v:
181 return
182 self.succ[u][v]=None
183 self.pred[v][u]=None
184
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
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
208 if u==v:
209 continue
210 self.succ[u][v]=None
211 self.pred[v][u]=None
212
213
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
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
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
257 if nbunch is None:
258 bunch=self.nodes_iter()
259 elif nbunch in self:
260 bunch=[nbunch]
261 else:
262 try: bunch=[n for n in nbunch if n in self]
263 except TypeError:
264 bunch=[]
265
266 for n in bunch:
267 for u in self.succ[n]:
268 yield (n,u)
269
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
281 if nbunch is None:
282 bunch=self.nodes_iter()
283 elif nbunch in self:
284 bunch=[nbunch]
285 else:
286 try: bunch=[n for n in nbunch if n in self]
287 except TypeError:
288 bunch=[]
289
290 for n in bunch:
291 for u in self.pred[n]:
292 yield (u,n)
293
294
295
296 edges_iter=out_edges_iter
297
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
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
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
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
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
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
350 out_neighbors=successors
351 in_neighbors=predecessors
352 neighbors=successors
353 neighbors_iter=successors_iter
354
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
373 if nbunch is None:
374 bunch=self.nodes_iter()
375 elif nbunch in self:
376 bunch=[nbunch]
377 else:
378 try: bunch=[n for n in nbunch if n in self]
379 except TypeError:
380 bunch=[]
381
382 if with_labels:
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
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
398 if nbunch is None:
399 bunch=self.nodes_iter()
400 elif nbunch in self:
401 bunch=[nbunch]
402 else:
403 try: bunch=[n for n in nbunch if n in self]
404 except TypeError:
405 bunch=[]
406
407 if with_labels:
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
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
423 if nbunch is None:
424 bunch=self.nodes_iter()
425 elif nbunch in self:
426 bunch=[nbunch]
427 else:
428 try: bunch=[n for n in nbunch if n in self]
429 except TypeError:
430 bunch=[]
431
432 if with_labels:
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:
447 return dict(self.out_degree_iter(nbunch,with_labels))
448 elif nbunch in self:
449 return self.out_degree_iter(nbunch,with_labels).next()
450 else:
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:
461 return dict(self.in_degree_iter(nbunch,with_labels))
462 elif nbunch in self:
463 return self.in_degree_iter(nbunch,with_labels).next()
464 else:
465 return list(self.in_degree_iter(nbunch,with_labels))
466
468 """Remove name and delete all nodes and edges from digraph."""
469 self.name=''
470 self.succ.clear()
471 self.pred.clear()
472
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
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:
515
516 bunch=dict.fromkeys(bunch)
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
522 if create_using is None:
523 H=self.__class__()
524 else:
525 H=create_using
526 H.clear()
527 H.name="Subgraph of (%s)"%(self.name)
528 H.add_nodes_from(bunch)
529
530
531 H_succ=H.succ
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
542 """ Return True if a directed graph."""
543 return True
544
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()
556 for u in H.adj:
557 H.adj[u]=self.succ[u].copy()
558 for v in self.pred[u]:
559 H.adj[u][v]=None
560 return H
561
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
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__()
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
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
598 nxbase=sys.path[0]+os.sep+os.pardir
599 sys.path.insert(0,nxbase)
600 unittest.TextTestRunner().run(_test_suite())
601