Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/classes/graph.py @ 0:26e78fe6e8c4 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
author shellac
date Sat, 02 May 2020 07:14:21 -0400
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:26e78fe6e8c4
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 # Author: Aric Hagberg (hagberg@lanl.gov),
9 # Pieter Swart (swart@lanl.gov),
10 # Dan Schult(dschult@colgate.edu)
11 """Base class for undirected graphs.
12
13 The Graph class allows any hashable object as a node
14 and can associate key/value attribute pairs with each undirected edge.
15
16 Self-loops are allowed but multiple edges are not (see MultiGraph).
17
18 For directed graphs see DiGraph and MultiDiGraph.
19 """
20 import warnings
21 from copy import deepcopy
22 from collections.abc import Mapping
23
24 import networkx as nx
25 from networkx.classes.coreviews import AtlasView, AdjacencyView
26 from networkx.classes.reportviews import NodeView, EdgeView, DegreeView
27 from networkx.exception import NetworkXError
28 import networkx.convert as convert
29 from networkx.utils import pairwise
30
31
32 class Graph(object):
33 """
34 Base class for undirected graphs.
35
36 A Graph stores nodes and edges with optional data, or attributes.
37
38 Graphs hold undirected edges. Self loops are allowed but multiple
39 (parallel) edges are not.
40
41 Nodes can be arbitrary (hashable) Python objects with optional
42 key/value attributes. By convention `None` is not used as a node.
43
44 Edges are represented as links between nodes with optional
45 key/value attributes.
46
47 Parameters
48 ----------
49 incoming_graph_data : input graph (optional, default: None)
50 Data to initialize graph. If None (default) an empty
51 graph is created. The data can be any format that is supported
52 by the to_networkx_graph() function, currently including edge list,
53 dict of dicts, dict of lists, NetworkX graph, NumPy matrix
54 or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph.
55
56 attr : keyword arguments, optional (default= no attributes)
57 Attributes to add to graph as key=value pairs.
58
59 See Also
60 --------
61 DiGraph
62 MultiGraph
63 MultiDiGraph
64 OrderedGraph
65
66 Examples
67 --------
68 Create an empty graph structure (a "null graph") with no nodes and
69 no edges.
70
71 >>> G = nx.Graph()
72
73 G can be grown in several ways.
74
75 **Nodes:**
76
77 Add one node at a time:
78
79 >>> G.add_node(1)
80
81 Add the nodes from any container (a list, dict, set or
82 even the lines from a file or the nodes from another graph).
83
84 >>> G.add_nodes_from([2, 3])
85 >>> G.add_nodes_from(range(100, 110))
86 >>> H = nx.path_graph(10)
87 >>> G.add_nodes_from(H)
88
89 In addition to strings and integers any hashable Python object
90 (except None) can represent a node, e.g. a customized node object,
91 or even another Graph.
92
93 >>> G.add_node(H)
94
95 **Edges:**
96
97 G can also be grown by adding edges.
98
99 Add one edge,
100
101 >>> G.add_edge(1, 2)
102
103 a list of edges,
104
105 >>> G.add_edges_from([(1, 2), (1, 3)])
106
107 or a collection of edges,
108
109 >>> G.add_edges_from(H.edges)
110
111 If some edges connect nodes not yet in the graph, the nodes
112 are added automatically. There are no errors when adding
113 nodes or edges that already exist.
114
115 **Attributes:**
116
117 Each graph, node, and edge can hold key/value attribute pairs
118 in an associated attribute dictionary (the keys must be hashable).
119 By default these are empty, but can be added or changed using
120 add_edge, add_node or direct manipulation of the attribute
121 dictionaries named graph, node and edge respectively.
122
123 >>> G = nx.Graph(day="Friday")
124 >>> G.graph
125 {'day': 'Friday'}
126
127 Add node attributes using add_node(), add_nodes_from() or G.nodes
128
129 >>> G.add_node(1, time='5pm')
130 >>> G.add_nodes_from([3], time='2pm')
131 >>> G.nodes[1]
132 {'time': '5pm'}
133 >>> G.nodes[1]['room'] = 714 # node must exist already to use G.nodes
134 >>> del G.nodes[1]['room'] # remove attribute
135 >>> list(G.nodes(data=True))
136 [(1, {'time': '5pm'}), (3, {'time': '2pm'})]
137
138 Add edge attributes using add_edge(), add_edges_from(), subscript
139 notation, or G.edges.
140
141 >>> G.add_edge(1, 2, weight=4.7 )
142 >>> G.add_edges_from([(3, 4), (4, 5)], color='red')
143 >>> G.add_edges_from([(1, 2, {'color': 'blue'}), (2, 3, {'weight': 8})])
144 >>> G[1][2]['weight'] = 4.7
145 >>> G.edges[1, 2]['weight'] = 4
146
147 Warning: we protect the graph data structure by making `G.edges` a
148 read-only dict-like structure. However, you can assign to attributes
149 in e.g. `G.edges[1, 2]`. Thus, use 2 sets of brackets to add/change
150 data attributes: `G.edges[1, 2]['weight'] = 4`
151 (For multigraphs: `MG.edges[u, v, key][name] = value`).
152
153 **Shortcuts:**
154
155 Many common graph features allow python syntax to speed reporting.
156
157 >>> 1 in G # check if node in graph
158 True
159 >>> [n for n in G if n < 3] # iterate through nodes
160 [1, 2]
161 >>> len(G) # number of nodes in graph
162 5
163
164 Often the best way to traverse all edges of a graph is via the neighbors.
165 The neighbors are reported as an adjacency-dict `G.adj` or `G.adjacency()`
166
167 >>> for n, nbrsdict in G.adjacency():
168 ... for nbr, eattr in nbrsdict.items():
169 ... if 'weight' in eattr:
170 ... # Do something useful with the edges
171 ... pass
172
173 But the edges() method is often more convenient:
174
175 >>> for u, v, weight in G.edges.data('weight'):
176 ... if weight is not None:
177 ... # Do something useful with the edges
178 ... pass
179
180 **Reporting:**
181
182 Simple graph information is obtained using object-attributes and methods.
183 Reporting typically provides views instead of containers to reduce memory
184 usage. The views update as the graph is updated similarly to dict-views.
185 The objects `nodes, `edges` and `adj` provide access to data attributes
186 via lookup (e.g. `nodes[n], `edges[u, v]`, `adj[u][v]`) and iteration
187 (e.g. `nodes.items()`, `nodes.data('color')`,
188 `nodes.data('color', default='blue')` and similarly for `edges`)
189 Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`.
190
191 For details on these and other miscellaneous methods, see below.
192
193 **Subclasses (Advanced):**
194
195 The Graph class uses a dict-of-dict-of-dict data structure.
196 The outer dict (node_dict) holds adjacency information keyed by node.
197 The next dict (adjlist_dict) represents the adjacency information and holds
198 edge data keyed by neighbor. The inner dict (edge_attr_dict) represents
199 the edge data and holds edge attribute values keyed by attribute names.
200
201 Each of these three dicts can be replaced in a subclass by a user defined
202 dict-like object. In general, the dict-like features should be
203 maintained but extra features can be added. To replace one of the
204 dicts create a new graph class by changing the class(!) variable
205 holding the factory for that dict-like structure. The variable names are
206 node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory,
207 adjlist_outer_dict_factory, edge_attr_dict_factory and graph_attr_dict_factory.
208
209 node_dict_factory : function, (default: dict)
210 Factory function to be used to create the dict containing node
211 attributes, keyed by node id.
212 It should require no arguments and return a dict-like object
213
214 node_attr_dict_factory: function, (default: dict)
215 Factory function to be used to create the node attribute
216 dict which holds attribute values keyed by attribute name.
217 It should require no arguments and return a dict-like object
218
219 adjlist_outer_dict_factory : function, (default: dict)
220 Factory function to be used to create the outer-most dict
221 in the data structure that holds adjacency info keyed by node.
222 It should require no arguments and return a dict-like object.
223
224 adjlist_inner_dict_factory : function, (default: dict)
225 Factory function to be used to create the adjacency list
226 dict which holds edge data keyed by neighbor.
227 It should require no arguments and return a dict-like object
228
229 edge_attr_dict_factory : function, (default: dict)
230 Factory function to be used to create the edge attribute
231 dict which holds attribute values keyed by attribute name.
232 It should require no arguments and return a dict-like object.
233
234 graph_attr_dict_factory : function, (default: dict)
235 Factory function to be used to create the graph attribute
236 dict which holds attribute values keyed by attribute name.
237 It should require no arguments and return a dict-like object.
238
239 Typically, if your extension doesn't impact the data structure all
240 methods will inherit without issue except: `to_directed/to_undirected`.
241 By default these methods create a DiGraph/Graph class and you probably
242 want them to create your extension of a DiGraph/Graph. To facilitate
243 this we define two class variables that you can set in your subclass.
244
245 to_directed_class : callable, (default: DiGraph or MultiDiGraph)
246 Class to create a new graph structure in the `to_directed` method.
247 If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used.
248
249 to_undirected_class : callable, (default: Graph or MultiGraph)
250 Class to create a new graph structure in the `to_undirected` method.
251 If `None`, a NetworkX class (Graph or MultiGraph) is used.
252
253 Examples
254 --------
255
256 Create a low memory graph class that effectively disallows edge
257 attributes by using a single attribute dict for all edges.
258 This reduces the memory used, but you lose edge attributes.
259
260 >>> class ThinGraph(nx.Graph):
261 ... all_edge_dict = {'weight': 1}
262 ... def single_edge_dict(self):
263 ... return self.all_edge_dict
264 ... edge_attr_dict_factory = single_edge_dict
265 >>> G = ThinGraph()
266 >>> G.add_edge(2, 1)
267 >>> G[2][1]
268 {'weight': 1}
269 >>> G.add_edge(2, 2)
270 >>> G[2][1] is G[2][2]
271 True
272
273 Please see :mod:`~networkx.classes.ordered` for more examples of
274 creating graph subclasses by overwriting the base class `dict` with
275 a dictionary-like object.
276 """
277 node_dict_factory = dict
278 node_attr_dict_factory = dict
279 adjlist_outer_dict_factory = dict
280 adjlist_inner_dict_factory = dict
281 edge_attr_dict_factory = dict
282 graph_attr_dict_factory = dict
283
284 def to_directed_class(self):
285 """Returns the class to use for empty directed copies.
286
287 If you subclass the base classes, use this to designate
288 what directed class to use for `to_directed()` copies.
289 """
290 return nx.DiGraph
291
292 def to_undirected_class(self):
293 """Returns the class to use for empty undirected copies.
294
295 If you subclass the base classes, use this to designate
296 what directed class to use for `to_directed()` copies.
297 """
298 return Graph
299
300 def __init__(self, incoming_graph_data=None, **attr):
301 """Initialize a graph with edges, name, or graph attributes.
302
303 Parameters
304 ----------
305 incoming_graph_data : input graph (optional, default: None)
306 Data to initialize graph. If None (default) an empty
307 graph is created. The data can be an edge list, or any
308 NetworkX graph object. If the corresponding optional Python
309 packages are installed the data can also be a NumPy matrix
310 or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph.
311
312 attr : keyword arguments, optional (default= no attributes)
313 Attributes to add to graph as key=value pairs.
314
315 See Also
316 --------
317 convert
318
319 Examples
320 --------
321 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
322 >>> G = nx.Graph(name='my graph')
323 >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges
324 >>> G = nx.Graph(e)
325
326 Arbitrary graph attribute pairs (key=value) may be assigned
327
328 >>> G = nx.Graph(e, day="Friday")
329 >>> G.graph
330 {'day': 'Friday'}
331
332 """
333 self.graph_attr_dict_factory = self.graph_attr_dict_factory
334 self.node_dict_factory = self.node_dict_factory
335 self.node_attr_dict_factory = self.node_attr_dict_factory
336 self.adjlist_outer_dict_factory = self.adjlist_outer_dict_factory
337 self.adjlist_inner_dict_factory = self.adjlist_inner_dict_factory
338 self.edge_attr_dict_factory = self.edge_attr_dict_factory
339
340 self.graph = self.graph_attr_dict_factory() # dictionary for graph attributes
341 self._node = self.node_dict_factory() # empty node attribute dict
342 self._adj = self.adjlist_outer_dict_factory() # empty adjacency dict
343 # attempt to load graph with data
344 if incoming_graph_data is not None:
345 convert.to_networkx_graph(incoming_graph_data, create_using=self)
346 # load graph attributes (must be after convert)
347 self.graph.update(attr)
348
349 @property
350 def adj(self):
351 """Graph adjacency object holding the neighbors of each node.
352
353 This object is a read-only dict-like structure with node keys
354 and neighbor-dict values. The neighbor-dict is keyed by neighbor
355 to the edge-data-dict. So `G.adj[3][2]['color'] = 'blue'` sets
356 the color of the edge `(3, 2)` to `"blue"`.
357
358 Iterating over G.adj behaves like a dict. Useful idioms include
359 `for nbr, datadict in G.adj[n].items():`.
360
361 The neighbor information is also provided by subscripting the graph.
362 So `for nbr, foovalue in G[node].data('foo', default=1):` works.
363
364 For directed graphs, `G.adj` holds outgoing (successor) info.
365 """
366 return AdjacencyView(self._adj)
367
368 @property
369 def name(self):
370 """String identifier of the graph.
371
372 This graph attribute appears in the attribute dict G.graph
373 keyed by the string `"name"`. as well as an attribute (technically
374 a property) `G.name`. This is entirely user controlled.
375 """
376 return self.graph.get('name', '')
377
378 @name.setter
379 def name(self, s):
380 self.graph['name'] = s
381
382 def __str__(self):
383 """Returns the graph name.
384
385 Returns
386 -------
387 name : string
388 The name of the graph.
389
390 Examples
391 --------
392 >>> G = nx.Graph(name='foo')
393 >>> str(G)
394 'foo'
395 """
396 return self.name
397
398 def __iter__(self):
399 """Iterate over the nodes. Use: 'for n in G'.
400
401 Returns
402 -------
403 niter : iterator
404 An iterator over all nodes in the graph.
405
406 Examples
407 --------
408 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
409 >>> [n for n in G]
410 [0, 1, 2, 3]
411 >>> list(G)
412 [0, 1, 2, 3]
413 """
414 return iter(self._node)
415
416 def __contains__(self, n):
417 """Returns True if n is a node, False otherwise. Use: 'n in G'.
418
419 Examples
420 --------
421 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
422 >>> 1 in G
423 True
424 """
425 try:
426 return n in self._node
427 except TypeError:
428 return False
429
430 def __len__(self):
431 """Returns the number of nodes in the graph. Use: 'len(G)'.
432
433 Returns
434 -------
435 nnodes : int
436 The number of nodes in the graph.
437
438 See Also
439 --------
440 number_of_nodes, order which are identical
441
442 Examples
443 --------
444 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
445 >>> len(G)
446 4
447
448 """
449 return len(self._node)
450
451 def __getitem__(self, n):
452 """Returns a dict of neighbors of node n. Use: 'G[n]'.
453
454 Parameters
455 ----------
456 n : node
457 A node in the graph.
458
459 Returns
460 -------
461 adj_dict : dictionary
462 The adjacency dictionary for nodes connected to n.
463
464 Notes
465 -----
466 G[n] is the same as G.adj[n] and similar to G.neighbors(n)
467 (which is an iterator over G.adj[n])
468
469 Examples
470 --------
471 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
472 >>> G[0]
473 AtlasView({1: {}})
474 """
475 return self.adj[n]
476
477 def add_node(self, node_for_adding, **attr):
478 """Add a single node `node_for_adding` and update node attributes.
479
480 Parameters
481 ----------
482 node_for_adding : node
483 A node can be any hashable Python object except None.
484 attr : keyword arguments, optional
485 Set or change node attributes using key=value.
486
487 See Also
488 --------
489 add_nodes_from
490
491 Examples
492 --------
493 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
494 >>> G.add_node(1)
495 >>> G.add_node('Hello')
496 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
497 >>> G.add_node(K3)
498 >>> G.number_of_nodes()
499 3
500
501 Use keywords set/change node attributes:
502
503 >>> G.add_node(1, size=10)
504 >>> G.add_node(3, weight=0.4, UTM=('13S', 382871, 3972649))
505
506 Notes
507 -----
508 A hashable object is one that can be used as a key in a Python
509 dictionary. This includes strings, numbers, tuples of strings
510 and numbers, etc.
511
512 On many platforms hashable items also include mutables such as
513 NetworkX Graphs, though one should be careful that the hash
514 doesn't change on mutables.
515 """
516 if node_for_adding not in self._node:
517 self._adj[node_for_adding] = self.adjlist_inner_dict_factory()
518 attr_dict = self._node[node_for_adding] = self.node_attr_dict_factory()
519 attr_dict.update(attr)
520 else: # update attr even if node already exists
521 self._node[node_for_adding].update(attr)
522
523 def add_nodes_from(self, nodes_for_adding, **attr):
524 """Add multiple nodes.
525
526 Parameters
527 ----------
528 nodes_for_adding : iterable container
529 A container of nodes (list, dict, set, etc.).
530 OR
531 A container of (node, attribute dict) tuples.
532 Node attributes are updated using the attribute dict.
533 attr : keyword arguments, optional (default= no attributes)
534 Update attributes for all nodes in nodes.
535 Node attributes specified in nodes as a tuple take
536 precedence over attributes specified via keyword arguments.
537
538 See Also
539 --------
540 add_node
541
542 Examples
543 --------
544 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
545 >>> G.add_nodes_from('Hello')
546 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
547 >>> G.add_nodes_from(K3)
548 >>> sorted(G.nodes(), key=str)
549 [0, 1, 2, 'H', 'e', 'l', 'o']
550
551 Use keywords to update specific node attributes for every node.
552
553 >>> G.add_nodes_from([1, 2], size=10)
554 >>> G.add_nodes_from([3, 4], weight=0.4)
555
556 Use (node, attrdict) tuples to update attributes for specific nodes.
557
558 >>> G.add_nodes_from([(1, dict(size=11)), (2, {'color':'blue'})])
559 >>> G.nodes[1]['size']
560 11
561 >>> H = nx.Graph()
562 >>> H.add_nodes_from(G.nodes(data=True))
563 >>> H.nodes[1]['size']
564 11
565
566 """
567 for n in nodes_for_adding:
568 # keep all this inside try/except because
569 # CPython throws TypeError on n not in self._node,
570 # while pre-2.7.5 ironpython throws on self._adj[n]
571 try:
572 if n not in self._node:
573 self._adj[n] = self.adjlist_inner_dict_factory()
574 attr_dict = self._node[n] = self.node_attr_dict_factory()
575 attr_dict.update(attr)
576 else:
577 self._node[n].update(attr)
578 except TypeError:
579 nn, ndict = n
580 if nn not in self._node:
581 self._adj[nn] = self.adjlist_inner_dict_factory()
582 newdict = attr.copy()
583 newdict.update(ndict)
584 attr_dict = self._node[nn] = self.node_attr_dict_factory()
585 attr_dict.update(newdict)
586 else:
587 olddict = self._node[nn]
588 olddict.update(attr)
589 olddict.update(ndict)
590
591 def remove_node(self, n):
592 """Remove node n.
593
594 Removes the node n and all adjacent edges.
595 Attempting to remove a non-existent node will raise an exception.
596
597 Parameters
598 ----------
599 n : node
600 A node in the graph
601
602 Raises
603 -------
604 NetworkXError
605 If n is not in the graph.
606
607 See Also
608 --------
609 remove_nodes_from
610
611 Examples
612 --------
613 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
614 >>> list(G.edges)
615 [(0, 1), (1, 2)]
616 >>> G.remove_node(1)
617 >>> list(G.edges)
618 []
619
620 """
621 adj = self._adj
622 try:
623 nbrs = list(adj[n]) # list handles self-loops (allows mutation)
624 del self._node[n]
625 except KeyError: # NetworkXError if n not in self
626 raise NetworkXError("The node %s is not in the graph." % (n,))
627 for u in nbrs:
628 del adj[u][n] # remove all edges n-u in graph
629 del adj[n] # now remove node
630
631 def remove_nodes_from(self, nodes):
632 """Remove multiple nodes.
633
634 Parameters
635 ----------
636 nodes : iterable container
637 A container of nodes (list, dict, set, etc.). If a node
638 in the container is not in the graph it is silently
639 ignored.
640
641 See Also
642 --------
643 remove_node
644
645 Examples
646 --------
647 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
648 >>> e = list(G.nodes)
649 >>> e
650 [0, 1, 2]
651 >>> G.remove_nodes_from(e)
652 >>> list(G.nodes)
653 []
654
655 """
656 adj = self._adj
657 for n in nodes:
658 try:
659 del self._node[n]
660 for u in list(adj[n]): # list handles self-loops
661 del adj[u][n] # (allows mutation of dict in loop)
662 del adj[n]
663 except KeyError:
664 pass
665
666 @property
667 def nodes(self):
668 """A NodeView of the Graph as G.nodes or G.nodes().
669
670 Can be used as `G.nodes` for data lookup and for set-like operations.
671 Can also be used as `G.nodes(data='color', default=None)` to return a
672 NodeDataView which reports specific node data but no set operations.
673 It presents a dict-like interface as well with `G.nodes.items()`
674 iterating over `(node, nodedata)` 2-tuples and `G.nodes[3]['foo']`
675 providing the value of the `foo` attribute for node `3`. In addition,
676 a view `G.nodes.data('foo')` provides a dict-like interface to the
677 `foo` attribute of each node. `G.nodes.data('foo', default=1)`
678 provides a default for nodes that do not have attribute `foo`.
679
680 Parameters
681 ----------
682 data : string or bool, optional (default=False)
683 The node attribute returned in 2-tuple (n, ddict[data]).
684 If True, return entire node attribute dict as (n, ddict).
685 If False, return just the nodes n.
686
687 default : value, optional (default=None)
688 Value used for nodes that don't have the requested attribute.
689 Only relevant if data is not True or False.
690
691 Returns
692 -------
693 NodeView
694 Allows set-like operations over the nodes as well as node
695 attribute dict lookup and calling to get a NodeDataView.
696 A NodeDataView iterates over `(n, data)` and has no set operations.
697 A NodeView iterates over `n` and includes set operations.
698
699 When called, if data is False, an iterator over nodes.
700 Otherwise an iterator of 2-tuples (node, attribute value)
701 where the attribute is specified in `data`.
702 If data is True then the attribute becomes the
703 entire data dictionary.
704
705 Notes
706 -----
707 If your node data is not needed, it is simpler and equivalent
708 to use the expression ``for n in G``, or ``list(G)``.
709
710 Examples
711 --------
712 There are two simple ways of getting a list of all nodes in the graph:
713
714 >>> G = nx.path_graph(3)
715 >>> list(G.nodes)
716 [0, 1, 2]
717 >>> list(G)
718 [0, 1, 2]
719
720 To get the node data along with the nodes:
721
722 >>> G.add_node(1, time='5pm')
723 >>> G.nodes[0]['foo'] = 'bar'
724 >>> list(G.nodes(data=True))
725 [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})]
726 >>> list(G.nodes.data())
727 [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})]
728
729 >>> list(G.nodes(data='foo'))
730 [(0, 'bar'), (1, None), (2, None)]
731 >>> list(G.nodes.data('foo'))
732 [(0, 'bar'), (1, None), (2, None)]
733
734 >>> list(G.nodes(data='time'))
735 [(0, None), (1, '5pm'), (2, None)]
736 >>> list(G.nodes.data('time'))
737 [(0, None), (1, '5pm'), (2, None)]
738
739 >>> list(G.nodes(data='time', default='Not Available'))
740 [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')]
741 >>> list(G.nodes.data('time', default='Not Available'))
742 [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')]
743
744 If some of your nodes have an attribute and the rest are assumed
745 to have a default attribute value you can create a dictionary
746 from node/attribute pairs using the `default` keyword argument
747 to guarantee the value is never None::
748
749 >>> G = nx.Graph()
750 >>> G.add_node(0)
751 >>> G.add_node(1, weight=2)
752 >>> G.add_node(2, weight=3)
753 >>> dict(G.nodes(data='weight', default=1))
754 {0: 1, 1: 2, 2: 3}
755
756 """
757 nodes = NodeView(self)
758 # Lazy View creation: overload the (class) property on the instance
759 # Then future G.nodes use the existing View
760 # setattr doesn't work because attribute already exists
761 self.__dict__['nodes'] = nodes
762 return nodes
763
764 def number_of_nodes(self):
765 """Returns the number of nodes in the graph.
766
767 Returns
768 -------
769 nnodes : int
770 The number of nodes in the graph.
771
772 See Also
773 --------
774 order, __len__ which are identical
775
776 Examples
777 --------
778 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
779 >>> G.number_of_nodes()
780 3
781 """
782 return len(self._node)
783
784 def order(self):
785 """Returns the number of nodes in the graph.
786
787 Returns
788 -------
789 nnodes : int
790 The number of nodes in the graph.
791
792 See Also
793 --------
794 number_of_nodes, __len__ which are identical
795
796 Examples
797 --------
798 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
799 >>> G.order()
800 3
801 """
802 return len(self._node)
803
804 def has_node(self, n):
805 """Returns True if the graph contains the node n.
806
807 Identical to `n in G`
808
809 Parameters
810 ----------
811 n : node
812
813 Examples
814 --------
815 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
816 >>> G.has_node(0)
817 True
818
819 It is more readable and simpler to use
820
821 >>> 0 in G
822 True
823
824 """
825 try:
826 return n in self._node
827 except TypeError:
828 return False
829
830 def add_edge(self, u_of_edge, v_of_edge, **attr):
831 """Add an edge between u and v.
832
833 The nodes u and v will be automatically added if they are
834 not already in the graph.
835
836 Edge attributes can be specified with keywords or by directly
837 accessing the edge's attribute dictionary. See examples below.
838
839 Parameters
840 ----------
841 u, v : nodes
842 Nodes can be, for example, strings or numbers.
843 Nodes must be hashable (and not None) Python objects.
844 attr : keyword arguments, optional
845 Edge data (or labels or objects) can be assigned using
846 keyword arguments.
847
848 See Also
849 --------
850 add_edges_from : add a collection of edges
851
852 Notes
853 -----
854 Adding an edge that already exists updates the edge data.
855
856 Many NetworkX algorithms designed for weighted graphs use
857 an edge attribute (by default `weight`) to hold a numerical value.
858
859 Examples
860 --------
861 The following all add the edge e=(1, 2) to graph G:
862
863 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
864 >>> e = (1, 2)
865 >>> G.add_edge(1, 2) # explicit two-node form
866 >>> G.add_edge(*e) # single edge as tuple of two nodes
867 >>> G.add_edges_from([(1, 2)]) # add edges from iterable container
868
869 Associate data to edges using keywords:
870
871 >>> G.add_edge(1, 2, weight=3)
872 >>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7)
873
874 For non-string attribute keys, use subscript notation.
875
876 >>> G.add_edge(1, 2)
877 >>> G[1][2].update({0: 5})
878 >>> G.edges[1, 2].update({0: 5})
879 """
880 u, v = u_of_edge, v_of_edge
881 # add nodes
882 if u not in self._node:
883 self._adj[u] = self.adjlist_inner_dict_factory()
884 self._node[u] = self.node_attr_dict_factory()
885 if v not in self._node:
886 self._adj[v] = self.adjlist_inner_dict_factory()
887 self._node[v] = self.node_attr_dict_factory()
888 # add the edge
889 datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
890 datadict.update(attr)
891 self._adj[u][v] = datadict
892 self._adj[v][u] = datadict
893
894 def add_edges_from(self, ebunch_to_add, **attr):
895 """Add all the edges in ebunch_to_add.
896
897 Parameters
898 ----------
899 ebunch_to_add : container of edges
900 Each edge given in the container will be added to the
901 graph. The edges must be given as as 2-tuples (u, v) or
902 3-tuples (u, v, d) where d is a dictionary containing edge data.
903 attr : keyword arguments, optional
904 Edge data (or labels or objects) can be assigned using
905 keyword arguments.
906
907 See Also
908 --------
909 add_edge : add a single edge
910 add_weighted_edges_from : convenient way to add weighted edges
911
912 Notes
913 -----
914 Adding the same edge twice has no effect but any edge data
915 will be updated when each duplicate edge is added.
916
917 Edge attributes specified in an ebunch take precedence over
918 attributes specified via keyword arguments.
919
920 Examples
921 --------
922 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
923 >>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples
924 >>> e = zip(range(0, 3), range(1, 4))
925 >>> G.add_edges_from(e) # Add the path graph 0-1-2-3
926
927 Associate data to edges
928
929 >>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
930 >>> G.add_edges_from([(3, 4), (1, 4)], label='WN2898')
931 """
932 for e in ebunch_to_add:
933 ne = len(e)
934 if ne == 3:
935 u, v, dd = e
936 elif ne == 2:
937 u, v = e
938 dd = {} # doesn't need edge_attr_dict_factory
939 else:
940 raise NetworkXError(
941 "Edge tuple %s must be a 2-tuple or 3-tuple." % (e,))
942 if u not in self._node:
943 self._adj[u] = self.adjlist_inner_dict_factory()
944 self._node[u] = self.node_attr_dict_factory()
945 if v not in self._node:
946 self._adj[v] = self.adjlist_inner_dict_factory()
947 self._node[v] = self.node_attr_dict_factory()
948 datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
949 datadict.update(attr)
950 datadict.update(dd)
951 self._adj[u][v] = datadict
952 self._adj[v][u] = datadict
953
954 def add_weighted_edges_from(self, ebunch_to_add, weight='weight', **attr):
955 """Add weighted edges in `ebunch_to_add` with specified weight attr
956
957 Parameters
958 ----------
959 ebunch_to_add : container of edges
960 Each edge given in the list or container will be added
961 to the graph. The edges must be given as 3-tuples (u, v, w)
962 where w is a number.
963 weight : string, optional (default= 'weight')
964 The attribute name for the edge weights to be added.
965 attr : keyword arguments, optional (default= no attributes)
966 Edge attributes to add/update for all edges.
967
968 See Also
969 --------
970 add_edge : add a single edge
971 add_edges_from : add multiple edges
972
973 Notes
974 -----
975 Adding the same edge twice for Graph/DiGraph simply updates
976 the edge data. For MultiGraph/MultiDiGraph, duplicate edges
977 are stored.
978
979 Examples
980 --------
981 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
982 >>> G.add_weighted_edges_from([(0, 1, 3.0), (1, 2, 7.5)])
983 """
984 self.add_edges_from(((u, v, {weight: d}) for u, v, d in ebunch_to_add),
985 **attr)
986
987 def remove_edge(self, u, v):
988 """Remove the edge between u and v.
989
990 Parameters
991 ----------
992 u, v : nodes
993 Remove the edge between nodes u and v.
994
995 Raises
996 ------
997 NetworkXError
998 If there is not an edge between u and v.
999
1000 See Also
1001 --------
1002 remove_edges_from : remove a collection of edges
1003
1004 Examples
1005 --------
1006 >>> G = nx.path_graph(4) # or DiGraph, etc
1007 >>> G.remove_edge(0, 1)
1008 >>> e = (1, 2)
1009 >>> G.remove_edge(*e) # unpacks e from an edge tuple
1010 >>> e = (2, 3, {'weight':7}) # an edge with attribute data
1011 >>> G.remove_edge(*e[:2]) # select first part of edge tuple
1012 """
1013 try:
1014 del self._adj[u][v]
1015 if u != v: # self-loop needs only one entry removed
1016 del self._adj[v][u]
1017 except KeyError:
1018 raise NetworkXError("The edge %s-%s is not in the graph" % (u, v))
1019
1020 def remove_edges_from(self, ebunch):
1021 """Remove all edges specified in ebunch.
1022
1023 Parameters
1024 ----------
1025 ebunch: list or container of edge tuples
1026 Each edge given in the list or container will be removed
1027 from the graph. The edges can be:
1028
1029 - 2-tuples (u, v) edge between u and v.
1030 - 3-tuples (u, v, k) where k is ignored.
1031
1032 See Also
1033 --------
1034 remove_edge : remove a single edge
1035
1036 Notes
1037 -----
1038 Will fail silently if an edge in ebunch is not in the graph.
1039
1040 Examples
1041 --------
1042 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1043 >>> ebunch=[(1, 2), (2, 3)]
1044 >>> G.remove_edges_from(ebunch)
1045 """
1046 adj = self._adj
1047 for e in ebunch:
1048 u, v = e[:2] # ignore edge data if present
1049 if u in adj and v in adj[u]:
1050 del adj[u][v]
1051 if u != v: # self loop needs only one entry removed
1052 del adj[v][u]
1053
1054 def update(self, edges=None, nodes=None):
1055 """Update the graph using nodes/edges/graphs as input.
1056
1057 Like dict.update, this method takes a graph as input, adding the
1058 graph's nodes and edges to this graph. It can also take two inputs:
1059 edges and nodes. Finally it can take either edges or nodes.
1060 To specify only nodes the keyword `nodes` must be used.
1061
1062 The collections of edges and nodes are treated similarly to
1063 the add_edges_from/add_nodes_from methods. When iterated, they
1064 should yield 2-tuples (u, v) or 3-tuples (u, v, datadict).
1065
1066 Parameters
1067 ----------
1068 edges : Graph object, collection of edges, or None
1069 The first parameter can be a graph or some edges. If it has
1070 attributes `nodes` and `edges`, then it is taken to be a
1071 Graph-like object and those attributes are used as collections
1072 of nodes and edges to be added to the graph.
1073 If the first parameter does not have those attributes, it is
1074 treated as a collection of edges and added to the graph.
1075 If the first argument is None, no edges are added.
1076 nodes : collection of nodes, or None
1077 The second parameter is treated as a collection of nodes
1078 to be added to the graph unless it is None.
1079 If `edges is None` and `nodes is None` an exception is raised.
1080 If the first parameter is a Graph, then `nodes` is ignored.
1081
1082 Examples
1083 --------
1084 >>> G = nx.path_graph(5)
1085 >>> G.update(nx.complete_graph(range(4,10)))
1086 >>> from itertools import combinations
1087 >>> edges = ((u, v, {'power': u * v})
1088 ... for u, v in combinations(range(10, 20), 2)
1089 ... if u * v < 225)
1090 >>> nodes = [1000] # for singleton, use a container
1091 >>> G.update(edges, nodes)
1092
1093 Notes
1094 -----
1095 It you want to update the graph using an adjacency structure
1096 it is straightforward to obtain the edges/nodes from adjacency.
1097 The following examples provide common cases, your adjacency may
1098 be slightly different and require tweaks of these examples.
1099
1100 >>> # dict-of-set/list/tuple
1101 >>> adj = {1: {2, 3}, 2: {1, 3}, 3: {1, 2}}
1102 >>> e = [(u, v) for u, nbrs in adj.items() for v in nbrs]
1103 >>> G.update(edges=e, nodes=adj)
1104
1105 >>> DG = nx.DiGraph()
1106 >>> # dict-of-dict-of-attribute
1107 >>> adj = {1: {2: 1.3, 3: 0.7}, 2: {1: 1.4}, 3: {1: 0.7}}
1108 >>> e = [(u, v, {'weight': d}) for u, nbrs in adj.items()
1109 ... for v, d in nbrs.items()]
1110 >>> DG.update(edges=e, nodes=adj)
1111
1112 >>> # dict-of-dict-of-dict
1113 >>> adj = {1: {2: {'weight': 1.3}, 3: {'color': 0.7, 'weight':1.2}}}
1114 >>> e = [(u, v, {'weight': d}) for u, nbrs in adj.items()
1115 ... for v, d in nbrs.items()]
1116 >>> DG.update(edges=e, nodes=adj)
1117
1118 >>> # predecessor adjacency (dict-of-set)
1119 >>> pred = {1: {2, 3}, 2: {3}, 3: {3}}
1120 >>> e = [(v, u) for u, nbrs in pred.items() for v in nbrs]
1121
1122 >>> # MultiGraph dict-of-dict-of-dict-of-attribute
1123 >>> MDG = nx.MultiDiGraph()
1124 >>> adj = {1: {2: {0: {'weight': 1.3}, 1: {'weight': 1.2}}},
1125 ... 3: {2: {0: {'weight': 0.7}}}}
1126 >>> e = [(u, v, ekey, d) for u, nbrs in adj.items()
1127 ... for v, keydict in nbrs.items()
1128 ... for ekey, d in keydict.items()]
1129 >>> MDG.update(edges=e)
1130
1131 See Also
1132 --------
1133 add_edges_from: add multiple edges to a graph
1134 add_nodes_from: add multiple nodes to a graph
1135 """
1136 if edges is not None:
1137 if nodes is not None:
1138 self.add_nodes_from(nodes)
1139 self.add_edges_from(edges)
1140 else:
1141 # check if edges is a Graph object
1142 try:
1143 graph_nodes = edges.nodes
1144 graph_edges = edges.edges
1145 except AttributeError:
1146 # edge not Graph-like
1147 self.add_edges_from(edges)
1148 else: # edges is Graph-like
1149 self.add_nodes_from(graph_nodes.data())
1150 self.add_edges_from(graph_edges.data())
1151 self.graph.update(edges.graph)
1152 elif nodes is not None:
1153 self.add_nodes_from(nodes)
1154 else:
1155 raise NetworkXError("update needs nodes or edges input")
1156
1157 def has_edge(self, u, v):
1158 """Returns True if the edge (u, v) is in the graph.
1159
1160 This is the same as `v in G[u]` without KeyError exceptions.
1161
1162 Parameters
1163 ----------
1164 u, v : nodes
1165 Nodes can be, for example, strings or numbers.
1166 Nodes must be hashable (and not None) Python objects.
1167
1168 Returns
1169 -------
1170 edge_ind : bool
1171 True if edge is in the graph, False otherwise.
1172
1173 Examples
1174 --------
1175 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1176 >>> G.has_edge(0, 1) # using two nodes
1177 True
1178 >>> e = (0, 1)
1179 >>> G.has_edge(*e) # e is a 2-tuple (u, v)
1180 True
1181 >>> e = (0, 1, {'weight':7})
1182 >>> G.has_edge(*e[:2]) # e is a 3-tuple (u, v, data_dictionary)
1183 True
1184
1185 The following syntax are equivalent:
1186
1187 >>> G.has_edge(0, 1)
1188 True
1189 >>> 1 in G[0] # though this gives KeyError if 0 not in G
1190 True
1191
1192 """
1193 try:
1194 return v in self._adj[u]
1195 except KeyError:
1196 return False
1197
1198 def neighbors(self, n):
1199 """Returns an iterator over all neighbors of node n.
1200
1201 This is identical to `iter(G[n])`
1202
1203 Parameters
1204 ----------
1205 n : node
1206 A node in the graph
1207
1208 Returns
1209 -------
1210 neighbors : iterator
1211 An iterator over all neighbors of node n
1212
1213 Raises
1214 ------
1215 NetworkXError
1216 If the node n is not in the graph.
1217
1218 Examples
1219 --------
1220 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1221 >>> [n for n in G.neighbors(0)]
1222 [1]
1223
1224 Notes
1225 -----
1226 It is usually more convenient (and faster) to access the
1227 adjacency dictionary as ``G[n]``:
1228
1229 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1230 >>> G.add_edge('a', 'b', weight=7)
1231 >>> G['a']
1232 AtlasView({'b': {'weight': 7}})
1233 >>> G = nx.path_graph(4)
1234 >>> [n for n in G[0]]
1235 [1]
1236 """
1237 try:
1238 return iter(self._adj[n])
1239 except KeyError:
1240 raise NetworkXError("The node %s is not in the graph." % (n,))
1241
1242 @property
1243 def edges(self):
1244 """An EdgeView of the Graph as G.edges or G.edges().
1245
1246 edges(self, nbunch=None, data=False, default=None)
1247
1248 The EdgeView provides set-like operations on the edge-tuples
1249 as well as edge attribute lookup. When called, it also provides
1250 an EdgeDataView object which allows control of access to edge
1251 attributes (but does not provide set-like operations).
1252 Hence, `G.edges[u, v]['color']` provides the value of the color
1253 attribute for edge `(u, v)` while
1254 `for (u, v, c) in G.edges.data('color', default='red'):`
1255 iterates through all the edges yielding the color attribute
1256 with default `'red'` if no color attribute exists.
1257
1258 Parameters
1259 ----------
1260 nbunch : single node, container, or all nodes (default= all nodes)
1261 The view will only report edges incident to these nodes.
1262 data : string or bool, optional (default=False)
1263 The edge attribute returned in 3-tuple (u, v, ddict[data]).
1264 If True, return edge attribute dict in 3-tuple (u, v, ddict).
1265 If False, return 2-tuple (u, v).
1266 default : value, optional (default=None)
1267 Value used for edges that don't have the requested attribute.
1268 Only relevant if data is not True or False.
1269
1270 Returns
1271 -------
1272 edges : EdgeView
1273 A view of edge attributes, usually it iterates over (u, v)
1274 or (u, v, d) tuples of edges, but can also be used for
1275 attribute lookup as `edges[u, v]['foo']`.
1276
1277 Notes
1278 -----
1279 Nodes in nbunch that are not in the graph will be (quietly) ignored.
1280 For directed graphs this returns the out-edges.
1281
1282 Examples
1283 --------
1284 >>> G = nx.path_graph(3) # or MultiGraph, etc
1285 >>> G.add_edge(2, 3, weight=5)
1286 >>> [e for e in G.edges]
1287 [(0, 1), (1, 2), (2, 3)]
1288 >>> G.edges.data() # default data is {} (empty dict)
1289 EdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})])
1290 >>> G.edges.data('weight', default=1)
1291 EdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)])
1292 >>> G.edges([0, 3]) # only edges incident to these nodes
1293 EdgeDataView([(0, 1), (3, 2)])
1294 >>> G.edges(0) # only edges incident to a single node (use G.adj[0]?)
1295 EdgeDataView([(0, 1)])
1296 """
1297 return EdgeView(self)
1298
1299 def get_edge_data(self, u, v, default=None):
1300 """Returns the attribute dictionary associated with edge (u, v).
1301
1302 This is identical to `G[u][v]` except the default is returned
1303 instead of an exception if the edge doesn't exist.
1304
1305 Parameters
1306 ----------
1307 u, v : nodes
1308 default: any Python object (default=None)
1309 Value to return if the edge (u, v) is not found.
1310
1311 Returns
1312 -------
1313 edge_dict : dictionary
1314 The edge attribute dictionary.
1315
1316 Examples
1317 --------
1318 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1319 >>> G[0][1]
1320 {}
1321
1322 Warning: Assigning to `G[u][v]` is not permitted.
1323 But it is safe to assign attributes `G[u][v]['foo']`
1324
1325 >>> G[0][1]['weight'] = 7
1326 >>> G[0][1]['weight']
1327 7
1328 >>> G[1][0]['weight']
1329 7
1330
1331 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1332 >>> G.get_edge_data(0, 1) # default edge data is {}
1333 {}
1334 >>> e = (0, 1)
1335 >>> G.get_edge_data(*e) # tuple form
1336 {}
1337 >>> G.get_edge_data('a', 'b', default=0) # edge not in graph, return 0
1338 0
1339 """
1340 try:
1341 return self._adj[u][v]
1342 except KeyError:
1343 return default
1344
1345 def adjacency(self):
1346 """Returns an iterator over (node, adjacency dict) tuples for all nodes.
1347
1348 For directed graphs, only outgoing neighbors/adjacencies are included.
1349
1350 Returns
1351 -------
1352 adj_iter : iterator
1353 An iterator over (node, adjacency dictionary) for all nodes in
1354 the graph.
1355
1356 Examples
1357 --------
1358 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1359 >>> [(n, nbrdict) for n, nbrdict in G.adjacency()]
1360 [(0, {1: {}}), (1, {0: {}, 2: {}}), (2, {1: {}, 3: {}}), (3, {2: {}})]
1361
1362 """
1363 return iter(self._adj.items())
1364
1365 @property
1366 def degree(self):
1367 """A DegreeView for the Graph as G.degree or G.degree().
1368
1369 The node degree is the number of edges adjacent to the node.
1370 The weighted node degree is the sum of the edge weights for
1371 edges incident to that node.
1372
1373 This object provides an iterator for (node, degree) as well as
1374 lookup for the degree for a single node.
1375
1376 Parameters
1377 ----------
1378 nbunch : single node, container, or all nodes (default= all nodes)
1379 The view will only report edges incident to these nodes.
1380
1381 weight : string or None, optional (default=None)
1382 The name of an edge attribute that holds the numerical value used
1383 as a weight. If None, then each edge has weight 1.
1384 The degree is the sum of the edge weights adjacent to the node.
1385
1386 Returns
1387 -------
1388 If a single node is requested
1389 deg : int
1390 Degree of the node
1391
1392 OR if multiple nodes are requested
1393 nd_view : A DegreeView object capable of iterating (node, degree) pairs
1394
1395 Examples
1396 --------
1397 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1398 >>> G.degree[0] # node 0 has degree 1
1399 1
1400 >>> list(G.degree([0, 1, 2]))
1401 [(0, 1), (1, 2), (2, 2)]
1402 """
1403 return DegreeView(self)
1404
1405 def clear(self):
1406 """Remove all nodes and edges from the graph.
1407
1408 This also removes the name, and all graph, node, and edge attributes.
1409
1410 Examples
1411 --------
1412 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1413 >>> G.clear()
1414 >>> list(G.nodes)
1415 []
1416 >>> list(G.edges)
1417 []
1418
1419 """
1420 self._adj.clear()
1421 self._node.clear()
1422 self.graph.clear()
1423
1424 def is_multigraph(self):
1425 """Returns True if graph is a multigraph, False otherwise."""
1426 return False
1427
1428 def is_directed(self):
1429 """Returns True if graph is directed, False otherwise."""
1430 return False
1431
1432 def copy(self, as_view=False):
1433 """Returns a copy of the graph.
1434
1435 The copy method by default returns an independent shallow copy
1436 of the graph and attributes. That is, if an attribute is a
1437 container, that container is shared by the original an the copy.
1438 Use Python's `copy.deepcopy` for new containers.
1439
1440 If `as_view` is True then a view is returned instead of a copy.
1441
1442 Notes
1443 -----
1444 All copies reproduce the graph structure, but data attributes
1445 may be handled in different ways. There are four types of copies
1446 of a graph that people might want.
1447
1448 Deepcopy -- A "deepcopy" copies the graph structure as well as
1449 all data attributes and any objects they might contain.
1450 The entire graph object is new so that changes in the copy
1451 do not affect the original object. (see Python's copy.deepcopy)
1452
1453 Data Reference (Shallow) -- For a shallow copy the graph structure
1454 is copied but the edge, node and graph attribute dicts are
1455 references to those in the original graph. This saves
1456 time and memory but could cause confusion if you change an attribute
1457 in one graph and it changes the attribute in the other.
1458 NetworkX does not provide this level of shallow copy.
1459
1460 Independent Shallow -- This copy creates new independent attribute
1461 dicts and then does a shallow copy of the attributes. That is, any
1462 attributes that are containers are shared between the new graph
1463 and the original. This is exactly what `dict.copy()` provides.
1464 You can obtain this style copy using:
1465
1466 >>> G = nx.path_graph(5)
1467 >>> H = G.copy()
1468 >>> H = G.copy(as_view=False)
1469 >>> H = nx.Graph(G)
1470 >>> H = G.__class__(G)
1471
1472 Fresh Data -- For fresh data, the graph structure is copied while
1473 new empty data attribute dicts are created. The resulting graph
1474 is independent of the original and it has no edge, node or graph
1475 attributes. Fresh copies are not enabled. Instead use:
1476
1477 >>> H = G.__class__()
1478 >>> H.add_nodes_from(G)
1479 >>> H.add_edges_from(G.edges)
1480
1481 View -- Inspired by dict-views, graph-views act like read-only
1482 versions of the original graph, providing a copy of the original
1483 structure without requiring any memory for copying the information.
1484
1485 See the Python copy module for more information on shallow
1486 and deep copies, https://docs.python.org/2/library/copy.html.
1487
1488 Parameters
1489 ----------
1490 as_view : bool, optional (default=False)
1491 If True, the returned graph-view provides a read-only view
1492 of the original graph without actually copying any data.
1493
1494 Returns
1495 -------
1496 G : Graph
1497 A copy of the graph.
1498
1499 See Also
1500 --------
1501 to_directed: return a directed copy of the graph.
1502
1503 Examples
1504 --------
1505 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1506 >>> H = G.copy()
1507
1508 """
1509 if as_view is True:
1510 return nx.graphviews.generic_graph_view(self)
1511 G = self.__class__()
1512 G.graph.update(self.graph)
1513 G.add_nodes_from((n, d.copy()) for n, d in self._node.items())
1514 G.add_edges_from((u, v, datadict.copy())
1515 for u, nbrs in self._adj.items()
1516 for v, datadict in nbrs.items())
1517 return G
1518
1519 def to_directed(self, as_view=False):
1520 """Returns a directed representation of the graph.
1521
1522 Returns
1523 -------
1524 G : DiGraph
1525 A directed graph with the same name, same nodes, and with
1526 each edge (u, v, data) replaced by two directed edges
1527 (u, v, data) and (v, u, data).
1528
1529 Notes
1530 -----
1531 This returns a "deepcopy" of the edge, node, and
1532 graph attributes which attempts to completely copy
1533 all of the data and references.
1534
1535 This is in contrast to the similar D=DiGraph(G) which returns a
1536 shallow copy of the data.
1537
1538 See the Python copy module for more information on shallow
1539 and deep copies, https://docs.python.org/2/library/copy.html.
1540
1541 Warning: If you have subclassed Graph to use dict-like objects
1542 in the data structure, those changes do not transfer to the
1543 DiGraph created by this method.
1544
1545 Examples
1546 --------
1547 >>> G = nx.Graph() # or MultiGraph, etc
1548 >>> G.add_edge(0, 1)
1549 >>> H = G.to_directed()
1550 >>> list(H.edges)
1551 [(0, 1), (1, 0)]
1552
1553 If already directed, return a (deep) copy
1554
1555 >>> G = nx.DiGraph() # or MultiDiGraph, etc
1556 >>> G.add_edge(0, 1)
1557 >>> H = G.to_directed()
1558 >>> list(H.edges)
1559 [(0, 1)]
1560 """
1561 graph_class = self.to_directed_class()
1562 if as_view is True:
1563 return nx.graphviews.generic_graph_view(self, graph_class)
1564 # deepcopy when not a view
1565 G = graph_class()
1566 G.graph.update(deepcopy(self.graph))
1567 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1568 G.add_edges_from((u, v, deepcopy(data))
1569 for u, nbrs in self._adj.items()
1570 for v, data in nbrs.items())
1571 return G
1572
1573 def to_undirected(self, as_view=False):
1574 """Returns an undirected copy of the graph.
1575
1576 Parameters
1577 ----------
1578 as_view : bool (optional, default=False)
1579 If True return a view of the original undirected graph.
1580
1581 Returns
1582 -------
1583 G : Graph/MultiGraph
1584 A deepcopy of the graph.
1585
1586 See Also
1587 --------
1588 Graph, copy, add_edge, add_edges_from
1589
1590 Notes
1591 -----
1592 This returns a "deepcopy" of the edge, node, and
1593 graph attributes which attempts to completely copy
1594 all of the data and references.
1595
1596 This is in contrast to the similar `G = nx.DiGraph(D)` which returns a
1597 shallow copy of the data.
1598
1599 See the Python copy module for more information on shallow
1600 and deep copies, https://docs.python.org/2/library/copy.html.
1601
1602 Warning: If you have subclassed DiGraph to use dict-like objects
1603 in the data structure, those changes do not transfer to the
1604 Graph created by this method.
1605
1606 Examples
1607 --------
1608 >>> G = nx.path_graph(2) # or MultiGraph, etc
1609 >>> H = G.to_directed()
1610 >>> list(H.edges)
1611 [(0, 1), (1, 0)]
1612 >>> G2 = H.to_undirected()
1613 >>> list(G2.edges)
1614 [(0, 1)]
1615 """
1616 graph_class = self.to_undirected_class()
1617 if as_view is True:
1618 return nx.graphviews.generic_graph_view(self, graph_class)
1619 # deepcopy when not a view
1620 G = graph_class()
1621 G.graph.update(deepcopy(self.graph))
1622 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1623 G.add_edges_from((u, v, deepcopy(d))
1624 for u, nbrs in self._adj.items()
1625 for v, d in nbrs.items())
1626 return G
1627
1628 def subgraph(self, nodes):
1629 """Returns a SubGraph view of the subgraph induced on `nodes`.
1630
1631 The induced subgraph of the graph contains the nodes in `nodes`
1632 and the edges between those nodes.
1633
1634 Parameters
1635 ----------
1636 nodes : list, iterable
1637 A container of nodes which will be iterated through once.
1638
1639 Returns
1640 -------
1641 G : SubGraph View
1642 A subgraph view of the graph. The graph structure cannot be
1643 changed but node/edge attributes can and are shared with the
1644 original graph.
1645
1646 Notes
1647 -----
1648 The graph, edge and node attributes are shared with the original graph.
1649 Changes to the graph structure is ruled out by the view, but changes
1650 to attributes are reflected in the original graph.
1651
1652 To create a subgraph with its own copy of the edge/node attributes use:
1653 G.subgraph(nodes).copy()
1654
1655 For an inplace reduction of a graph to a subgraph you can remove nodes:
1656 G.remove_nodes_from([n for n in G if n not in set(nodes)])
1657
1658 Subgraph views are sometimes NOT what you want. In most cases where
1659 you want to do more than simply look at the induced edges, it makes
1660 more sense to just create the subgraph as its own graph with code like:
1661
1662 ::
1663
1664 # Create a subgraph SG based on a (possibly multigraph) G
1665 SG = G.__class__()
1666 SG.add_nodes_from((n, G.nodes[n]) for n in largest_wcc)
1667 if SG.is_multigraph:
1668 SG.add_edges_from((n, nbr, key, d)
1669 for n, nbrs in G.adj.items() if n in largest_wcc
1670 for nbr, keydict in nbrs.items() if nbr in largest_wcc
1671 for key, d in keydict.items())
1672 else:
1673 SG.add_edges_from((n, nbr, d)
1674 for n, nbrs in G.adj.items() if n in largest_wcc
1675 for nbr, d in nbrs.items() if nbr in largest_wcc)
1676 SG.graph.update(G.graph)
1677
1678 Examples
1679 --------
1680 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1681 >>> H = G.subgraph([0, 1, 2])
1682 >>> list(H.edges)
1683 [(0, 1), (1, 2)]
1684 """
1685 induced_nodes = nx.filters.show_nodes(self.nbunch_iter(nodes))
1686 # if already a subgraph, don't make a chain
1687 subgraph = nx.graphviews.subgraph_view
1688 if hasattr(self, '_NODE_OK'):
1689 return subgraph(self._graph, induced_nodes, self._EDGE_OK)
1690 return subgraph(self, induced_nodes)
1691
1692 def edge_subgraph(self, edges):
1693 """Returns the subgraph induced by the specified edges.
1694
1695 The induced subgraph contains each edge in `edges` and each
1696 node incident to any one of those edges.
1697
1698 Parameters
1699 ----------
1700 edges : iterable
1701 An iterable of edges in this graph.
1702
1703 Returns
1704 -------
1705 G : Graph
1706 An edge-induced subgraph of this graph with the same edge
1707 attributes.
1708
1709 Notes
1710 -----
1711 The graph, edge, and node attributes in the returned subgraph
1712 view are references to the corresponding attributes in the original
1713 graph. The view is read-only.
1714
1715 To create a full graph version of the subgraph with its own copy
1716 of the edge or node attributes, use::
1717
1718 >>> G.edge_subgraph(edges).copy() # doctest: +SKIP
1719
1720 Examples
1721 --------
1722 >>> G = nx.path_graph(5)
1723 >>> H = G.edge_subgraph([(0, 1), (3, 4)])
1724 >>> list(H.nodes)
1725 [0, 1, 3, 4]
1726 >>> list(H.edges)
1727 [(0, 1), (3, 4)]
1728
1729 """
1730 return nx.edge_subgraph(self, edges)
1731
1732 def size(self, weight=None):
1733 """Returns the number of edges or total of all edge weights.
1734
1735 Parameters
1736 ----------
1737 weight : string or None, optional (default=None)
1738 The edge attribute that holds the numerical value used
1739 as a weight. If None, then each edge has weight 1.
1740
1741 Returns
1742 -------
1743 size : numeric
1744 The number of edges or
1745 (if weight keyword is provided) the total weight sum.
1746
1747 If weight is None, returns an int. Otherwise a float
1748 (or more general numeric if the weights are more general).
1749
1750 See Also
1751 --------
1752 number_of_edges
1753
1754 Examples
1755 --------
1756 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1757 >>> G.size()
1758 3
1759
1760 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1761 >>> G.add_edge('a', 'b', weight=2)
1762 >>> G.add_edge('b', 'c', weight=4)
1763 >>> G.size()
1764 2
1765 >>> G.size(weight='weight')
1766 6.0
1767 """
1768 s = sum(d for v, d in self.degree(weight=weight))
1769 # If `weight` is None, the sum of the degrees is guaranteed to be
1770 # even, so we can perform integer division and hence return an
1771 # integer. Otherwise, the sum of the weighted degrees is not
1772 # guaranteed to be an integer, so we perform "real" division.
1773 return s // 2 if weight is None else s / 2
1774
1775 def number_of_edges(self, u=None, v=None):
1776 """Returns the number of edges between two nodes.
1777
1778 Parameters
1779 ----------
1780 u, v : nodes, optional (default=all edges)
1781 If u and v are specified, return the number of edges between
1782 u and v. Otherwise return the total number of all edges.
1783
1784 Returns
1785 -------
1786 nedges : int
1787 The number of edges in the graph. If nodes `u` and `v` are
1788 specified return the number of edges between those nodes. If
1789 the graph is directed, this only returns the number of edges
1790 from `u` to `v`.
1791
1792 See Also
1793 --------
1794 size
1795
1796 Examples
1797 --------
1798 For undirected graphs, this method counts the total number of
1799 edges in the graph:
1800
1801 >>> G = nx.path_graph(4)
1802 >>> G.number_of_edges()
1803 3
1804
1805 If you specify two nodes, this counts the total number of edges
1806 joining the two nodes:
1807
1808 >>> G.number_of_edges(0, 1)
1809 1
1810
1811 For directed graphs, this method can count the total number of
1812 directed edges from `u` to `v`:
1813
1814 >>> G = nx.DiGraph()
1815 >>> G.add_edge(0, 1)
1816 >>> G.add_edge(1, 0)
1817 >>> G.number_of_edges(0, 1)
1818 1
1819
1820 """
1821 if u is None:
1822 return int(self.size())
1823 if v in self._adj[u]:
1824 return 1
1825 return 0
1826
1827 def nbunch_iter(self, nbunch=None):
1828 """Returns an iterator over nodes contained in nbunch that are
1829 also in the graph.
1830
1831 The nodes in nbunch are checked for membership in the graph
1832 and if not are silently ignored.
1833
1834 Parameters
1835 ----------
1836 nbunch : single node, container, or all nodes (default= all nodes)
1837 The view will only report edges incident to these nodes.
1838
1839 Returns
1840 -------
1841 niter : iterator
1842 An iterator over nodes in nbunch that are also in the graph.
1843 If nbunch is None, iterate over all nodes in the graph.
1844
1845 Raises
1846 ------
1847 NetworkXError
1848 If nbunch is not a node or or sequence of nodes.
1849 If a node in nbunch is not hashable.
1850
1851 See Also
1852 --------
1853 Graph.__iter__
1854
1855 Notes
1856 -----
1857 When nbunch is an iterator, the returned iterator yields values
1858 directly from nbunch, becoming exhausted when nbunch is exhausted.
1859
1860 To test whether nbunch is a single node, one can use
1861 "if nbunch in self:", even after processing with this routine.
1862
1863 If nbunch is not a node or a (possibly empty) sequence/iterator
1864 or None, a :exc:`NetworkXError` is raised. Also, if any object in
1865 nbunch is not hashable, a :exc:`NetworkXError` is raised.
1866 """
1867 if nbunch is None: # include all nodes via iterator
1868 bunch = iter(self._adj)
1869 elif nbunch in self: # if nbunch is a single node
1870 bunch = iter([nbunch])
1871 else: # if nbunch is a sequence of nodes
1872 def bunch_iter(nlist, adj):
1873 try:
1874 for n in nlist:
1875 if n in adj:
1876 yield n
1877 except TypeError as e:
1878 message = e.args[0]
1879 # capture error for non-sequence/iterator nbunch.
1880 if 'iter' in message:
1881 msg = "nbunch is not a node or a sequence of nodes."
1882 raise NetworkXError(msg)
1883 # capture error for unhashable node.
1884 elif 'hashable' in message:
1885 msg = "Node {} in sequence nbunch is not a valid node."
1886 raise NetworkXError(msg.format(n))
1887 else:
1888 raise
1889 bunch = bunch_iter(nbunch, self._adj)
1890 return bunch