Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/classes/graph.py: 43%
287 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Base class for undirected graphs.
3The Graph class allows any hashable object as a node
4and can associate key/value attribute pairs with each undirected edge.
6Self-loops are allowed but multiple edges are not (see MultiGraph).
8For directed graphs see DiGraph and MultiDiGraph.
9"""
10from copy import deepcopy
11from functools import cached_property
13import networkx as nx
14from networkx import convert
15from networkx.classes.coreviews import AdjacencyView
16from networkx.classes.reportviews import DegreeView, EdgeView, NodeView
17from networkx.exception import NetworkXError
19__all__ = ["Graph"]
22class _CachedPropertyResetterAdj:
23 """Data Descriptor class for _adj that resets ``adj`` cached_property when needed
25 This assumes that the ``cached_property`` ``G.adj`` should be reset whenever
26 ``G._adj`` is set to a new value.
28 This object sits on a class and ensures that any instance of that
29 class clears its cached property "adj" whenever the underlying
30 instance attribute "_adj" is set to a new object. It only affects
31 the set process of the obj._adj attribute. All get/del operations
32 act as they normally would.
34 For info on Data Descriptors see: https://docs.python.org/3/howto/descriptor.html
35 """
37 def __set__(self, obj, value):
38 od = obj.__dict__
39 od["_adj"] = value
40 if "adj" in od:
41 del od["adj"]
44class _CachedPropertyResetterNode:
45 """Data Descriptor class for _node that resets ``nodes`` cached_property when needed
47 This assumes that the ``cached_property`` ``G.node`` should be reset whenever
48 ``G._node`` is set to a new value.
50 This object sits on a class and ensures that any instance of that
51 class clears its cached property "nodes" whenever the underlying
52 instance attribute "_node" is set to a new object. It only affects
53 the set process of the obj._adj attribute. All get/del operations
54 act as they normally would.
56 For info on Data Descriptors see: https://docs.python.org/3/howto/descriptor.html
57 """
59 def __set__(self, obj, value):
60 od = obj.__dict__
61 od["_node"] = value
62 if "nodes" in od:
63 del od["nodes"]
66class Graph:
67 """
68 Base class for undirected graphs.
70 A Graph stores nodes and edges with optional data, or attributes.
72 Graphs hold undirected edges. Self loops are allowed but multiple
73 (parallel) edges are not.
75 Nodes can be arbitrary (hashable) Python objects with optional
76 key/value attributes, except that `None` is not allowed as a node.
78 Edges are represented as links between nodes with optional
79 key/value attributes.
81 Parameters
82 ----------
83 incoming_graph_data : input graph (optional, default: None)
84 Data to initialize graph. If None (default) an empty
85 graph is created. The data can be any format that is supported
86 by the to_networkx_graph() function, currently including edge list,
87 dict of dicts, dict of lists, NetworkX graph, 2D NumPy array, SciPy
88 sparse matrix, or PyGraphviz graph.
90 attr : keyword arguments, optional (default= no attributes)
91 Attributes to add to graph as key=value pairs.
93 See Also
94 --------
95 DiGraph
96 MultiGraph
97 MultiDiGraph
99 Examples
100 --------
101 Create an empty graph structure (a "null graph") with no nodes and
102 no edges.
104 >>> G = nx.Graph()
106 G can be grown in several ways.
108 **Nodes:**
110 Add one node at a time:
112 >>> G.add_node(1)
114 Add the nodes from any container (a list, dict, set or
115 even the lines from a file or the nodes from another graph).
117 >>> G.add_nodes_from([2, 3])
118 >>> G.add_nodes_from(range(100, 110))
119 >>> H = nx.path_graph(10)
120 >>> G.add_nodes_from(H)
122 In addition to strings and integers any hashable Python object
123 (except None) can represent a node, e.g. a customized node object,
124 or even another Graph.
126 >>> G.add_node(H)
128 **Edges:**
130 G can also be grown by adding edges.
132 Add one edge,
134 >>> G.add_edge(1, 2)
136 a list of edges,
138 >>> G.add_edges_from([(1, 2), (1, 3)])
140 or a collection of edges,
142 >>> G.add_edges_from(H.edges)
144 If some edges connect nodes not yet in the graph, the nodes
145 are added automatically. There are no errors when adding
146 nodes or edges that already exist.
148 **Attributes:**
150 Each graph, node, and edge can hold key/value attribute pairs
151 in an associated attribute dictionary (the keys must be hashable).
152 By default these are empty, but can be added or changed using
153 add_edge, add_node or direct manipulation of the attribute
154 dictionaries named graph, node and edge respectively.
156 >>> G = nx.Graph(day="Friday")
157 >>> G.graph
158 {'day': 'Friday'}
160 Add node attributes using add_node(), add_nodes_from() or G.nodes
162 >>> G.add_node(1, time="5pm")
163 >>> G.add_nodes_from([3], time="2pm")
164 >>> G.nodes[1]
165 {'time': '5pm'}
166 >>> G.nodes[1]["room"] = 714 # node must exist already to use G.nodes
167 >>> del G.nodes[1]["room"] # remove attribute
168 >>> list(G.nodes(data=True))
169 [(1, {'time': '5pm'}), (3, {'time': '2pm'})]
171 Add edge attributes using add_edge(), add_edges_from(), subscript
172 notation, or G.edges.
174 >>> G.add_edge(1, 2, weight=4.7)
175 >>> G.add_edges_from([(3, 4), (4, 5)], color="red")
176 >>> G.add_edges_from([(1, 2, {"color": "blue"}), (2, 3, {"weight": 8})])
177 >>> G[1][2]["weight"] = 4.7
178 >>> G.edges[1, 2]["weight"] = 4
180 Warning: we protect the graph data structure by making `G.edges` a
181 read-only dict-like structure. However, you can assign to attributes
182 in e.g. `G.edges[1, 2]`. Thus, use 2 sets of brackets to add/change
183 data attributes: `G.edges[1, 2]['weight'] = 4`
184 (For multigraphs: `MG.edges[u, v, key][name] = value`).
186 **Shortcuts:**
188 Many common graph features allow python syntax to speed reporting.
190 >>> 1 in G # check if node in graph
191 True
192 >>> [n for n in G if n < 3] # iterate through nodes
193 [1, 2]
194 >>> len(G) # number of nodes in graph
195 5
197 Often the best way to traverse all edges of a graph is via the neighbors.
198 The neighbors are reported as an adjacency-dict `G.adj` or `G.adjacency()`
200 >>> for n, nbrsdict in G.adjacency():
201 ... for nbr, eattr in nbrsdict.items():
202 ... if "weight" in eattr:
203 ... # Do something useful with the edges
204 ... pass
206 But the edges() method is often more convenient:
208 >>> for u, v, weight in G.edges.data("weight"):
209 ... if weight is not None:
210 ... # Do something useful with the edges
211 ... pass
213 **Reporting:**
215 Simple graph information is obtained using object-attributes and methods.
216 Reporting typically provides views instead of containers to reduce memory
217 usage. The views update as the graph is updated similarly to dict-views.
218 The objects `nodes`, `edges` and `adj` provide access to data attributes
219 via lookup (e.g. `nodes[n]`, `edges[u, v]`, `adj[u][v]`) and iteration
220 (e.g. `nodes.items()`, `nodes.data('color')`,
221 `nodes.data('color', default='blue')` and similarly for `edges`)
222 Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`.
224 For details on these and other miscellaneous methods, see below.
226 **Subclasses (Advanced):**
228 The Graph class uses a dict-of-dict-of-dict data structure.
229 The outer dict (node_dict) holds adjacency information keyed by node.
230 The next dict (adjlist_dict) represents the adjacency information and holds
231 edge data keyed by neighbor. The inner dict (edge_attr_dict) represents
232 the edge data and holds edge attribute values keyed by attribute names.
234 Each of these three dicts can be replaced in a subclass by a user defined
235 dict-like object. In general, the dict-like features should be
236 maintained but extra features can be added. To replace one of the
237 dicts create a new graph class by changing the class(!) variable
238 holding the factory for that dict-like structure.
240 node_dict_factory : function, (default: dict)
241 Factory function to be used to create the dict containing node
242 attributes, keyed by node id.
243 It should require no arguments and return a dict-like object
245 node_attr_dict_factory: function, (default: dict)
246 Factory function to be used to create the node attribute
247 dict which holds attribute values keyed by attribute name.
248 It should require no arguments and return a dict-like object
250 adjlist_outer_dict_factory : function, (default: dict)
251 Factory function to be used to create the outer-most dict
252 in the data structure that holds adjacency info keyed by node.
253 It should require no arguments and return a dict-like object.
255 adjlist_inner_dict_factory : function, (default: dict)
256 Factory function to be used to create the adjacency list
257 dict which holds edge data keyed by neighbor.
258 It should require no arguments and return a dict-like object
260 edge_attr_dict_factory : function, (default: dict)
261 Factory function to be used to create the edge attribute
262 dict which holds attribute values keyed by attribute name.
263 It should require no arguments and return a dict-like object.
265 graph_attr_dict_factory : function, (default: dict)
266 Factory function to be used to create the graph attribute
267 dict which holds attribute values keyed by attribute name.
268 It should require no arguments and return a dict-like object.
270 Typically, if your extension doesn't impact the data structure all
271 methods will inherit without issue except: `to_directed/to_undirected`.
272 By default these methods create a DiGraph/Graph class and you probably
273 want them to create your extension of a DiGraph/Graph. To facilitate
274 this we define two class variables that you can set in your subclass.
276 to_directed_class : callable, (default: DiGraph or MultiDiGraph)
277 Class to create a new graph structure in the `to_directed` method.
278 If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used.
280 to_undirected_class : callable, (default: Graph or MultiGraph)
281 Class to create a new graph structure in the `to_undirected` method.
282 If `None`, a NetworkX class (Graph or MultiGraph) is used.
284 **Subclassing Example**
286 Create a low memory graph class that effectively disallows edge
287 attributes by using a single attribute dict for all edges.
288 This reduces the memory used, but you lose edge attributes.
290 >>> class ThinGraph(nx.Graph):
291 ... all_edge_dict = {"weight": 1}
292 ...
293 ... def single_edge_dict(self):
294 ... return self.all_edge_dict
295 ...
296 ... edge_attr_dict_factory = single_edge_dict
297 >>> G = ThinGraph()
298 >>> G.add_edge(2, 1)
299 >>> G[2][1]
300 {'weight': 1}
301 >>> G.add_edge(2, 2)
302 >>> G[2][1] is G[2][2]
303 True
304 """
306 _adj = _CachedPropertyResetterAdj()
307 _node = _CachedPropertyResetterNode()
309 node_dict_factory = dict
310 node_attr_dict_factory = dict
311 adjlist_outer_dict_factory = dict
312 adjlist_inner_dict_factory = dict
313 edge_attr_dict_factory = dict
314 graph_attr_dict_factory = dict
316 def to_directed_class(self):
317 """Returns the class to use for empty directed copies.
319 If you subclass the base classes, use this to designate
320 what directed class to use for `to_directed()` copies.
321 """
322 return nx.DiGraph
324 def to_undirected_class(self):
325 """Returns the class to use for empty undirected copies.
327 If you subclass the base classes, use this to designate
328 what directed class to use for `to_directed()` copies.
329 """
330 return Graph
332 def __init__(self, incoming_graph_data=None, **attr):
333 """Initialize a graph with edges, name, or graph attributes.
335 Parameters
336 ----------
337 incoming_graph_data : input graph (optional, default: None)
338 Data to initialize graph. If None (default) an empty
339 graph is created. The data can be an edge list, or any
340 NetworkX graph object. If the corresponding optional Python
341 packages are installed the data can also be a 2D NumPy array, a
342 SciPy sparse array, or a PyGraphviz graph.
344 attr : keyword arguments, optional (default= no attributes)
345 Attributes to add to graph as key=value pairs.
347 See Also
348 --------
349 convert
351 Examples
352 --------
353 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
354 >>> G = nx.Graph(name="my graph")
355 >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges
356 >>> G = nx.Graph(e)
358 Arbitrary graph attribute pairs (key=value) may be assigned
360 >>> G = nx.Graph(e, day="Friday")
361 >>> G.graph
362 {'day': 'Friday'}
364 """
365 self.graph = self.graph_attr_dict_factory() # dictionary for graph attributes
366 self._node = self.node_dict_factory() # empty node attribute dict
367 self._adj = self.adjlist_outer_dict_factory() # empty adjacency dict
368 # attempt to load graph with data
369 if incoming_graph_data is not None:
370 convert.to_networkx_graph(incoming_graph_data, create_using=self)
371 # load graph attributes (must be after convert)
372 self.graph.update(attr)
374 @cached_property
375 def adj(self):
376 """Graph adjacency object holding the neighbors of each node.
378 This object is a read-only dict-like structure with node keys
379 and neighbor-dict values. The neighbor-dict is keyed by neighbor
380 to the edge-data-dict. So `G.adj[3][2]['color'] = 'blue'` sets
381 the color of the edge `(3, 2)` to `"blue"`.
383 Iterating over G.adj behaves like a dict. Useful idioms include
384 `for nbr, datadict in G.adj[n].items():`.
386 The neighbor information is also provided by subscripting the graph.
387 So `for nbr, foovalue in G[node].data('foo', default=1):` works.
389 For directed graphs, `G.adj` holds outgoing (successor) info.
390 """
391 return AdjacencyView(self._adj)
393 @property
394 def name(self):
395 """String identifier of the graph.
397 This graph attribute appears in the attribute dict G.graph
398 keyed by the string `"name"`. as well as an attribute (technically
399 a property) `G.name`. This is entirely user controlled.
400 """
401 return self.graph.get("name", "")
403 @name.setter
404 def name(self, s):
405 self.graph["name"] = s
407 def __str__(self):
408 """Returns a short summary of the graph.
410 Returns
411 -------
412 info : string
413 Graph information including the graph name (if any), graph type, and the
414 number of nodes and edges.
416 Examples
417 --------
418 >>> G = nx.Graph(name="foo")
419 >>> str(G)
420 "Graph named 'foo' with 0 nodes and 0 edges"
422 >>> G = nx.path_graph(3)
423 >>> str(G)
424 'Graph with 3 nodes and 2 edges'
426 """
427 return "".join(
428 [
429 type(self).__name__,
430 f" named {self.name!r}" if self.name else "",
431 f" with {self.number_of_nodes()} nodes and {self.number_of_edges()} edges",
432 ]
433 )
435 def __iter__(self):
436 """Iterate over the nodes. Use: 'for n in G'.
438 Returns
439 -------
440 niter : iterator
441 An iterator over all nodes in the graph.
443 Examples
444 --------
445 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
446 >>> [n for n in G]
447 [0, 1, 2, 3]
448 >>> list(G)
449 [0, 1, 2, 3]
450 """
451 return iter(self._node)
453 def __contains__(self, n):
454 """Returns True if n is a node, False otherwise. Use: 'n in G'.
456 Examples
457 --------
458 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
459 >>> 1 in G
460 True
461 """
462 try:
463 return n in self._node
464 except TypeError:
465 return False
467 def __len__(self):
468 """Returns the number of nodes in the graph. Use: 'len(G)'.
470 Returns
471 -------
472 nnodes : int
473 The number of nodes in the graph.
475 See Also
476 --------
477 number_of_nodes: identical method
478 order: identical method
480 Examples
481 --------
482 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
483 >>> len(G)
484 4
486 """
487 return len(self._node)
489 def __getitem__(self, n):
490 """Returns a dict of neighbors of node n. Use: 'G[n]'.
492 Parameters
493 ----------
494 n : node
495 A node in the graph.
497 Returns
498 -------
499 adj_dict : dictionary
500 The adjacency dictionary for nodes connected to n.
502 Notes
503 -----
504 G[n] is the same as G.adj[n] and similar to G.neighbors(n)
505 (which is an iterator over G.adj[n])
507 Examples
508 --------
509 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
510 >>> G[0]
511 AtlasView({1: {}})
512 """
513 return self.adj[n]
515 def add_node(self, node_for_adding, **attr):
516 """Add a single node `node_for_adding` and update node attributes.
518 Parameters
519 ----------
520 node_for_adding : node
521 A node can be any hashable Python object except None.
522 attr : keyword arguments, optional
523 Set or change node attributes using key=value.
525 See Also
526 --------
527 add_nodes_from
529 Examples
530 --------
531 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
532 >>> G.add_node(1)
533 >>> G.add_node("Hello")
534 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
535 >>> G.add_node(K3)
536 >>> G.number_of_nodes()
537 3
539 Use keywords set/change node attributes:
541 >>> G.add_node(1, size=10)
542 >>> G.add_node(3, weight=0.4, UTM=("13S", 382871, 3972649))
544 Notes
545 -----
546 A hashable object is one that can be used as a key in a Python
547 dictionary. This includes strings, numbers, tuples of strings
548 and numbers, etc.
550 On many platforms hashable items also include mutables such as
551 NetworkX Graphs, though one should be careful that the hash
552 doesn't change on mutables.
553 """
554 if node_for_adding not in self._node:
555 if node_for_adding is None:
556 raise ValueError("None cannot be a node")
557 self._adj[node_for_adding] = self.adjlist_inner_dict_factory()
558 attr_dict = self._node[node_for_adding] = self.node_attr_dict_factory()
559 attr_dict.update(attr)
560 else: # update attr even if node already exists
561 self._node[node_for_adding].update(attr)
563 def add_nodes_from(self, nodes_for_adding, **attr):
564 """Add multiple nodes.
566 Parameters
567 ----------
568 nodes_for_adding : iterable container
569 A container of nodes (list, dict, set, etc.).
570 OR
571 A container of (node, attribute dict) tuples.
572 Node attributes are updated using the attribute dict.
573 attr : keyword arguments, optional (default= no attributes)
574 Update attributes for all nodes in nodes.
575 Node attributes specified in nodes as a tuple take
576 precedence over attributes specified via keyword arguments.
578 See Also
579 --------
580 add_node
582 Notes
583 -----
584 When adding nodes from an iterator over the graph you are changing,
585 a `RuntimeError` can be raised with message:
586 `RuntimeError: dictionary changed size during iteration`. This
587 happens when the graph's underlying dictionary is modified during
588 iteration. To avoid this error, evaluate the iterator into a separate
589 object, e.g. by using `list(iterator_of_nodes)`, and pass this
590 object to `G.add_nodes_from`.
592 Examples
593 --------
594 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
595 >>> G.add_nodes_from("Hello")
596 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
597 >>> G.add_nodes_from(K3)
598 >>> sorted(G.nodes(), key=str)
599 [0, 1, 2, 'H', 'e', 'l', 'o']
601 Use keywords to update specific node attributes for every node.
603 >>> G.add_nodes_from([1, 2], size=10)
604 >>> G.add_nodes_from([3, 4], weight=0.4)
606 Use (node, attrdict) tuples to update attributes for specific nodes.
608 >>> G.add_nodes_from([(1, dict(size=11)), (2, {"color": "blue"})])
609 >>> G.nodes[1]["size"]
610 11
611 >>> H = nx.Graph()
612 >>> H.add_nodes_from(G.nodes(data=True))
613 >>> H.nodes[1]["size"]
614 11
616 Evaluate an iterator over a graph if using it to modify the same graph
618 >>> G = nx.Graph([(0, 1), (1, 2), (3, 4)])
619 >>> # wrong way - will raise RuntimeError
620 >>> # G.add_nodes_from(n + 1 for n in G.nodes)
621 >>> # correct way
622 >>> G.add_nodes_from(list(n + 1 for n in G.nodes))
623 """
624 for n in nodes_for_adding:
625 try:
626 newnode = n not in self._node
627 newdict = attr
628 except TypeError:
629 n, ndict = n
630 newnode = n not in self._node
631 newdict = attr.copy()
632 newdict.update(ndict)
633 if newnode:
634 if n is None:
635 raise ValueError("None cannot be a node")
636 self._adj[n] = self.adjlist_inner_dict_factory()
637 self._node[n] = self.node_attr_dict_factory()
638 self._node[n].update(newdict)
640 def remove_node(self, n):
641 """Remove node n.
643 Removes the node n and all adjacent edges.
644 Attempting to remove a nonexistent node will raise an exception.
646 Parameters
647 ----------
648 n : node
649 A node in the graph
651 Raises
652 ------
653 NetworkXError
654 If n is not in the graph.
656 See Also
657 --------
658 remove_nodes_from
660 Examples
661 --------
662 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
663 >>> list(G.edges)
664 [(0, 1), (1, 2)]
665 >>> G.remove_node(1)
666 >>> list(G.edges)
667 []
669 """
670 adj = self._adj
671 try:
672 nbrs = list(adj[n]) # list handles self-loops (allows mutation)
673 del self._node[n]
674 except KeyError as err: # NetworkXError if n not in self
675 raise NetworkXError(f"The node {n} is not in the graph.") from err
676 for u in nbrs:
677 del adj[u][n] # remove all edges n-u in graph
678 del adj[n] # now remove node
680 def remove_nodes_from(self, nodes):
681 """Remove multiple nodes.
683 Parameters
684 ----------
685 nodes : iterable container
686 A container of nodes (list, dict, set, etc.). If a node
687 in the container is not in the graph it is silently
688 ignored.
690 See Also
691 --------
692 remove_node
694 Notes
695 -----
696 When removing nodes from an iterator over the graph you are changing,
697 a `RuntimeError` will be raised with message:
698 `RuntimeError: dictionary changed size during iteration`. This
699 happens when the graph's underlying dictionary is modified during
700 iteration. To avoid this error, evaluate the iterator into a separate
701 object, e.g. by using `list(iterator_of_nodes)`, and pass this
702 object to `G.remove_nodes_from`.
704 Examples
705 --------
706 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
707 >>> e = list(G.nodes)
708 >>> e
709 [0, 1, 2]
710 >>> G.remove_nodes_from(e)
711 >>> list(G.nodes)
712 []
714 Evaluate an iterator over a graph if using it to modify the same graph
716 >>> G = nx.Graph([(0, 1), (1, 2), (3, 4)])
717 >>> # this command will fail, as the graph's dict is modified during iteration
718 >>> # G.remove_nodes_from(n for n in G.nodes if n < 2)
719 >>> # this command will work, since the dictionary underlying graph is not modified
720 >>> G.remove_nodes_from(list(n for n in G.nodes if n < 2))
721 """
722 adj = self._adj
723 for n in nodes:
724 try:
725 del self._node[n]
726 for u in list(adj[n]): # list handles self-loops
727 del adj[u][n] # (allows mutation of dict in loop)
728 del adj[n]
729 except KeyError:
730 pass
732 @cached_property
733 def nodes(self):
734 """A NodeView of the Graph as G.nodes or G.nodes().
736 Can be used as `G.nodes` for data lookup and for set-like operations.
737 Can also be used as `G.nodes(data='color', default=None)` to return a
738 NodeDataView which reports specific node data but no set operations.
739 It presents a dict-like interface as well with `G.nodes.items()`
740 iterating over `(node, nodedata)` 2-tuples and `G.nodes[3]['foo']`
741 providing the value of the `foo` attribute for node `3`. In addition,
742 a view `G.nodes.data('foo')` provides a dict-like interface to the
743 `foo` attribute of each node. `G.nodes.data('foo', default=1)`
744 provides a default for nodes that do not have attribute `foo`.
746 Parameters
747 ----------
748 data : string or bool, optional (default=False)
749 The node attribute returned in 2-tuple (n, ddict[data]).
750 If True, return entire node attribute dict as (n, ddict).
751 If False, return just the nodes n.
753 default : value, optional (default=None)
754 Value used for nodes that don't have the requested attribute.
755 Only relevant if data is not True or False.
757 Returns
758 -------
759 NodeView
760 Allows set-like operations over the nodes as well as node
761 attribute dict lookup and calling to get a NodeDataView.
762 A NodeDataView iterates over `(n, data)` and has no set operations.
763 A NodeView iterates over `n` and includes set operations.
765 When called, if data is False, an iterator over nodes.
766 Otherwise an iterator of 2-tuples (node, attribute value)
767 where the attribute is specified in `data`.
768 If data is True then the attribute becomes the
769 entire data dictionary.
771 Notes
772 -----
773 If your node data is not needed, it is simpler and equivalent
774 to use the expression ``for n in G``, or ``list(G)``.
776 Examples
777 --------
778 There are two simple ways of getting a list of all nodes in the graph:
780 >>> G = nx.path_graph(3)
781 >>> list(G.nodes)
782 [0, 1, 2]
783 >>> list(G)
784 [0, 1, 2]
786 To get the node data along with the nodes:
788 >>> G.add_node(1, time="5pm")
789 >>> G.nodes[0]["foo"] = "bar"
790 >>> list(G.nodes(data=True))
791 [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})]
792 >>> list(G.nodes.data())
793 [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})]
795 >>> list(G.nodes(data="foo"))
796 [(0, 'bar'), (1, None), (2, None)]
797 >>> list(G.nodes.data("foo"))
798 [(0, 'bar'), (1, None), (2, None)]
800 >>> list(G.nodes(data="time"))
801 [(0, None), (1, '5pm'), (2, None)]
802 >>> list(G.nodes.data("time"))
803 [(0, None), (1, '5pm'), (2, None)]
805 >>> list(G.nodes(data="time", default="Not Available"))
806 [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')]
807 >>> list(G.nodes.data("time", default="Not Available"))
808 [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')]
810 If some of your nodes have an attribute and the rest are assumed
811 to have a default attribute value you can create a dictionary
812 from node/attribute pairs using the `default` keyword argument
813 to guarantee the value is never None::
815 >>> G = nx.Graph()
816 >>> G.add_node(0)
817 >>> G.add_node(1, weight=2)
818 >>> G.add_node(2, weight=3)
819 >>> dict(G.nodes(data="weight", default=1))
820 {0: 1, 1: 2, 2: 3}
822 """
823 return NodeView(self)
825 def number_of_nodes(self):
826 """Returns the number of nodes in the graph.
828 Returns
829 -------
830 nnodes : int
831 The number of nodes in the graph.
833 See Also
834 --------
835 order: identical method
836 __len__: identical method
838 Examples
839 --------
840 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
841 >>> G.number_of_nodes()
842 3
843 """
844 return len(self._node)
846 def order(self):
847 """Returns the number of nodes in the graph.
849 Returns
850 -------
851 nnodes : int
852 The number of nodes in the graph.
854 See Also
855 --------
856 number_of_nodes: identical method
857 __len__: identical method
859 Examples
860 --------
861 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
862 >>> G.order()
863 3
864 """
865 return len(self._node)
867 def has_node(self, n):
868 """Returns True if the graph contains the node n.
870 Identical to `n in G`
872 Parameters
873 ----------
874 n : node
876 Examples
877 --------
878 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
879 >>> G.has_node(0)
880 True
882 It is more readable and simpler to use
884 >>> 0 in G
885 True
887 """
888 try:
889 return n in self._node
890 except TypeError:
891 return False
893 def add_edge(self, u_of_edge, v_of_edge, **attr):
894 """Add an edge between u and v.
896 The nodes u and v will be automatically added if they are
897 not already in the graph.
899 Edge attributes can be specified with keywords or by directly
900 accessing the edge's attribute dictionary. See examples below.
902 Parameters
903 ----------
904 u_of_edge, v_of_edge : nodes
905 Nodes can be, for example, strings or numbers.
906 Nodes must be hashable (and not None) Python objects.
907 attr : keyword arguments, optional
908 Edge data (or labels or objects) can be assigned using
909 keyword arguments.
911 See Also
912 --------
913 add_edges_from : add a collection of edges
915 Notes
916 -----
917 Adding an edge that already exists updates the edge data.
919 Many NetworkX algorithms designed for weighted graphs use
920 an edge attribute (by default `weight`) to hold a numerical value.
922 Examples
923 --------
924 The following all add the edge e=(1, 2) to graph G:
926 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
927 >>> e = (1, 2)
928 >>> G.add_edge(1, 2) # explicit two-node form
929 >>> G.add_edge(*e) # single edge as tuple of two nodes
930 >>> G.add_edges_from([(1, 2)]) # add edges from iterable container
932 Associate data to edges using keywords:
934 >>> G.add_edge(1, 2, weight=3)
935 >>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7)
937 For non-string attribute keys, use subscript notation.
939 >>> G.add_edge(1, 2)
940 >>> G[1][2].update({0: 5})
941 >>> G.edges[1, 2].update({0: 5})
942 """
943 u, v = u_of_edge, v_of_edge
944 # add nodes
945 if u not in self._node:
946 if u is None:
947 raise ValueError("None cannot be a node")
948 self._adj[u] = self.adjlist_inner_dict_factory()
949 self._node[u] = self.node_attr_dict_factory()
950 if v not in self._node:
951 if v is None:
952 raise ValueError("None cannot be a node")
953 self._adj[v] = self.adjlist_inner_dict_factory()
954 self._node[v] = self.node_attr_dict_factory()
955 # add the edge
956 datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
957 datadict.update(attr)
958 self._adj[u][v] = datadict
959 self._adj[v][u] = datadict
961 def add_edges_from(self, ebunch_to_add, **attr):
962 """Add all the edges in ebunch_to_add.
964 Parameters
965 ----------
966 ebunch_to_add : container of edges
967 Each edge given in the container will be added to the
968 graph. The edges must be given as 2-tuples (u, v) or
969 3-tuples (u, v, d) where d is a dictionary containing edge data.
970 attr : keyword arguments, optional
971 Edge data (or labels or objects) can be assigned using
972 keyword arguments.
974 See Also
975 --------
976 add_edge : add a single edge
977 add_weighted_edges_from : convenient way to add weighted edges
979 Notes
980 -----
981 Adding the same edge twice has no effect but any edge data
982 will be updated when each duplicate edge is added.
984 Edge attributes specified in an ebunch take precedence over
985 attributes specified via keyword arguments.
987 When adding edges from an iterator over the graph you are changing,
988 a `RuntimeError` can be raised with message:
989 `RuntimeError: dictionary changed size during iteration`. This
990 happens when the graph's underlying dictionary is modified during
991 iteration. To avoid this error, evaluate the iterator into a separate
992 object, e.g. by using `list(iterator_of_edges)`, and pass this
993 object to `G.add_edges_from`.
995 Examples
996 --------
997 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
998 >>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples
999 >>> e = zip(range(0, 3), range(1, 4))
1000 >>> G.add_edges_from(e) # Add the path graph 0-1-2-3
1002 Associate data to edges
1004 >>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
1005 >>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898")
1007 Evaluate an iterator over a graph if using it to modify the same graph
1009 >>> G = nx.Graph([(1, 2), (2, 3), (3, 4)])
1010 >>> # Grow graph by one new node, adding edges to all existing nodes.
1011 >>> # wrong way - will raise RuntimeError
1012 >>> # G.add_edges_from(((5, n) for n in G.nodes))
1013 >>> # correct way - note that there will be no self-edge for node 5
1014 >>> G.add_edges_from(list((5, n) for n in G.nodes))
1015 """
1016 for e in ebunch_to_add:
1017 ne = len(e)
1018 if ne == 3:
1019 u, v, dd = e
1020 elif ne == 2:
1021 u, v = e
1022 dd = {} # doesn't need edge_attr_dict_factory
1023 else:
1024 raise NetworkXError(f"Edge tuple {e} must be a 2-tuple or 3-tuple.")
1025 if u not in self._node:
1026 if u is None:
1027 raise ValueError("None cannot be a node")
1028 self._adj[u] = self.adjlist_inner_dict_factory()
1029 self._node[u] = self.node_attr_dict_factory()
1030 if v not in self._node:
1031 if v is None:
1032 raise ValueError("None cannot be a node")
1033 self._adj[v] = self.adjlist_inner_dict_factory()
1034 self._node[v] = self.node_attr_dict_factory()
1035 datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
1036 datadict.update(attr)
1037 datadict.update(dd)
1038 self._adj[u][v] = datadict
1039 self._adj[v][u] = datadict
1041 def add_weighted_edges_from(self, ebunch_to_add, weight="weight", **attr):
1042 """Add weighted edges in `ebunch_to_add` with specified weight attr
1044 Parameters
1045 ----------
1046 ebunch_to_add : container of edges
1047 Each edge given in the list or container will be added
1048 to the graph. The edges must be given as 3-tuples (u, v, w)
1049 where w is a number.
1050 weight : string, optional (default= 'weight')
1051 The attribute name for the edge weights to be added.
1052 attr : keyword arguments, optional (default= no attributes)
1053 Edge attributes to add/update for all edges.
1055 See Also
1056 --------
1057 add_edge : add a single edge
1058 add_edges_from : add multiple edges
1060 Notes
1061 -----
1062 Adding the same edge twice for Graph/DiGraph simply updates
1063 the edge data. For MultiGraph/MultiDiGraph, duplicate edges
1064 are stored.
1066 When adding edges from an iterator over the graph you are changing,
1067 a `RuntimeError` can be raised with message:
1068 `RuntimeError: dictionary changed size during iteration`. This
1069 happens when the graph's underlying dictionary is modified during
1070 iteration. To avoid this error, evaluate the iterator into a separate
1071 object, e.g. by using `list(iterator_of_edges)`, and pass this
1072 object to `G.add_weighted_edges_from`.
1074 Examples
1075 --------
1076 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1077 >>> G.add_weighted_edges_from([(0, 1, 3.0), (1, 2, 7.5)])
1079 Evaluate an iterator over edges before passing it
1081 >>> G = nx.Graph([(1, 2), (2, 3), (3, 4)])
1082 >>> weight = 0.1
1083 >>> # Grow graph by one new node, adding edges to all existing nodes.
1084 >>> # wrong way - will raise RuntimeError
1085 >>> # G.add_weighted_edges_from(((5, n, weight) for n in G.nodes))
1086 >>> # correct way - note that there will be no self-edge for node 5
1087 >>> G.add_weighted_edges_from(list((5, n, weight) for n in G.nodes))
1088 """
1089 self.add_edges_from(((u, v, {weight: d}) for u, v, d in ebunch_to_add), **attr)
1091 def remove_edge(self, u, v):
1092 """Remove the edge between u and v.
1094 Parameters
1095 ----------
1096 u, v : nodes
1097 Remove the edge between nodes u and v.
1099 Raises
1100 ------
1101 NetworkXError
1102 If there is not an edge between u and v.
1104 See Also
1105 --------
1106 remove_edges_from : remove a collection of edges
1108 Examples
1109 --------
1110 >>> G = nx.path_graph(4) # or DiGraph, etc
1111 >>> G.remove_edge(0, 1)
1112 >>> e = (1, 2)
1113 >>> G.remove_edge(*e) # unpacks e from an edge tuple
1114 >>> e = (2, 3, {"weight": 7}) # an edge with attribute data
1115 >>> G.remove_edge(*e[:2]) # select first part of edge tuple
1116 """
1117 try:
1118 del self._adj[u][v]
1119 if u != v: # self-loop needs only one entry removed
1120 del self._adj[v][u]
1121 except KeyError as err:
1122 raise NetworkXError(f"The edge {u}-{v} is not in the graph") from err
1124 def remove_edges_from(self, ebunch):
1125 """Remove all edges specified in ebunch.
1127 Parameters
1128 ----------
1129 ebunch: list or container of edge tuples
1130 Each edge given in the list or container will be removed
1131 from the graph. The edges can be:
1133 - 2-tuples (u, v) edge between u and v.
1134 - 3-tuples (u, v, k) where k is ignored.
1136 See Also
1137 --------
1138 remove_edge : remove a single edge
1140 Notes
1141 -----
1142 Will fail silently if an edge in ebunch is not in the graph.
1144 Examples
1145 --------
1146 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1147 >>> ebunch = [(1, 2), (2, 3)]
1148 >>> G.remove_edges_from(ebunch)
1149 """
1150 adj = self._adj
1151 for e in ebunch:
1152 u, v = e[:2] # ignore edge data if present
1153 if u in adj and v in adj[u]:
1154 del adj[u][v]
1155 if u != v: # self loop needs only one entry removed
1156 del adj[v][u]
1158 def update(self, edges=None, nodes=None):
1159 """Update the graph using nodes/edges/graphs as input.
1161 Like dict.update, this method takes a graph as input, adding the
1162 graph's nodes and edges to this graph. It can also take two inputs:
1163 edges and nodes. Finally it can take either edges or nodes.
1164 To specify only nodes the keyword `nodes` must be used.
1166 The collections of edges and nodes are treated similarly to
1167 the add_edges_from/add_nodes_from methods. When iterated, they
1168 should yield 2-tuples (u, v) or 3-tuples (u, v, datadict).
1170 Parameters
1171 ----------
1172 edges : Graph object, collection of edges, or None
1173 The first parameter can be a graph or some edges. If it has
1174 attributes `nodes` and `edges`, then it is taken to be a
1175 Graph-like object and those attributes are used as collections
1176 of nodes and edges to be added to the graph.
1177 If the first parameter does not have those attributes, it is
1178 treated as a collection of edges and added to the graph.
1179 If the first argument is None, no edges are added.
1180 nodes : collection of nodes, or None
1181 The second parameter is treated as a collection of nodes
1182 to be added to the graph unless it is None.
1183 If `edges is None` and `nodes is None` an exception is raised.
1184 If the first parameter is a Graph, then `nodes` is ignored.
1186 Examples
1187 --------
1188 >>> G = nx.path_graph(5)
1189 >>> G.update(nx.complete_graph(range(4, 10)))
1190 >>> from itertools import combinations
1191 >>> edges = (
1192 ... (u, v, {"power": u * v})
1193 ... for u, v in combinations(range(10, 20), 2)
1194 ... if u * v < 225
1195 ... )
1196 >>> nodes = [1000] # for singleton, use a container
1197 >>> G.update(edges, nodes)
1199 Notes
1200 -----
1201 It you want to update the graph using an adjacency structure
1202 it is straightforward to obtain the edges/nodes from adjacency.
1203 The following examples provide common cases, your adjacency may
1204 be slightly different and require tweaks of these examples::
1206 >>> # dict-of-set/list/tuple
1207 >>> adj = {1: {2, 3}, 2: {1, 3}, 3: {1, 2}}
1208 >>> e = [(u, v) for u, nbrs in adj.items() for v in nbrs]
1209 >>> G.update(edges=e, nodes=adj)
1211 >>> DG = nx.DiGraph()
1212 >>> # dict-of-dict-of-attribute
1213 >>> adj = {1: {2: 1.3, 3: 0.7}, 2: {1: 1.4}, 3: {1: 0.7}}
1214 >>> e = [
1215 ... (u, v, {"weight": d})
1216 ... for u, nbrs in adj.items()
1217 ... for v, d in nbrs.items()
1218 ... ]
1219 >>> DG.update(edges=e, nodes=adj)
1221 >>> # dict-of-dict-of-dict
1222 >>> adj = {1: {2: {"weight": 1.3}, 3: {"color": 0.7, "weight": 1.2}}}
1223 >>> e = [
1224 ... (u, v, {"weight": d})
1225 ... for u, nbrs in adj.items()
1226 ... for v, d in nbrs.items()
1227 ... ]
1228 >>> DG.update(edges=e, nodes=adj)
1230 >>> # predecessor adjacency (dict-of-set)
1231 >>> pred = {1: {2, 3}, 2: {3}, 3: {3}}
1232 >>> e = [(v, u) for u, nbrs in pred.items() for v in nbrs]
1234 >>> # MultiGraph dict-of-dict-of-dict-of-attribute
1235 >>> MDG = nx.MultiDiGraph()
1236 >>> adj = {
1237 ... 1: {2: {0: {"weight": 1.3}, 1: {"weight": 1.2}}},
1238 ... 3: {2: {0: {"weight": 0.7}}},
1239 ... }
1240 >>> e = [
1241 ... (u, v, ekey, d)
1242 ... for u, nbrs in adj.items()
1243 ... for v, keydict in nbrs.items()
1244 ... for ekey, d in keydict.items()
1245 ... ]
1246 >>> MDG.update(edges=e)
1248 See Also
1249 --------
1250 add_edges_from: add multiple edges to a graph
1251 add_nodes_from: add multiple nodes to a graph
1252 """
1253 if edges is not None:
1254 if nodes is not None:
1255 self.add_nodes_from(nodes)
1256 self.add_edges_from(edges)
1257 else:
1258 # check if edges is a Graph object
1259 try:
1260 graph_nodes = edges.nodes
1261 graph_edges = edges.edges
1262 except AttributeError:
1263 # edge not Graph-like
1264 self.add_edges_from(edges)
1265 else: # edges is Graph-like
1266 self.add_nodes_from(graph_nodes.data())
1267 self.add_edges_from(graph_edges.data())
1268 self.graph.update(edges.graph)
1269 elif nodes is not None:
1270 self.add_nodes_from(nodes)
1271 else:
1272 raise NetworkXError("update needs nodes or edges input")
1274 def has_edge(self, u, v):
1275 """Returns True if the edge (u, v) is in the graph.
1277 This is the same as `v in G[u]` without KeyError exceptions.
1279 Parameters
1280 ----------
1281 u, v : nodes
1282 Nodes can be, for example, strings or numbers.
1283 Nodes must be hashable (and not None) Python objects.
1285 Returns
1286 -------
1287 edge_ind : bool
1288 True if edge is in the graph, False otherwise.
1290 Examples
1291 --------
1292 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1293 >>> G.has_edge(0, 1) # using two nodes
1294 True
1295 >>> e = (0, 1)
1296 >>> G.has_edge(*e) # e is a 2-tuple (u, v)
1297 True
1298 >>> e = (0, 1, {"weight": 7})
1299 >>> G.has_edge(*e[:2]) # e is a 3-tuple (u, v, data_dictionary)
1300 True
1302 The following syntax are equivalent:
1304 >>> G.has_edge(0, 1)
1305 True
1306 >>> 1 in G[0] # though this gives KeyError if 0 not in G
1307 True
1309 """
1310 try:
1311 return v in self._adj[u]
1312 except KeyError:
1313 return False
1315 def neighbors(self, n):
1316 """Returns an iterator over all neighbors of node n.
1318 This is identical to `iter(G[n])`
1320 Parameters
1321 ----------
1322 n : node
1323 A node in the graph
1325 Returns
1326 -------
1327 neighbors : iterator
1328 An iterator over all neighbors of node n
1330 Raises
1331 ------
1332 NetworkXError
1333 If the node n is not in the graph.
1335 Examples
1336 --------
1337 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1338 >>> [n for n in G.neighbors(0)]
1339 [1]
1341 Notes
1342 -----
1343 Alternate ways to access the neighbors are ``G.adj[n]`` or ``G[n]``:
1345 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1346 >>> G.add_edge("a", "b", weight=7)
1347 >>> G["a"]
1348 AtlasView({'b': {'weight': 7}})
1349 >>> G = nx.path_graph(4)
1350 >>> [n for n in G[0]]
1351 [1]
1352 """
1353 try:
1354 return iter(self._adj[n])
1355 except KeyError as err:
1356 raise NetworkXError(f"The node {n} is not in the graph.") from err
1358 @cached_property
1359 def edges(self):
1360 """An EdgeView of the Graph as G.edges or G.edges().
1362 edges(self, nbunch=None, data=False, default=None)
1364 The EdgeView provides set-like operations on the edge-tuples
1365 as well as edge attribute lookup. When called, it also provides
1366 an EdgeDataView object which allows control of access to edge
1367 attributes (but does not provide set-like operations).
1368 Hence, `G.edges[u, v]['color']` provides the value of the color
1369 attribute for edge `(u, v)` while
1370 `for (u, v, c) in G.edges.data('color', default='red'):`
1371 iterates through all the edges yielding the color attribute
1372 with default `'red'` if no color attribute exists.
1374 Parameters
1375 ----------
1376 nbunch : single node, container, or all nodes (default= all nodes)
1377 The view will only report edges from these nodes.
1378 data : string or bool, optional (default=False)
1379 The edge attribute returned in 3-tuple (u, v, ddict[data]).
1380 If True, return edge attribute dict in 3-tuple (u, v, ddict).
1381 If False, return 2-tuple (u, v).
1382 default : value, optional (default=None)
1383 Value used for edges that don't have the requested attribute.
1384 Only relevant if data is not True or False.
1386 Returns
1387 -------
1388 edges : EdgeView
1389 A view of edge attributes, usually it iterates over (u, v)
1390 or (u, v, d) tuples of edges, but can also be used for
1391 attribute lookup as `edges[u, v]['foo']`.
1393 Notes
1394 -----
1395 Nodes in nbunch that are not in the graph will be (quietly) ignored.
1396 For directed graphs this returns the out-edges.
1398 Examples
1399 --------
1400 >>> G = nx.path_graph(3) # or MultiGraph, etc
1401 >>> G.add_edge(2, 3, weight=5)
1402 >>> [e for e in G.edges]
1403 [(0, 1), (1, 2), (2, 3)]
1404 >>> G.edges.data() # default data is {} (empty dict)
1405 EdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})])
1406 >>> G.edges.data("weight", default=1)
1407 EdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)])
1408 >>> G.edges([0, 3]) # only edges from these nodes
1409 EdgeDataView([(0, 1), (3, 2)])
1410 >>> G.edges(0) # only edges from node 0
1411 EdgeDataView([(0, 1)])
1412 """
1413 return EdgeView(self)
1415 def get_edge_data(self, u, v, default=None):
1416 """Returns the attribute dictionary associated with edge (u, v).
1418 This is identical to `G[u][v]` except the default is returned
1419 instead of an exception if the edge doesn't exist.
1421 Parameters
1422 ----------
1423 u, v : nodes
1424 default: any Python object (default=None)
1425 Value to return if the edge (u, v) is not found.
1427 Returns
1428 -------
1429 edge_dict : dictionary
1430 The edge attribute dictionary.
1432 Examples
1433 --------
1434 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1435 >>> G[0][1]
1436 {}
1438 Warning: Assigning to `G[u][v]` is not permitted.
1439 But it is safe to assign attributes `G[u][v]['foo']`
1441 >>> G[0][1]["weight"] = 7
1442 >>> G[0][1]["weight"]
1443 7
1444 >>> G[1][0]["weight"]
1445 7
1447 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1448 >>> G.get_edge_data(0, 1) # default edge data is {}
1449 {}
1450 >>> e = (0, 1)
1451 >>> G.get_edge_data(*e) # tuple form
1452 {}
1453 >>> G.get_edge_data("a", "b", default=0) # edge not in graph, return 0
1454 0
1455 """
1456 try:
1457 return self._adj[u][v]
1458 except KeyError:
1459 return default
1461 def adjacency(self):
1462 """Returns an iterator over (node, adjacency dict) tuples for all nodes.
1464 For directed graphs, only outgoing neighbors/adjacencies are included.
1466 Returns
1467 -------
1468 adj_iter : iterator
1469 An iterator over (node, adjacency dictionary) for all nodes in
1470 the graph.
1472 Examples
1473 --------
1474 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1475 >>> [(n, nbrdict) for n, nbrdict in G.adjacency()]
1476 [(0, {1: {}}), (1, {0: {}, 2: {}}), (2, {1: {}, 3: {}}), (3, {2: {}})]
1478 """
1479 return iter(self._adj.items())
1481 @cached_property
1482 def degree(self):
1483 """A DegreeView for the Graph as G.degree or G.degree().
1485 The node degree is the number of edges adjacent to the node.
1486 The weighted node degree is the sum of the edge weights for
1487 edges incident to that node.
1489 This object provides an iterator for (node, degree) as well as
1490 lookup for the degree for a single node.
1492 Parameters
1493 ----------
1494 nbunch : single node, container, or all nodes (default= all nodes)
1495 The view will only report edges incident to these nodes.
1497 weight : string or None, optional (default=None)
1498 The name of an edge attribute that holds the numerical value used
1499 as a weight. If None, then each edge has weight 1.
1500 The degree is the sum of the edge weights adjacent to the node.
1502 Returns
1503 -------
1504 DegreeView or int
1505 If multiple nodes are requested (the default), returns a `DegreeView`
1506 mapping nodes to their degree.
1507 If a single node is requested, returns the degree of the node as an integer.
1509 Examples
1510 --------
1511 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1512 >>> G.degree[0] # node 0 has degree 1
1513 1
1514 >>> list(G.degree([0, 1, 2]))
1515 [(0, 1), (1, 2), (2, 2)]
1516 """
1517 return DegreeView(self)
1519 def clear(self):
1520 """Remove all nodes and edges from the graph.
1522 This also removes the name, and all graph, node, and edge attributes.
1524 Examples
1525 --------
1526 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1527 >>> G.clear()
1528 >>> list(G.nodes)
1529 []
1530 >>> list(G.edges)
1531 []
1533 """
1534 self._adj.clear()
1535 self._node.clear()
1536 self.graph.clear()
1538 def clear_edges(self):
1539 """Remove all edges from the graph without altering nodes.
1541 Examples
1542 --------
1543 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1544 >>> G.clear_edges()
1545 >>> list(G.nodes)
1546 [0, 1, 2, 3]
1547 >>> list(G.edges)
1548 []
1549 """
1550 for neighbours_dict in self._adj.values():
1551 neighbours_dict.clear()
1553 def is_multigraph(self):
1554 """Returns True if graph is a multigraph, False otherwise."""
1555 return False
1557 def is_directed(self):
1558 """Returns True if graph is directed, False otherwise."""
1559 return False
1561 def copy(self, as_view=False):
1562 """Returns a copy of the graph.
1564 The copy method by default returns an independent shallow copy
1565 of the graph and attributes. That is, if an attribute is a
1566 container, that container is shared by the original an the copy.
1567 Use Python's `copy.deepcopy` for new containers.
1569 If `as_view` is True then a view is returned instead of a copy.
1571 Notes
1572 -----
1573 All copies reproduce the graph structure, but data attributes
1574 may be handled in different ways. There are four types of copies
1575 of a graph that people might want.
1577 Deepcopy -- A "deepcopy" copies the graph structure as well as
1578 all data attributes and any objects they might contain.
1579 The entire graph object is new so that changes in the copy
1580 do not affect the original object. (see Python's copy.deepcopy)
1582 Data Reference (Shallow) -- For a shallow copy the graph structure
1583 is copied but the edge, node and graph attribute dicts are
1584 references to those in the original graph. This saves
1585 time and memory but could cause confusion if you change an attribute
1586 in one graph and it changes the attribute in the other.
1587 NetworkX does not provide this level of shallow copy.
1589 Independent Shallow -- This copy creates new independent attribute
1590 dicts and then does a shallow copy of the attributes. That is, any
1591 attributes that are containers are shared between the new graph
1592 and the original. This is exactly what `dict.copy()` provides.
1593 You can obtain this style copy using:
1595 >>> G = nx.path_graph(5)
1596 >>> H = G.copy()
1597 >>> H = G.copy(as_view=False)
1598 >>> H = nx.Graph(G)
1599 >>> H = G.__class__(G)
1601 Fresh Data -- For fresh data, the graph structure is copied while
1602 new empty data attribute dicts are created. The resulting graph
1603 is independent of the original and it has no edge, node or graph
1604 attributes. Fresh copies are not enabled. Instead use:
1606 >>> H = G.__class__()
1607 >>> H.add_nodes_from(G)
1608 >>> H.add_edges_from(G.edges)
1610 View -- Inspired by dict-views, graph-views act like read-only
1611 versions of the original graph, providing a copy of the original
1612 structure without requiring any memory for copying the information.
1614 See the Python copy module for more information on shallow
1615 and deep copies, https://docs.python.org/3/library/copy.html.
1617 Parameters
1618 ----------
1619 as_view : bool, optional (default=False)
1620 If True, the returned graph-view provides a read-only view
1621 of the original graph without actually copying any data.
1623 Returns
1624 -------
1625 G : Graph
1626 A copy of the graph.
1628 See Also
1629 --------
1630 to_directed: return a directed copy of the graph.
1632 Examples
1633 --------
1634 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1635 >>> H = G.copy()
1637 """
1638 if as_view is True:
1639 return nx.graphviews.generic_graph_view(self)
1640 G = self.__class__()
1641 G.graph.update(self.graph)
1642 G.add_nodes_from((n, d.copy()) for n, d in self._node.items())
1643 G.add_edges_from(
1644 (u, v, datadict.copy())
1645 for u, nbrs in self._adj.items()
1646 for v, datadict in nbrs.items()
1647 )
1648 return G
1650 def to_directed(self, as_view=False):
1651 """Returns a directed representation of the graph.
1653 Returns
1654 -------
1655 G : DiGraph
1656 A directed graph with the same name, same nodes, and with
1657 each edge (u, v, data) replaced by two directed edges
1658 (u, v, data) and (v, u, data).
1660 Notes
1661 -----
1662 This returns a "deepcopy" of the edge, node, and
1663 graph attributes which attempts to completely copy
1664 all of the data and references.
1666 This is in contrast to the similar D=DiGraph(G) which returns a
1667 shallow copy of the data.
1669 See the Python copy module for more information on shallow
1670 and deep copies, https://docs.python.org/3/library/copy.html.
1672 Warning: If you have subclassed Graph to use dict-like objects
1673 in the data structure, those changes do not transfer to the
1674 DiGraph created by this method.
1676 Examples
1677 --------
1678 >>> G = nx.Graph() # or MultiGraph, etc
1679 >>> G.add_edge(0, 1)
1680 >>> H = G.to_directed()
1681 >>> list(H.edges)
1682 [(0, 1), (1, 0)]
1684 If already directed, return a (deep) copy
1686 >>> G = nx.DiGraph() # or MultiDiGraph, etc
1687 >>> G.add_edge(0, 1)
1688 >>> H = G.to_directed()
1689 >>> list(H.edges)
1690 [(0, 1)]
1691 """
1692 graph_class = self.to_directed_class()
1693 if as_view is True:
1694 return nx.graphviews.generic_graph_view(self, graph_class)
1695 # deepcopy when not a view
1696 G = graph_class()
1697 G.graph.update(deepcopy(self.graph))
1698 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1699 G.add_edges_from(
1700 (u, v, deepcopy(data))
1701 for u, nbrs in self._adj.items()
1702 for v, data in nbrs.items()
1703 )
1704 return G
1706 def to_undirected(self, as_view=False):
1707 """Returns an undirected copy of the graph.
1709 Parameters
1710 ----------
1711 as_view : bool (optional, default=False)
1712 If True return a view of the original undirected graph.
1714 Returns
1715 -------
1716 G : Graph/MultiGraph
1717 A deepcopy of the graph.
1719 See Also
1720 --------
1721 Graph, copy, add_edge, add_edges_from
1723 Notes
1724 -----
1725 This returns a "deepcopy" of the edge, node, and
1726 graph attributes which attempts to completely copy
1727 all of the data and references.
1729 This is in contrast to the similar `G = nx.DiGraph(D)` which returns a
1730 shallow copy of the data.
1732 See the Python copy module for more information on shallow
1733 and deep copies, https://docs.python.org/3/library/copy.html.
1735 Warning: If you have subclassed DiGraph to use dict-like objects
1736 in the data structure, those changes do not transfer to the
1737 Graph created by this method.
1739 Examples
1740 --------
1741 >>> G = nx.path_graph(2) # or MultiGraph, etc
1742 >>> H = G.to_directed()
1743 >>> list(H.edges)
1744 [(0, 1), (1, 0)]
1745 >>> G2 = H.to_undirected()
1746 >>> list(G2.edges)
1747 [(0, 1)]
1748 """
1749 graph_class = self.to_undirected_class()
1750 if as_view is True:
1751 return nx.graphviews.generic_graph_view(self, graph_class)
1752 # deepcopy when not a view
1753 G = graph_class()
1754 G.graph.update(deepcopy(self.graph))
1755 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1756 G.add_edges_from(
1757 (u, v, deepcopy(d))
1758 for u, nbrs in self._adj.items()
1759 for v, d in nbrs.items()
1760 )
1761 return G
1763 def subgraph(self, nodes):
1764 """Returns a SubGraph view of the subgraph induced on `nodes`.
1766 The induced subgraph of the graph contains the nodes in `nodes`
1767 and the edges between those nodes.
1769 Parameters
1770 ----------
1771 nodes : list, iterable
1772 A container of nodes which will be iterated through once.
1774 Returns
1775 -------
1776 G : SubGraph View
1777 A subgraph view of the graph. The graph structure cannot be
1778 changed but node/edge attributes can and are shared with the
1779 original graph.
1781 Notes
1782 -----
1783 The graph, edge and node attributes are shared with the original graph.
1784 Changes to the graph structure is ruled out by the view, but changes
1785 to attributes are reflected in the original graph.
1787 To create a subgraph with its own copy of the edge/node attributes use:
1788 G.subgraph(nodes).copy()
1790 For an inplace reduction of a graph to a subgraph you can remove nodes:
1791 G.remove_nodes_from([n for n in G if n not in set(nodes)])
1793 Subgraph views are sometimes NOT what you want. In most cases where
1794 you want to do more than simply look at the induced edges, it makes
1795 more sense to just create the subgraph as its own graph with code like:
1797 ::
1799 # Create a subgraph SG based on a (possibly multigraph) G
1800 SG = G.__class__()
1801 SG.add_nodes_from((n, G.nodes[n]) for n in largest_wcc)
1802 if SG.is_multigraph():
1803 SG.add_edges_from((n, nbr, key, d)
1804 for n, nbrs in G.adj.items() if n in largest_wcc
1805 for nbr, keydict in nbrs.items() if nbr in largest_wcc
1806 for key, d in keydict.items())
1807 else:
1808 SG.add_edges_from((n, nbr, d)
1809 for n, nbrs in G.adj.items() if n in largest_wcc
1810 for nbr, d in nbrs.items() if nbr in largest_wcc)
1811 SG.graph.update(G.graph)
1813 Examples
1814 --------
1815 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1816 >>> H = G.subgraph([0, 1, 2])
1817 >>> list(H.edges)
1818 [(0, 1), (1, 2)]
1819 """
1820 induced_nodes = nx.filters.show_nodes(self.nbunch_iter(nodes))
1821 # if already a subgraph, don't make a chain
1822 subgraph = nx.subgraph_view
1823 if hasattr(self, "_NODE_OK"):
1824 return subgraph(
1825 self._graph, filter_node=induced_nodes, filter_edge=self._EDGE_OK
1826 )
1827 return subgraph(self, filter_node=induced_nodes)
1829 def edge_subgraph(self, edges):
1830 """Returns the subgraph induced by the specified edges.
1832 The induced subgraph contains each edge in `edges` and each
1833 node incident to any one of those edges.
1835 Parameters
1836 ----------
1837 edges : iterable
1838 An iterable of edges in this graph.
1840 Returns
1841 -------
1842 G : Graph
1843 An edge-induced subgraph of this graph with the same edge
1844 attributes.
1846 Notes
1847 -----
1848 The graph, edge, and node attributes in the returned subgraph
1849 view are references to the corresponding attributes in the original
1850 graph. The view is read-only.
1852 To create a full graph version of the subgraph with its own copy
1853 of the edge or node attributes, use::
1855 G.edge_subgraph(edges).copy()
1857 Examples
1858 --------
1859 >>> G = nx.path_graph(5)
1860 >>> H = G.edge_subgraph([(0, 1), (3, 4)])
1861 >>> list(H.nodes)
1862 [0, 1, 3, 4]
1863 >>> list(H.edges)
1864 [(0, 1), (3, 4)]
1866 """
1867 return nx.edge_subgraph(self, edges)
1869 def size(self, weight=None):
1870 """Returns the number of edges or total of all edge weights.
1872 Parameters
1873 ----------
1874 weight : string or None, optional (default=None)
1875 The edge attribute that holds the numerical value used
1876 as a weight. If None, then each edge has weight 1.
1878 Returns
1879 -------
1880 size : numeric
1881 The number of edges or
1882 (if weight keyword is provided) the total weight sum.
1884 If weight is None, returns an int. Otherwise a float
1885 (or more general numeric if the weights are more general).
1887 See Also
1888 --------
1889 number_of_edges
1891 Examples
1892 --------
1893 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1894 >>> G.size()
1895 3
1897 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1898 >>> G.add_edge("a", "b", weight=2)
1899 >>> G.add_edge("b", "c", weight=4)
1900 >>> G.size()
1901 2
1902 >>> G.size(weight="weight")
1903 6.0
1904 """
1905 s = sum(d for v, d in self.degree(weight=weight))
1906 # If `weight` is None, the sum of the degrees is guaranteed to be
1907 # even, so we can perform integer division and hence return an
1908 # integer. Otherwise, the sum of the weighted degrees is not
1909 # guaranteed to be an integer, so we perform "real" division.
1910 return s // 2 if weight is None else s / 2
1912 def number_of_edges(self, u=None, v=None):
1913 """Returns the number of edges between two nodes.
1915 Parameters
1916 ----------
1917 u, v : nodes, optional (default=all edges)
1918 If u and v are specified, return the number of edges between
1919 u and v. Otherwise return the total number of all edges.
1921 Returns
1922 -------
1923 nedges : int
1924 The number of edges in the graph. If nodes `u` and `v` are
1925 specified return the number of edges between those nodes. If
1926 the graph is directed, this only returns the number of edges
1927 from `u` to `v`.
1929 See Also
1930 --------
1931 size
1933 Examples
1934 --------
1935 For undirected graphs, this method counts the total number of
1936 edges in the graph:
1938 >>> G = nx.path_graph(4)
1939 >>> G.number_of_edges()
1940 3
1942 If you specify two nodes, this counts the total number of edges
1943 joining the two nodes:
1945 >>> G.number_of_edges(0, 1)
1946 1
1948 For directed graphs, this method can count the total number of
1949 directed edges from `u` to `v`:
1951 >>> G = nx.DiGraph()
1952 >>> G.add_edge(0, 1)
1953 >>> G.add_edge(1, 0)
1954 >>> G.number_of_edges(0, 1)
1955 1
1957 """
1958 if u is None:
1959 return int(self.size())
1960 if v in self._adj[u]:
1961 return 1
1962 return 0
1964 def nbunch_iter(self, nbunch=None):
1965 """Returns an iterator over nodes contained in nbunch that are
1966 also in the graph.
1968 The nodes in nbunch are checked for membership in the graph
1969 and if not are silently ignored.
1971 Parameters
1972 ----------
1973 nbunch : single node, container, or all nodes (default= all nodes)
1974 The view will only report edges incident to these nodes.
1976 Returns
1977 -------
1978 niter : iterator
1979 An iterator over nodes in nbunch that are also in the graph.
1980 If nbunch is None, iterate over all nodes in the graph.
1982 Raises
1983 ------
1984 NetworkXError
1985 If nbunch is not a node or sequence of nodes.
1986 If a node in nbunch is not hashable.
1988 See Also
1989 --------
1990 Graph.__iter__
1992 Notes
1993 -----
1994 When nbunch is an iterator, the returned iterator yields values
1995 directly from nbunch, becoming exhausted when nbunch is exhausted.
1997 To test whether nbunch is a single node, one can use
1998 "if nbunch in self:", even after processing with this routine.
2000 If nbunch is not a node or a (possibly empty) sequence/iterator
2001 or None, a :exc:`NetworkXError` is raised. Also, if any object in
2002 nbunch is not hashable, a :exc:`NetworkXError` is raised.
2003 """
2004 if nbunch is None: # include all nodes via iterator
2005 bunch = iter(self._adj)
2006 elif nbunch in self: # if nbunch is a single node
2007 bunch = iter([nbunch])
2008 else: # if nbunch is a sequence of nodes
2010 def bunch_iter(nlist, adj):
2011 try:
2012 for n in nlist:
2013 if n in adj:
2014 yield n
2015 except TypeError as err:
2016 exc, message = err, err.args[0]
2017 # capture error for non-sequence/iterator nbunch.
2018 if "iter" in message:
2019 exc = NetworkXError(
2020 "nbunch is not a node or a sequence of nodes."
2021 )
2022 # capture error for unhashable node.
2023 if "hashable" in message:
2024 exc = NetworkXError(
2025 f"Node {n} in sequence nbunch is not a valid node."
2026 )
2027 raise exc
2029 bunch = bunch_iter(nbunch, self._adj)
2030 return bunch