Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/classes/digraph.py @ 2:6af9afd405e9 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 0a63dd5f4d38a1f6944587f52a8cd79874177fc1"
author shellac
date Thu, 14 May 2020 14:56:58 -0400
parents 26e78fe6e8c4
children
comparison
equal deleted inserted replaced
1:75ca89e9b81c 2:6af9afd405e9
1 # Copyright (C) 2004-2019 by
2 # Aric Hagberg <hagberg@lanl.gov>
3 # Dan Schult <dschult@colgate.edu>
4 # Pieter Swart <swart@lanl.gov>
5 # All rights reserved.
6 # BSD license.
7 #
8 # Authors: Aric Hagberg <hagberg@lanl.gov>
9 # Dan Schult <dschult@colgate.edu>
10 # Pieter Swart <swart@lanl.gov>
11 """Base class for directed graphs."""
12 from copy import deepcopy
13
14 import networkx as nx
15 from networkx.classes.graph import Graph
16 from networkx.classes.coreviews import AdjacencyView
17 from networkx.classes.reportviews import OutEdgeView, InEdgeView, \
18 DiDegreeView, InDegreeView, OutDegreeView
19 from networkx.exception import NetworkXError
20 import networkx.convert as convert
21
22
23 class DiGraph(Graph):
24 """
25 Base class for directed graphs.
26
27 A DiGraph stores nodes and edges with optional data, or attributes.
28
29 DiGraphs hold directed edges. Self loops are allowed but multiple
30 (parallel) edges are not.
31
32 Nodes can be arbitrary (hashable) Python objects with optional
33 key/value attributes. By convention `None` is not used as a node.
34
35 Edges are represented as links between nodes with optional
36 key/value attributes.
37
38 Parameters
39 ----------
40 incoming_graph_data : input graph (optional, default: None)
41 Data to initialize graph. If None (default) an empty
42 graph is created. The data can be any format that is supported
43 by the to_networkx_graph() function, currently including edge list,
44 dict of dicts, dict of lists, NetworkX graph, NumPy matrix
45 or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph.
46
47 attr : keyword arguments, optional (default= no attributes)
48 Attributes to add to graph as key=value pairs.
49
50 See Also
51 --------
52 Graph
53 MultiGraph
54 MultiDiGraph
55 OrderedDiGraph
56
57 Examples
58 --------
59 Create an empty graph structure (a "null graph") with no nodes and
60 no edges.
61
62 >>> G = nx.DiGraph()
63
64 G can be grown in several ways.
65
66 **Nodes:**
67
68 Add one node at a time:
69
70 >>> G.add_node(1)
71
72 Add the nodes from any container (a list, dict, set or
73 even the lines from a file or the nodes from another graph).
74
75 >>> G.add_nodes_from([2, 3])
76 >>> G.add_nodes_from(range(100, 110))
77 >>> H = nx.path_graph(10)
78 >>> G.add_nodes_from(H)
79
80 In addition to strings and integers any hashable Python object
81 (except None) can represent a node, e.g. a customized node object,
82 or even another Graph.
83
84 >>> G.add_node(H)
85
86 **Edges:**
87
88 G can also be grown by adding edges.
89
90 Add one edge,
91
92 >>> G.add_edge(1, 2)
93
94 a list of edges,
95
96 >>> G.add_edges_from([(1, 2), (1, 3)])
97
98 or a collection of edges,
99
100 >>> G.add_edges_from(H.edges)
101
102 If some edges connect nodes not yet in the graph, the nodes
103 are added automatically. There are no errors when adding
104 nodes or edges that already exist.
105
106 **Attributes:**
107
108 Each graph, node, and edge can hold key/value attribute pairs
109 in an associated attribute dictionary (the keys must be hashable).
110 By default these are empty, but can be added or changed using
111 add_edge, add_node or direct manipulation of the attribute
112 dictionaries named graph, node and edge respectively.
113
114 >>> G = nx.DiGraph(day="Friday")
115 >>> G.graph
116 {'day': 'Friday'}
117
118 Add node attributes using add_node(), add_nodes_from() or G.nodes
119
120 >>> G.add_node(1, time='5pm')
121 >>> G.add_nodes_from([3], time='2pm')
122 >>> G.nodes[1]
123 {'time': '5pm'}
124 >>> G.nodes[1]['room'] = 714
125 >>> del G.nodes[1]['room'] # remove attribute
126 >>> list(G.nodes(data=True))
127 [(1, {'time': '5pm'}), (3, {'time': '2pm'})]
128
129 Add edge attributes using add_edge(), add_edges_from(), subscript
130 notation, or G.edges.
131
132 >>> G.add_edge(1, 2, weight=4.7 )
133 >>> G.add_edges_from([(3, 4), (4, 5)], color='red')
134 >>> G.add_edges_from([(1, 2, {'color':'blue'}), (2, 3, {'weight':8})])
135 >>> G[1][2]['weight'] = 4.7
136 >>> G.edges[1, 2]['weight'] = 4
137
138 Warning: we protect the graph data structure by making `G.edges[1, 2]` a
139 read-only dict-like structure. However, you can assign to attributes
140 in e.g. `G.edges[1, 2]`. Thus, use 2 sets of brackets to add/change
141 data attributes: `G.edges[1, 2]['weight'] = 4`
142 (For multigraphs: `MG.edges[u, v, key][name] = value`).
143
144 **Shortcuts:**
145
146 Many common graph features allow python syntax to speed reporting.
147
148 >>> 1 in G # check if node in graph
149 True
150 >>> [n for n in G if n < 3] # iterate through nodes
151 [1, 2]
152 >>> len(G) # number of nodes in graph
153 5
154
155 Often the best way to traverse all edges of a graph is via the neighbors.
156 The neighbors are reported as an adjacency-dict `G.adj` or `G.adjacency()`
157
158 >>> for n, nbrsdict in G.adjacency():
159 ... for nbr, eattr in nbrsdict.items():
160 ... if 'weight' in eattr:
161 ... # Do something useful with the edges
162 ... pass
163
164 But the edges reporting object is often more convenient:
165
166 >>> for u, v, weight in G.edges(data='weight'):
167 ... if weight is not None:
168 ... # Do something useful with the edges
169 ... pass
170
171 **Reporting:**
172
173 Simple graph information is obtained using object-attributes and methods.
174 Reporting usually provides views instead of containers to reduce memory
175 usage. The views update as the graph is updated similarly to dict-views.
176 The objects `nodes, `edges` and `adj` provide access to data attributes
177 via lookup (e.g. `nodes[n], `edges[u, v]`, `adj[u][v]`) and iteration
178 (e.g. `nodes.items()`, `nodes.data('color')`,
179 `nodes.data('color', default='blue')` and similarly for `edges`)
180 Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`.
181
182 For details on these and other miscellaneous methods, see below.
183
184 **Subclasses (Advanced):**
185
186 The Graph class uses a dict-of-dict-of-dict data structure.
187 The outer dict (node_dict) holds adjacency information keyed by node.
188 The next dict (adjlist_dict) represents the adjacency information and holds
189 edge data keyed by neighbor. The inner dict (edge_attr_dict) represents
190 the edge data and holds edge attribute values keyed by attribute names.
191
192 Each of these three dicts can be replaced in a subclass by a user defined
193 dict-like object. In general, the dict-like features should be
194 maintained but extra features can be added. To replace one of the
195 dicts create a new graph class by changing the class(!) variable
196 holding the factory for that dict-like structure. The variable names are
197 node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory,
198 adjlist_outer_dict_factory, edge_attr_dict_factory and graph_attr_dict_factory.
199
200 node_dict_factory : function, (default: dict)
201 Factory function to be used to create the dict containing node
202 attributes, keyed by node id.
203 It should require no arguments and return a dict-like object
204
205 node_attr_dict_factory: function, (default: dict)
206 Factory function to be used to create the node attribute
207 dict which holds attribute values keyed by attribute name.
208 It should require no arguments and return a dict-like object
209
210 adjlist_outer_dict_factory : function, (default: dict)
211 Factory function to be used to create the outer-most dict
212 in the data structure that holds adjacency info keyed by node.
213 It should require no arguments and return a dict-like object.
214
215 adjlist_inner_dict_factory : function, optional (default: dict)
216 Factory function to be used to create the adjacency list
217 dict which holds edge data keyed by neighbor.
218 It should require no arguments and return a dict-like object
219
220 edge_attr_dict_factory : function, optional (default: dict)
221 Factory function to be used to create the edge attribute
222 dict which holds attribute values keyed by attribute name.
223 It should require no arguments and return a dict-like object.
224
225 graph_attr_dict_factory : function, (default: dict)
226 Factory function to be used to create the graph attribute
227 dict which holds attribute values keyed by attribute name.
228 It should require no arguments and return a dict-like object.
229
230 Typically, if your extension doesn't impact the data structure all
231 methods will inherited without issue except: `to_directed/to_undirected`.
232 By default these methods create a DiGraph/Graph class and you probably
233 want them to create your extension of a DiGraph/Graph. To facilitate
234 this we define two class variables that you can set in your subclass.
235
236 to_directed_class : callable, (default: DiGraph or MultiDiGraph)
237 Class to create a new graph structure in the `to_directed` method.
238 If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used.
239
240 to_undirected_class : callable, (default: Graph or MultiGraph)
241 Class to create a new graph structure in the `to_undirected` method.
242 If `None`, a NetworkX class (Graph or MultiGraph) is used.
243
244 Examples
245 --------
246
247 Create a low memory graph class that effectively disallows edge
248 attributes by using a single attribute dict for all edges.
249 This reduces the memory used, but you lose edge attributes.
250
251 >>> class ThinGraph(nx.Graph):
252 ... all_edge_dict = {'weight': 1}
253 ... def single_edge_dict(self):
254 ... return self.all_edge_dict
255 ... edge_attr_dict_factory = single_edge_dict
256 >>> G = ThinGraph()
257 >>> G.add_edge(2, 1)
258 >>> G[2][1]
259 {'weight': 1}
260 >>> G.add_edge(2, 2)
261 >>> G[2][1] is G[2][2]
262 True
263
264
265 Please see :mod:`~networkx.classes.ordered` for more examples of
266 creating graph subclasses by overwriting the base class `dict` with
267 a dictionary-like object.
268 """
269
270 def __init__(self, incoming_graph_data=None, **attr):
271 """Initialize a graph with edges, name, or graph attributes.
272
273 Parameters
274 ----------
275 incoming_graph_data : input graph (optional, default: None)
276 Data to initialize graph. If None (default) an empty
277 graph is created. The data can be an edge list, or any
278 NetworkX graph object. If the corresponding optional Python
279 packages are installed the data can also be a NumPy matrix
280 or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph.
281
282 attr : keyword arguments, optional (default= no attributes)
283 Attributes to add to graph as key=value pairs.
284
285 See Also
286 --------
287 convert
288
289 Examples
290 --------
291 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
292 >>> G = nx.Graph(name='my graph')
293 >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges
294 >>> G = nx.Graph(e)
295
296 Arbitrary graph attribute pairs (key=value) may be assigned
297
298 >>> G = nx.Graph(e, day="Friday")
299 >>> G.graph
300 {'day': 'Friday'}
301
302 """
303 self.graph_attr_dict_factory = self.graph_attr_dict_factory
304 self.node_dict_factory = self.node_dict_factory
305 self.node_attr_dict_factory = self.node_attr_dict_factory
306 self.adjlist_outer_dict_factory = self.adjlist_outer_dict_factory
307 self.adjlist_inner_dict_factory = self.adjlist_inner_dict_factory
308 self.edge_attr_dict_factory = self.edge_attr_dict_factory
309
310 self.graph = self.graph_attr_dict_factory() # dictionary for graph attributes
311 self._node = self.node_dict_factory() # dictionary for node attr
312 # We store two adjacency lists:
313 # the predecessors of node n are stored in the dict self._pred
314 # the successors of node n are stored in the dict self._succ=self._adj
315 self._adj = self.adjlist_outer_dict_factory() # empty adjacency dict
316 self._pred = self.adjlist_outer_dict_factory() # predecessor
317 self._succ = self._adj # successor
318
319 # attempt to load graph with data
320 if incoming_graph_data is not None:
321 convert.to_networkx_graph(incoming_graph_data, create_using=self)
322 # load graph attributes (must be after convert)
323 self.graph.update(attr)
324
325 @property
326 def adj(self):
327 """Graph adjacency object holding the neighbors of each node.
328
329 This object is a read-only dict-like structure with node keys
330 and neighbor-dict values. The neighbor-dict is keyed by neighbor
331 to the edge-data-dict. So `G.adj[3][2]['color'] = 'blue'` sets
332 the color of the edge `(3, 2)` to `"blue"`.
333
334 Iterating over G.adj behaves like a dict. Useful idioms include
335 `for nbr, datadict in G.adj[n].items():`.
336
337 The neighbor information is also provided by subscripting the graph.
338 So `for nbr, foovalue in G[node].data('foo', default=1):` works.
339
340 For directed graphs, `G.adj` holds outgoing (successor) info.
341 """
342 return AdjacencyView(self._succ)
343
344 @property
345 def succ(self):
346 """Graph adjacency object holding the successors of each node.
347
348 This object is a read-only dict-like structure with node keys
349 and neighbor-dict values. The neighbor-dict is keyed by neighbor
350 to the edge-data-dict. So `G.succ[3][2]['color'] = 'blue'` sets
351 the color of the edge `(3, 2)` to `"blue"`.
352
353 Iterating over G.succ behaves like a dict. Useful idioms include
354 `for nbr, datadict in G.succ[n].items():`. A data-view not provided
355 by dicts also exists: `for nbr, foovalue in G.succ[node].data('foo'):`
356 and a default can be set via a `default` argument to the `data` method.
357
358 The neighbor information is also provided by subscripting the graph.
359 So `for nbr, foovalue in G[node].data('foo', default=1):` works.
360
361 For directed graphs, `G.adj` is identical to `G.succ`.
362 """
363 return AdjacencyView(self._succ)
364
365 @property
366 def pred(self):
367 """Graph adjacency object holding the predecessors of each node.
368
369 This object is a read-only dict-like structure with node keys
370 and neighbor-dict values. The neighbor-dict is keyed by neighbor
371 to the edge-data-dict. So `G.pred[2][3]['color'] = 'blue'` sets
372 the color of the edge `(3, 2)` to `"blue"`.
373
374 Iterating over G.pred behaves like a dict. Useful idioms include
375 `for nbr, datadict in G.pred[n].items():`. A data-view not provided
376 by dicts also exists: `for nbr, foovalue in G.pred[node].data('foo'):`
377 A default can be set via a `default` argument to the `data` method.
378 """
379 return AdjacencyView(self._pred)
380
381 def add_node(self, node_for_adding, **attr):
382 """Add a single node `node_for_adding` and update node attributes.
383
384 Parameters
385 ----------
386 node_for_adding : node
387 A node can be any hashable Python object except None.
388 attr : keyword arguments, optional
389 Set or change node attributes using key=value.
390
391 See Also
392 --------
393 add_nodes_from
394
395 Examples
396 --------
397 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
398 >>> G.add_node(1)
399 >>> G.add_node('Hello')
400 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
401 >>> G.add_node(K3)
402 >>> G.number_of_nodes()
403 3
404
405 Use keywords set/change node attributes:
406
407 >>> G.add_node(1, size=10)
408 >>> G.add_node(3, weight=0.4, UTM=('13S', 382871, 3972649))
409
410 Notes
411 -----
412 A hashable object is one that can be used as a key in a Python
413 dictionary. This includes strings, numbers, tuples of strings
414 and numbers, etc.
415
416 On many platforms hashable items also include mutables such as
417 NetworkX Graphs, though one should be careful that the hash
418 doesn't change on mutables.
419 """
420 if node_for_adding not in self._succ:
421 self._succ[node_for_adding] = self.adjlist_inner_dict_factory()
422 self._pred[node_for_adding] = self.adjlist_inner_dict_factory()
423 attr_dict = self._node[node_for_adding] = self.node_attr_dict_factory()
424 attr_dict.update(attr)
425 else: # update attr even if node already exists
426 self._node[node_for_adding].update(attr)
427
428 def add_nodes_from(self, nodes_for_adding, **attr):
429 """Add multiple nodes.
430
431 Parameters
432 ----------
433 nodes_for_adding : iterable container
434 A container of nodes (list, dict, set, etc.).
435 OR
436 A container of (node, attribute dict) tuples.
437 Node attributes are updated using the attribute dict.
438 attr : keyword arguments, optional (default= no attributes)
439 Update attributes for all nodes in nodes.
440 Node attributes specified in nodes as a tuple take
441 precedence over attributes specified via keyword arguments.
442
443 See Also
444 --------
445 add_node
446
447 Examples
448 --------
449 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
450 >>> G.add_nodes_from('Hello')
451 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
452 >>> G.add_nodes_from(K3)
453 >>> sorted(G.nodes(), key=str)
454 [0, 1, 2, 'H', 'e', 'l', 'o']
455
456 Use keywords to update specific node attributes for every node.
457
458 >>> G.add_nodes_from([1, 2], size=10)
459 >>> G.add_nodes_from([3, 4], weight=0.4)
460
461 Use (node, attrdict) tuples to update attributes for specific nodes.
462
463 >>> G.add_nodes_from([(1, dict(size=11)), (2, {'color':'blue'})])
464 >>> G.nodes[1]['size']
465 11
466 >>> H = nx.Graph()
467 >>> H.add_nodes_from(G.nodes(data=True))
468 >>> H.nodes[1]['size']
469 11
470
471 """
472 for n in nodes_for_adding:
473 # keep all this inside try/except because
474 # CPython throws TypeError on n not in self._succ,
475 # while pre-2.7.5 ironpython throws on self._succ[n]
476 try:
477 if n not in self._succ:
478 self._succ[n] = self.adjlist_inner_dict_factory()
479 self._pred[n] = self.adjlist_inner_dict_factory()
480 attr_dict = self._node[n] = self.node_attr_dict_factory()
481 attr_dict.update(attr)
482 else:
483 self._node[n].update(attr)
484 except TypeError:
485 nn, ndict = n
486 if nn not in self._succ:
487 self._succ[nn] = self.adjlist_inner_dict_factory()
488 self._pred[nn] = self.adjlist_inner_dict_factory()
489 newdict = attr.copy()
490 newdict.update(ndict)
491 attr_dict = self._node[nn] = self.node_attr_dict_factory()
492 attr_dict.update(newdict)
493 else:
494 olddict = self._node[nn]
495 olddict.update(attr)
496 olddict.update(ndict)
497
498 def remove_node(self, n):
499 """Remove node n.
500
501 Removes the node n and all adjacent edges.
502 Attempting to remove a non-existent node will raise an exception.
503
504 Parameters
505 ----------
506 n : node
507 A node in the graph
508
509 Raises
510 -------
511 NetworkXError
512 If n is not in the graph.
513
514 See Also
515 --------
516 remove_nodes_from
517
518 Examples
519 --------
520 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
521 >>> list(G.edges)
522 [(0, 1), (1, 2)]
523 >>> G.remove_node(1)
524 >>> list(G.edges)
525 []
526
527 """
528 try:
529 nbrs = self._succ[n]
530 del self._node[n]
531 except KeyError: # NetworkXError if n not in self
532 raise NetworkXError("The node %s is not in the digraph." % (n,))
533 for u in nbrs:
534 del self._pred[u][n] # remove all edges n-u in digraph
535 del self._succ[n] # remove node from succ
536 for u in self._pred[n]:
537 del self._succ[u][n] # remove all edges n-u in digraph
538 del self._pred[n] # remove node from pred
539
540 def remove_nodes_from(self, nodes):
541 """Remove multiple nodes.
542
543 Parameters
544 ----------
545 nodes : iterable container
546 A container of nodes (list, dict, set, etc.). If a node
547 in the container is not in the graph it is silently ignored.
548
549 See Also
550 --------
551 remove_node
552
553 Examples
554 --------
555 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
556 >>> e = list(G.nodes)
557 >>> e
558 [0, 1, 2]
559 >>> G.remove_nodes_from(e)
560 >>> list(G.nodes)
561 []
562
563 """
564 for n in nodes:
565 try:
566 succs = self._succ[n]
567 del self._node[n]
568 for u in succs:
569 del self._pred[u][n] # remove all edges n-u in digraph
570 del self._succ[n] # now remove node
571 for u in self._pred[n]:
572 del self._succ[u][n] # remove all edges n-u in digraph
573 del self._pred[n] # now remove node
574 except KeyError:
575 pass # silent failure on remove
576
577 def add_edge(self, u_of_edge, v_of_edge, **attr):
578 """Add an edge between u and v.
579
580 The nodes u and v will be automatically added if they are
581 not already in the graph.
582
583 Edge attributes can be specified with keywords or by directly
584 accessing the edge's attribute dictionary. See examples below.
585
586 Parameters
587 ----------
588 u, v : nodes
589 Nodes can be, for example, strings or numbers.
590 Nodes must be hashable (and not None) Python objects.
591 attr : keyword arguments, optional
592 Edge data (or labels or objects) can be assigned using
593 keyword arguments.
594
595 See Also
596 --------
597 add_edges_from : add a collection of edges
598
599 Notes
600 -----
601 Adding an edge that already exists updates the edge data.
602
603 Many NetworkX algorithms designed for weighted graphs use
604 an edge attribute (by default `weight`) to hold a numerical value.
605
606 Examples
607 --------
608 The following all add the edge e=(1, 2) to graph G:
609
610 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
611 >>> e = (1, 2)
612 >>> G.add_edge(1, 2) # explicit two-node form
613 >>> G.add_edge(*e) # single edge as tuple of two nodes
614 >>> G.add_edges_from( [(1, 2)] ) # add edges from iterable container
615
616 Associate data to edges using keywords:
617
618 >>> G.add_edge(1, 2, weight=3)
619 >>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7)
620
621 For non-string attribute keys, use subscript notation.
622
623 >>> G.add_edge(1, 2)
624 >>> G[1][2].update({0: 5})
625 >>> G.edges[1, 2].update({0: 5})
626 """
627 u, v = u_of_edge, v_of_edge
628 # add nodes
629 if u not in self._succ:
630 self._succ[u] = self.adjlist_inner_dict_factory()
631 self._pred[u] = self.adjlist_inner_dict_factory()
632 self._node[u] = self.node_attr_dict_factory()
633 if v not in self._succ:
634 self._succ[v] = self.adjlist_inner_dict_factory()
635 self._pred[v] = self.adjlist_inner_dict_factory()
636 self._node[v] = self.node_attr_dict_factory()
637 # add the edge
638 datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
639 datadict.update(attr)
640 self._succ[u][v] = datadict
641 self._pred[v][u] = datadict
642
643 def add_edges_from(self, ebunch_to_add, **attr):
644 """Add all the edges in ebunch_to_add.
645
646 Parameters
647 ----------
648 ebunch_to_add : container of edges
649 Each edge given in the container will be added to the
650 graph. The edges must be given as 2-tuples (u, v) or
651 3-tuples (u, v, d) where d is a dictionary containing edge data.
652 attr : keyword arguments, optional
653 Edge data (or labels or objects) can be assigned using
654 keyword arguments.
655
656 See Also
657 --------
658 add_edge : add a single edge
659 add_weighted_edges_from : convenient way to add weighted edges
660
661 Notes
662 -----
663 Adding the same edge twice has no effect but any edge data
664 will be updated when each duplicate edge is added.
665
666 Edge attributes specified in an ebunch take precedence over
667 attributes specified via keyword arguments.
668
669 Examples
670 --------
671 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
672 >>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples
673 >>> e = zip(range(0, 3), range(1, 4))
674 >>> G.add_edges_from(e) # Add the path graph 0-1-2-3
675
676 Associate data to edges
677
678 >>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
679 >>> G.add_edges_from([(3, 4), (1, 4)], label='WN2898')
680 """
681 for e in ebunch_to_add:
682 ne = len(e)
683 if ne == 3:
684 u, v, dd = e
685 elif ne == 2:
686 u, v = e
687 dd = {}
688 else:
689 raise NetworkXError(
690 "Edge tuple %s must be a 2-tuple or 3-tuple." % (e,))
691 if u not in self._succ:
692 self._succ[u] = self.adjlist_inner_dict_factory()
693 self._pred[u] = self.adjlist_inner_dict_factory()
694 self._node[u] = self.node_attr_dict_factory()
695 if v not in self._succ:
696 self._succ[v] = self.adjlist_inner_dict_factory()
697 self._pred[v] = self.adjlist_inner_dict_factory()
698 self._node[v] = self.node_attr_dict_factory()
699 datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
700 datadict.update(attr)
701 datadict.update(dd)
702 self._succ[u][v] = datadict
703 self._pred[v][u] = datadict
704
705 def remove_edge(self, u, v):
706 """Remove the edge between u and v.
707
708 Parameters
709 ----------
710 u, v : nodes
711 Remove the edge between nodes u and v.
712
713 Raises
714 ------
715 NetworkXError
716 If there is not an edge between u and v.
717
718 See Also
719 --------
720 remove_edges_from : remove a collection of edges
721
722 Examples
723 --------
724 >>> G = nx.Graph() # or DiGraph, etc
725 >>> nx.add_path(G, [0, 1, 2, 3])
726 >>> G.remove_edge(0, 1)
727 >>> e = (1, 2)
728 >>> G.remove_edge(*e) # unpacks e from an edge tuple
729 >>> e = (2, 3, {'weight':7}) # an edge with attribute data
730 >>> G.remove_edge(*e[:2]) # select first part of edge tuple
731 """
732 try:
733 del self._succ[u][v]
734 del self._pred[v][u]
735 except KeyError:
736 raise NetworkXError("The edge %s-%s not in graph." % (u, v))
737
738 def remove_edges_from(self, ebunch):
739 """Remove all edges specified in ebunch.
740
741 Parameters
742 ----------
743 ebunch: list or container of edge tuples
744 Each edge given in the list or container will be removed
745 from the graph. The edges can be:
746
747 - 2-tuples (u, v) edge between u and v.
748 - 3-tuples (u, v, k) where k is ignored.
749
750 See Also
751 --------
752 remove_edge : remove a single edge
753
754 Notes
755 -----
756 Will fail silently if an edge in ebunch is not in the graph.
757
758 Examples
759 --------
760 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
761 >>> ebunch = [(1, 2), (2, 3)]
762 >>> G.remove_edges_from(ebunch)
763 """
764 for e in ebunch:
765 u, v = e[:2] # ignore edge data
766 if u in self._succ and v in self._succ[u]:
767 del self._succ[u][v]
768 del self._pred[v][u]
769
770 def has_successor(self, u, v):
771 """Returns True if node u has successor v.
772
773 This is true if graph has the edge u->v.
774 """
775 return (u in self._succ and v in self._succ[u])
776
777 def has_predecessor(self, u, v):
778 """Returns True if node u has predecessor v.
779
780 This is true if graph has the edge u<-v.
781 """
782 return (u in self._pred and v in self._pred[u])
783
784 def successors(self, n):
785 """Returns an iterator over successor nodes of n.
786
787 A successor of n is a node m such that there exists a directed
788 edge from n to m.
789
790 Parameters
791 ----------
792 n : node
793 A node in the graph
794
795 Raises
796 -------
797 NetworkXError
798 If n is not in the graph.
799
800 See Also
801 --------
802 predecessors
803
804 Notes
805 -----
806 neighbors() and successors() are the same.
807 """
808 try:
809 return iter(self._succ[n])
810 except KeyError:
811 raise NetworkXError("The node %s is not in the digraph." % (n,))
812
813 # digraph definitions
814 neighbors = successors
815
816 def predecessors(self, n):
817 """Returns an iterator over predecessor nodes of n.
818
819 A predecessor of n is a node m such that there exists a directed
820 edge from m to n.
821
822 Parameters
823 ----------
824 n : node
825 A node in the graph
826
827 Raises
828 -------
829 NetworkXError
830 If n is not in the graph.
831
832 See Also
833 --------
834 successors
835 """
836 try:
837 return iter(self._pred[n])
838 except KeyError:
839 raise NetworkXError("The node %s is not in the digraph." % (n,))
840
841 @property
842 def edges(self):
843 """An OutEdgeView of the DiGraph as G.edges or G.edges().
844
845 edges(self, nbunch=None, data=False, default=None)
846
847 The OutEdgeView provides set-like operations on the edge-tuples
848 as well as edge attribute lookup. When called, it also provides
849 an EdgeDataView object which allows control of access to edge
850 attributes (but does not provide set-like operations).
851 Hence, `G.edges[u, v]['color']` provides the value of the color
852 attribute for edge `(u, v)` while
853 `for (u, v, c) in G.edges.data('color', default='red'):`
854 iterates through all the edges yielding the color attribute
855 with default `'red'` if no color attribute exists.
856
857 Parameters
858 ----------
859 nbunch : single node, container, or all nodes (default= all nodes)
860 The view will only report edges incident to these nodes.
861 data : string or bool, optional (default=False)
862 The edge attribute returned in 3-tuple (u, v, ddict[data]).
863 If True, return edge attribute dict in 3-tuple (u, v, ddict).
864 If False, return 2-tuple (u, v).
865 default : value, optional (default=None)
866 Value used for edges that don't have the requested attribute.
867 Only relevant if data is not True or False.
868
869 Returns
870 -------
871 edges : OutEdgeView
872 A view of edge attributes, usually it iterates over (u, v)
873 or (u, v, d) tuples of edges, but can also be used for
874 attribute lookup as `edges[u, v]['foo']`.
875
876 See Also
877 --------
878 in_edges, out_edges
879
880 Notes
881 -----
882 Nodes in nbunch that are not in the graph will be (quietly) ignored.
883 For directed graphs this returns the out-edges.
884
885 Examples
886 --------
887 >>> G = nx.DiGraph() # or MultiDiGraph, etc
888 >>> nx.add_path(G, [0, 1, 2])
889 >>> G.add_edge(2, 3, weight=5)
890 >>> [e for e in G.edges]
891 [(0, 1), (1, 2), (2, 3)]
892 >>> G.edges.data() # default data is {} (empty dict)
893 OutEdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})])
894 >>> G.edges.data('weight', default=1)
895 OutEdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)])
896 >>> G.edges([0, 2]) # only edges incident to these nodes
897 OutEdgeDataView([(0, 1), (2, 3)])
898 >>> G.edges(0) # only edges incident to a single node (use G.adj[0]?)
899 OutEdgeDataView([(0, 1)])
900
901 """
902 return OutEdgeView(self)
903
904 # alias out_edges to edges
905 out_edges = edges
906
907 @property
908 def in_edges(self):
909 """An InEdgeView of the Graph as G.in_edges or G.in_edges().
910
911 in_edges(self, nbunch=None, data=False, default=None):
912
913 Parameters
914 ----------
915 nbunch : single node, container, or all nodes (default= all nodes)
916 The view will only report edges incident to these nodes.
917 data : string or bool, optional (default=False)
918 The edge attribute returned in 3-tuple (u, v, ddict[data]).
919 If True, return edge attribute dict in 3-tuple (u, v, ddict).
920 If False, return 2-tuple (u, v).
921 default : value, optional (default=None)
922 Value used for edges that don't have the requested attribute.
923 Only relevant if data is not True or False.
924
925 Returns
926 -------
927 in_edges : InEdgeView
928 A view of edge attributes, usually it iterates over (u, v)
929 or (u, v, d) tuples of edges, but can also be used for
930 attribute lookup as `edges[u, v]['foo']`.
931
932 See Also
933 --------
934 edges
935 """
936 return InEdgeView(self)
937
938 @property
939 def degree(self):
940 """A DegreeView for the Graph as G.degree or G.degree().
941
942 The node degree is the number of edges adjacent to the node.
943 The weighted node degree is the sum of the edge weights for
944 edges incident to that node.
945
946 This object provides an iterator for (node, degree) as well as
947 lookup for the degree for a single node.
948
949 Parameters
950 ----------
951 nbunch : single node, container, or all nodes (default= all nodes)
952 The view will only report edges incident to these nodes.
953
954 weight : string or None, optional (default=None)
955 The name of an edge attribute that holds the numerical value used
956 as a weight. If None, then each edge has weight 1.
957 The degree is the sum of the edge weights adjacent to the node.
958
959 Returns
960 -------
961 If a single node is requested
962 deg : int
963 Degree of the node
964
965 OR if multiple nodes are requested
966 nd_iter : iterator
967 The iterator returns two-tuples of (node, degree).
968
969 See Also
970 --------
971 in_degree, out_degree
972
973 Examples
974 --------
975 >>> G = nx.DiGraph() # or MultiDiGraph
976 >>> nx.add_path(G, [0, 1, 2, 3])
977 >>> G.degree(0) # node 0 with degree 1
978 1
979 >>> list(G.degree([0, 1, 2]))
980 [(0, 1), (1, 2), (2, 2)]
981
982 """
983 return DiDegreeView(self)
984
985 @property
986 def in_degree(self):
987 """An InDegreeView for (node, in_degree) or in_degree for single node.
988
989 The node in_degree is the number of edges pointing to the node.
990 The weighted node degree is the sum of the edge weights for
991 edges incident to that node.
992
993 This object provides an iteration over (node, in_degree) as well as
994 lookup for the degree for a single node.
995
996 Parameters
997 ----------
998 nbunch : single node, container, or all nodes (default= all nodes)
999 The view will only report edges incident to these nodes.
1000
1001 weight : string or None, optional (default=None)
1002 The name of an edge attribute that holds the numerical value used
1003 as a weight. If None, then each edge has weight 1.
1004 The degree is the sum of the edge weights adjacent to the node.
1005
1006 Returns
1007 -------
1008 If a single node is requested
1009 deg : int
1010 In-degree of the node
1011
1012 OR if multiple nodes are requested
1013 nd_iter : iterator
1014 The iterator returns two-tuples of (node, in-degree).
1015
1016 See Also
1017 --------
1018 degree, out_degree
1019
1020 Examples
1021 --------
1022 >>> G = nx.DiGraph()
1023 >>> nx.add_path(G, [0, 1, 2, 3])
1024 >>> G.in_degree(0) # node 0 with degree 0
1025 0
1026 >>> list(G.in_degree([0, 1, 2]))
1027 [(0, 0), (1, 1), (2, 1)]
1028
1029 """
1030 return InDegreeView(self)
1031
1032 @property
1033 def out_degree(self):
1034 """An OutDegreeView for (node, out_degree)
1035
1036 The node out_degree is the number of edges pointing out of the node.
1037 The weighted node degree is the sum of the edge weights for
1038 edges incident to that node.
1039
1040 This object provides an iterator over (node, out_degree) as well as
1041 lookup for the degree for a single node.
1042
1043 Parameters
1044 ----------
1045 nbunch : single node, container, or all nodes (default= all nodes)
1046 The view will only report edges incident to these nodes.
1047
1048 weight : string or None, optional (default=None)
1049 The name of an edge attribute that holds the numerical value used
1050 as a weight. If None, then each edge has weight 1.
1051 The degree is the sum of the edge weights adjacent to the node.
1052
1053 Returns
1054 -------
1055 If a single node is requested
1056 deg : int
1057 Out-degree of the node
1058
1059 OR if multiple nodes are requested
1060 nd_iter : iterator
1061 The iterator returns two-tuples of (node, out-degree).
1062
1063 See Also
1064 --------
1065 degree, in_degree
1066
1067 Examples
1068 --------
1069 >>> G = nx.DiGraph()
1070 >>> nx.add_path(G, [0, 1, 2, 3])
1071 >>> G.out_degree(0) # node 0 with degree 1
1072 1
1073 >>> list(G.out_degree([0, 1, 2]))
1074 [(0, 1), (1, 1), (2, 1)]
1075
1076 """
1077 return OutDegreeView(self)
1078
1079 def clear(self):
1080 """Remove all nodes and edges from the graph.
1081
1082 This also removes the name, and all graph, node, and edge attributes.
1083
1084 Examples
1085 --------
1086 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1087 >>> G.clear()
1088 >>> list(G.nodes)
1089 []
1090 >>> list(G.edges)
1091 []
1092 """
1093 self._succ.clear()
1094 self._pred.clear()
1095 self._node.clear()
1096 self.graph.clear()
1097
1098 def is_multigraph(self):
1099 """Returns True if graph is a multigraph, False otherwise."""
1100 return False
1101
1102 def is_directed(self):
1103 """Returns True if graph is directed, False otherwise."""
1104 return True
1105
1106 def to_undirected(self, reciprocal=False, as_view=False):
1107 """Returns an undirected representation of the digraph.
1108
1109 Parameters
1110 ----------
1111 reciprocal : bool (optional)
1112 If True only keep edges that appear in both directions
1113 in the original digraph.
1114 as_view : bool (optional, default=False)
1115 If True return an undirected view of the original directed graph.
1116
1117 Returns
1118 -------
1119 G : Graph
1120 An undirected graph with the same name and nodes and
1121 with edge (u, v, data) if either (u, v, data) or (v, u, data)
1122 is in the digraph. If both edges exist in digraph and
1123 their edge data is different, only one edge is created
1124 with an arbitrary choice of which edge data to use.
1125 You must check and correct for this manually if desired.
1126
1127 See Also
1128 --------
1129 Graph, copy, add_edge, add_edges_from
1130
1131 Notes
1132 -----
1133 If edges in both directions (u, v) and (v, u) exist in the
1134 graph, attributes for the new undirected edge will be a combination of
1135 the attributes of the directed edges. The edge data is updated
1136 in the (arbitrary) order that the edges are encountered. For
1137 more customized control of the edge attributes use add_edge().
1138
1139 This returns a "deepcopy" of the edge, node, and
1140 graph attributes which attempts to completely copy
1141 all of the data and references.
1142
1143 This is in contrast to the similar G=DiGraph(D) which returns a
1144 shallow copy of the data.
1145
1146 See the Python copy module for more information on shallow
1147 and deep copies, https://docs.python.org/2/library/copy.html.
1148
1149 Warning: If you have subclassed DiGraph to use dict-like objects
1150 in the data structure, those changes do not transfer to the
1151 Graph created by this method.
1152
1153 Examples
1154 --------
1155 >>> G = nx.path_graph(2) # or MultiGraph, etc
1156 >>> H = G.to_directed()
1157 >>> list(H.edges)
1158 [(0, 1), (1, 0)]
1159 >>> G2 = H.to_undirected()
1160 >>> list(G2.edges)
1161 [(0, 1)]
1162 """
1163 graph_class = self.to_undirected_class()
1164 if as_view is True:
1165 return nx.graphviews.generic_graph_view(self, Graph)
1166 # deepcopy when not a view
1167 G = Graph()
1168 G.graph.update(deepcopy(self.graph))
1169 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1170 if reciprocal is True:
1171 G.add_edges_from((u, v, deepcopy(d))
1172 for u, nbrs in self._adj.items()
1173 for v, d in nbrs.items()
1174 if v in self._pred[u])
1175 else:
1176 G.add_edges_from((u, v, deepcopy(d))
1177 for u, nbrs in self._adj.items()
1178 for v, d in nbrs.items())
1179 return G
1180
1181 def reverse(self, copy=True):
1182 """Returns the reverse of the graph.
1183
1184 The reverse is a graph with the same nodes and edges
1185 but with the directions of the edges reversed.
1186
1187 Parameters
1188 ----------
1189 copy : bool optional (default=True)
1190 If True, return a new DiGraph holding the reversed edges.
1191 If False, the reverse graph is created using a view of
1192 the original graph.
1193 """
1194 if copy:
1195 H = self.__class__()
1196 H.graph.update(deepcopy(self.graph))
1197 H.add_nodes_from((n, deepcopy(d)) for n, d in self.nodes.items())
1198 H.add_edges_from((v, u, deepcopy(d)) for u, v, d
1199 in self.edges(data=True))
1200 return H
1201 return nx.graphviews.reverse_view(self)