Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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"""
11from copy import deepcopy
12from functools import cached_property
14import networkx as nx
15from networkx import convert
16from networkx.classes.coreviews import AdjacencyView
17from networkx.classes.reportviews import DegreeView, EdgeView, NodeView
18from networkx.exception import NetworkXError
20__all__ = ["Graph"]
23class _CachedPropertyResetterAdj:
24 """Data Descriptor class for _adj that resets ``adj`` cached_property when needed
26 This assumes that the ``cached_property`` ``G.adj`` should be reset whenever
27 ``G._adj`` is set to a new value.
29 This object sits on a class and ensures that any instance of that
30 class clears its cached property "adj" whenever the underlying
31 instance attribute "_adj" is set to a new object. It only affects
32 the set process of the obj._adj attribute. All get/del operations
33 act as they normally would.
35 For info on Data Descriptors see: https://docs.python.org/3/howto/descriptor.html
36 """
38 def __set__(self, obj, value):
39 od = obj.__dict__
40 od["_adj"] = value
41 # reset cached properties
42 props = ["adj", "edges", "degree"]
43 for prop in props:
44 if prop in od:
45 del od[prop]
48class _CachedPropertyResetterNode:
49 """Data Descriptor class for _node that resets ``nodes`` cached_property when needed
51 This assumes that the ``cached_property`` ``G.node`` should be reset whenever
52 ``G._node`` is set to a new value.
54 This object sits on a class and ensures that any instance of that
55 class clears its cached property "nodes" whenever the underlying
56 instance attribute "_node" is set to a new object. It only affects
57 the set process of the obj._adj attribute. All get/del operations
58 act as they normally would.
60 For info on Data Descriptors see: https://docs.python.org/3/howto/descriptor.html
61 """
63 def __set__(self, obj, value):
64 od = obj.__dict__
65 od["_node"] = value
66 # reset cached properties
67 if "nodes" in od:
68 del od["nodes"]
71class Graph:
72 """
73 Base class for undirected graphs.
75 A Graph stores nodes and edges with optional data, or attributes.
77 Graphs hold undirected edges. Self loops are allowed but multiple
78 (parallel) edges are not.
80 Nodes can be arbitrary (hashable) Python objects with optional
81 key/value attributes, except that `None` is not allowed as a node.
83 Edges are represented as links between nodes with optional
84 key/value attributes.
86 Parameters
87 ----------
88 incoming_graph_data : input graph (optional, default: None)
89 Data to initialize graph. If None (default) an empty
90 graph is created. The data can be any format that is supported
91 by the to_networkx_graph() function, currently including edge list,
92 dict of dicts, dict of lists, NetworkX graph, 2D NumPy array, SciPy
93 sparse matrix, or PyGraphviz graph.
95 attr : keyword arguments, optional (default= no attributes)
96 Attributes to add to graph as key=value pairs.
98 See Also
99 --------
100 DiGraph
101 MultiGraph
102 MultiDiGraph
104 Examples
105 --------
106 Create an empty graph structure (a "null graph") with no nodes and
107 no edges.
109 >>> G = nx.Graph()
111 G can be grown in several ways.
113 **Nodes:**
115 Add one node at a time:
117 >>> G.add_node(1)
119 Add the nodes from any container (a list, dict, set or
120 even the lines from a file or the nodes from another graph).
122 >>> G.add_nodes_from([2, 3])
123 >>> G.add_nodes_from(range(100, 110))
124 >>> H = nx.path_graph(10)
125 >>> G.add_nodes_from(H)
127 In addition to strings and integers any hashable Python object
128 (except None) can represent a node, e.g. a customized node object,
129 or even another Graph.
131 >>> G.add_node(H)
133 **Edges:**
135 G can also be grown by adding edges.
137 Add one edge,
139 >>> G.add_edge(1, 2)
141 a list of edges,
143 >>> G.add_edges_from([(1, 2), (1, 3)])
145 or a collection of edges,
147 >>> G.add_edges_from(H.edges)
149 If some edges connect nodes not yet in the graph, the nodes
150 are added automatically. There are no errors when adding
151 nodes or edges that already exist.
153 **Attributes:**
155 Each graph, node, and edge can hold key/value attribute pairs
156 in an associated attribute dictionary (the keys must be hashable).
157 By default these are empty, but can be added or changed using
158 add_edge, add_node or direct manipulation of the attribute
159 dictionaries named graph, node and edge respectively.
161 >>> G = nx.Graph(day="Friday")
162 >>> G.graph
163 {'day': 'Friday'}
165 Add node attributes using add_node(), add_nodes_from() or G.nodes
167 >>> G.add_node(1, time="5pm")
168 >>> G.add_nodes_from([3], time="2pm")
169 >>> G.nodes[1]
170 {'time': '5pm'}
171 >>> G.nodes[1]["room"] = 714 # node must exist already to use G.nodes
172 >>> del G.nodes[1]["room"] # remove attribute
173 >>> list(G.nodes(data=True))
174 [(1, {'time': '5pm'}), (3, {'time': '2pm'})]
176 Add edge attributes using add_edge(), add_edges_from(), subscript
177 notation, or G.edges.
179 >>> G.add_edge(1, 2, weight=4.7)
180 >>> G.add_edges_from([(3, 4), (4, 5)], color="red")
181 >>> G.add_edges_from([(1, 2, {"color": "blue"}), (2, 3, {"weight": 8})])
182 >>> G[1][2]["weight"] = 4.7
183 >>> G.edges[1, 2]["weight"] = 4
185 Warning: we protect the graph data structure by making `G.edges` a
186 read-only dict-like structure. However, you can assign to attributes
187 in e.g. `G.edges[1, 2]`. Thus, use 2 sets of brackets to add/change
188 data attributes: `G.edges[1, 2]['weight'] = 4`
189 (For multigraphs: `MG.edges[u, v, key][name] = value`).
191 **Shortcuts:**
193 Many common graph features allow python syntax to speed reporting.
195 >>> 1 in G # check if node in graph
196 True
197 >>> [n for n in G if n < 3] # iterate through nodes
198 [1, 2]
199 >>> len(G) # number of nodes in graph
200 5
202 Often the best way to traverse all edges of a graph is via the neighbors.
203 The neighbors are reported as an adjacency-dict `G.adj` or `G.adjacency()`
205 >>> for n, nbrsdict in G.adjacency():
206 ... for nbr, eattr in nbrsdict.items():
207 ... if "weight" in eattr:
208 ... # Do something useful with the edges
209 ... pass
211 But the edges() method is often more convenient:
213 >>> for u, v, weight in G.edges.data("weight"):
214 ... if weight is not None:
215 ... # Do something useful with the edges
216 ... pass
218 **Reporting:**
220 Simple graph information is obtained using object-attributes and methods.
221 Reporting typically provides views instead of containers to reduce memory
222 usage. The views update as the graph is updated similarly to dict-views.
223 The objects `nodes`, `edges` and `adj` provide access to data attributes
224 via lookup (e.g. `nodes[n]`, `edges[u, v]`, `adj[u][v]`) and iteration
225 (e.g. `nodes.items()`, `nodes.data('color')`,
226 `nodes.data('color', default='blue')` and similarly for `edges`)
227 Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`.
229 For details on these and other miscellaneous methods, see below.
231 **Subclasses (Advanced):**
233 The Graph class uses a dict-of-dict-of-dict data structure.
234 The outer dict (node_dict) holds adjacency information keyed by node.
235 The next dict (adjlist_dict) represents the adjacency information and holds
236 edge data keyed by neighbor. The inner dict (edge_attr_dict) represents
237 the edge data and holds edge attribute values keyed by attribute names.
239 Each of these three dicts can be replaced in a subclass by a user defined
240 dict-like object. In general, the dict-like features should be
241 maintained but extra features can be added. To replace one of the
242 dicts create a new graph class by changing the class(!) variable
243 holding the factory for that dict-like structure.
245 node_dict_factory : function, (default: dict)
246 Factory function to be used to create the dict containing node
247 attributes, keyed by node id.
248 It should require no arguments and return a dict-like object
250 node_attr_dict_factory: function, (default: dict)
251 Factory function to be used to create the node attribute
252 dict which holds attribute values keyed by attribute name.
253 It should require no arguments and return a dict-like object
255 adjlist_outer_dict_factory : function, (default: dict)
256 Factory function to be used to create the outer-most dict
257 in the data structure that holds adjacency info keyed by node.
258 It should require no arguments and return a dict-like object.
260 adjlist_inner_dict_factory : function, (default: dict)
261 Factory function to be used to create the adjacency list
262 dict which holds edge data keyed by neighbor.
263 It should require no arguments and return a dict-like object
265 edge_attr_dict_factory : function, (default: dict)
266 Factory function to be used to create the edge attribute
267 dict which holds attribute values keyed by attribute name.
268 It should require no arguments and return a dict-like object.
270 graph_attr_dict_factory : function, (default: dict)
271 Factory function to be used to create the graph attribute
272 dict which holds attribute values keyed by attribute name.
273 It should require no arguments and return a dict-like object.
275 Typically, if your extension doesn't impact the data structure all
276 methods will inherit without issue except: `to_directed/to_undirected`.
277 By default these methods create a DiGraph/Graph class and you probably
278 want them to create your extension of a DiGraph/Graph. To facilitate
279 this we define two class variables that you can set in your subclass.
281 to_directed_class : callable, (default: DiGraph or MultiDiGraph)
282 Class to create a new graph structure in the `to_directed` method.
283 If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used.
285 to_undirected_class : callable, (default: Graph or MultiGraph)
286 Class to create a new graph structure in the `to_undirected` method.
287 If `None`, a NetworkX class (Graph or MultiGraph) is used.
289 **Subclassing Example**
291 Create a low memory graph class that effectively disallows edge
292 attributes by using a single attribute dict for all edges.
293 This reduces the memory used, but you lose edge attributes.
295 >>> class ThinGraph(nx.Graph):
296 ... all_edge_dict = {"weight": 1}
297 ...
298 ... def single_edge_dict(self):
299 ... return self.all_edge_dict
300 ...
301 ... edge_attr_dict_factory = single_edge_dict
302 >>> G = ThinGraph()
303 >>> G.add_edge(2, 1)
304 >>> G[2][1]
305 {'weight': 1}
306 >>> G.add_edge(2, 2)
307 >>> G[2][1] is G[2][2]
308 True
309 """
311 __networkx_backend__ = "networkx"
313 _adj = _CachedPropertyResetterAdj()
314 _node = _CachedPropertyResetterNode()
316 node_dict_factory = dict
317 node_attr_dict_factory = dict
318 adjlist_outer_dict_factory = dict
319 adjlist_inner_dict_factory = dict
320 edge_attr_dict_factory = dict
321 graph_attr_dict_factory = dict
323 def to_directed_class(self):
324 """Returns the class to use for empty directed copies.
326 If you subclass the base classes, use this to designate
327 what directed class to use for `to_directed()` copies.
328 """
329 return nx.DiGraph
331 def to_undirected_class(self):
332 """Returns the class to use for empty undirected copies.
334 If you subclass the base classes, use this to designate
335 what directed class to use for `to_directed()` copies.
336 """
337 return Graph
339 # This __new__ method just does what Python itself does automatically.
340 # We include it here as part of the dispatchable/backend interface.
341 # If your goal is to understand how the graph classes work, you can ignore
342 # this method, even when subclassing the base classes. If you are subclassing
343 # in order to provide a backend that allows class instantiation, this method
344 # can be overridden to return your own backend graph class.
345 @nx._dispatchable(name="graph__new__", graphs=None, returns_graph=True)
346 def __new__(cls, incoming_graph_data=None, **attr):
347 return object.__new__(cls)
349 def __init__(self, incoming_graph_data=None, **attr):
350 """Initialize a graph with edges, name, or graph attributes.
352 Parameters
353 ----------
354 incoming_graph_data : input graph (optional, default: None)
355 Data to initialize graph. If None (default) an empty
356 graph is created. The data can be an edge list, or any
357 NetworkX graph object. If the corresponding optional Python
358 packages are installed the data can also be a 2D NumPy array, a
359 SciPy sparse array, or a PyGraphviz graph.
361 attr : keyword arguments, optional (default= no attributes)
362 Attributes to add to graph as key=value pairs.
364 See Also
365 --------
366 convert
368 Examples
369 --------
370 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
371 >>> G = nx.Graph(name="my graph")
372 >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges
373 >>> G = nx.Graph(e)
375 Arbitrary graph attribute pairs (key=value) may be assigned
377 >>> G = nx.Graph(e, day="Friday")
378 >>> G.graph
379 {'day': 'Friday'}
381 """
382 self.graph = self.graph_attr_dict_factory() # dictionary for graph attributes
383 self._node = self.node_dict_factory() # empty node attribute dict
384 self._adj = self.adjlist_outer_dict_factory() # empty adjacency dict
385 self.__networkx_cache__ = {}
386 # attempt to load graph with data
387 if incoming_graph_data is not None:
388 convert.to_networkx_graph(incoming_graph_data, create_using=self)
389 # load graph attributes (must be after convert)
390 attr.pop("backend", None) # Ignore explicit `backend="networkx"`
391 self.graph.update(attr)
393 @cached_property
394 def adj(self):
395 """Graph adjacency object holding the neighbors of each node.
397 This object is a read-only dict-like structure with node keys
398 and neighbor-dict values. The neighbor-dict is keyed by neighbor
399 to the edge-data-dict. So `G.adj[3][2]['color'] = 'blue'` sets
400 the color of the edge `(3, 2)` to `"blue"`.
402 Iterating over G.adj behaves like a dict. Useful idioms include
403 `for nbr, datadict in G.adj[n].items():`.
405 The neighbor information is also provided by subscripting the graph.
406 So `for nbr, foovalue in G[node].data('foo', default=1):` works.
408 For directed graphs, `G.adj` holds outgoing (successor) info.
409 """
410 return AdjacencyView(self._adj)
412 @property
413 def name(self):
414 """String identifier of the graph.
416 This graph attribute appears in the attribute dict G.graph
417 keyed by the string `"name"`. as well as an attribute (technically
418 a property) `G.name`. This is entirely user controlled.
419 """
420 return self.graph.get("name", "")
422 @name.setter
423 def name(self, s):
424 self.graph["name"] = s
425 nx._clear_cache(self)
427 def __str__(self):
428 """Returns a short summary of the graph.
430 Returns
431 -------
432 info : string
433 Graph information including the graph name (if any), graph type, and the
434 number of nodes and edges.
436 Examples
437 --------
438 >>> G = nx.Graph(name="foo")
439 >>> str(G)
440 "Graph named 'foo' with 0 nodes and 0 edges"
442 >>> G = nx.path_graph(3)
443 >>> str(G)
444 'Graph with 3 nodes and 2 edges'
446 """
447 return "".join(
448 [
449 type(self).__name__,
450 f" named {self.name!r}" if self.name else "",
451 f" with {self.number_of_nodes()} nodes and {self.number_of_edges()} edges",
452 ]
453 )
455 def __iter__(self):
456 """Iterate over the nodes. Use: 'for n in G'.
458 Returns
459 -------
460 niter : iterator
461 An iterator over all nodes in the graph.
463 Examples
464 --------
465 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
466 >>> [n for n in G]
467 [0, 1, 2, 3]
468 >>> list(G)
469 [0, 1, 2, 3]
470 """
471 return iter(self._node)
473 def __contains__(self, n):
474 """Returns True if n is a node, False otherwise. Use: 'n in G'.
476 Examples
477 --------
478 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
479 >>> 1 in G
480 True
481 """
482 try:
483 return n in self._node
484 except TypeError:
485 return False
487 def __len__(self):
488 """Returns the number of nodes in the graph. Use: 'len(G)'.
490 Returns
491 -------
492 nnodes : int
493 The number of nodes in the graph.
495 See Also
496 --------
497 number_of_nodes: identical method
498 order: identical method
500 Examples
501 --------
502 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
503 >>> len(G)
504 4
506 """
507 return len(self._node)
509 def __getitem__(self, n):
510 """Returns a dict of neighbors of node n. Use: 'G[n]'.
512 Parameters
513 ----------
514 n : node
515 A node in the graph.
517 Returns
518 -------
519 adj_dict : dictionary
520 The adjacency dictionary for nodes connected to n.
522 Notes
523 -----
524 G[n] is the same as G.adj[n] and similar to G.neighbors(n)
525 (which is an iterator over G.adj[n])
527 Examples
528 --------
529 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
530 >>> G[0]
531 AtlasView({1: {}})
532 """
533 return self.adj[n]
535 def add_node(self, node_for_adding, **attr):
536 """Add a single node `node_for_adding` and update node attributes.
538 Parameters
539 ----------
540 node_for_adding : node
541 A node can be any hashable Python object except None.
542 attr : keyword arguments, optional
543 Set or change node attributes using key=value.
545 See Also
546 --------
547 add_nodes_from
549 Examples
550 --------
551 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
552 >>> G.add_node(1)
553 >>> G.add_node("Hello")
554 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
555 >>> G.add_node(K3)
556 >>> G.number_of_nodes()
557 3
559 Use keywords set/change node attributes:
561 >>> G.add_node(1, size=10)
562 >>> G.add_node(3, weight=0.4, UTM=("13S", 382871, 3972649))
564 Notes
565 -----
566 A hashable object is one that can be used as a key in a Python
567 dictionary. This includes strings, numbers, tuples of strings
568 and numbers, etc.
570 On many platforms hashable items also include mutables such as
571 NetworkX Graphs, though one should be careful that the hash
572 doesn't change on mutables.
573 """
574 if node_for_adding not in self._node:
575 if node_for_adding is None:
576 raise ValueError("None cannot be a node")
577 self._adj[node_for_adding] = self.adjlist_inner_dict_factory()
578 attr_dict = self._node[node_for_adding] = self.node_attr_dict_factory()
579 attr_dict.update(attr)
580 else: # update attr even if node already exists
581 self._node[node_for_adding].update(attr)
582 nx._clear_cache(self)
584 def add_nodes_from(self, nodes_for_adding, **attr):
585 """Add multiple nodes.
587 Parameters
588 ----------
589 nodes_for_adding : iterable container
590 A container of nodes (list, dict, set, etc.).
591 OR
592 A container of (node, attribute dict) tuples.
593 Node attributes are updated using the attribute dict.
594 attr : keyword arguments, optional (default= no attributes)
595 Update attributes for all nodes in nodes.
596 Node attributes specified in nodes as a tuple take
597 precedence over attributes specified via keyword arguments.
599 See Also
600 --------
601 add_node
603 Notes
604 -----
605 When adding nodes from an iterator over the graph you are changing,
606 a `RuntimeError` can be raised with message:
607 `RuntimeError: dictionary changed size during iteration`. This
608 happens when the graph's underlying dictionary is modified during
609 iteration. To avoid this error, evaluate the iterator into a separate
610 object, e.g. by using `list(iterator_of_nodes)`, and pass this
611 object to `G.add_nodes_from`.
613 Examples
614 --------
615 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
616 >>> G.add_nodes_from("Hello")
617 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
618 >>> G.add_nodes_from(K3)
619 >>> sorted(G.nodes(), key=str)
620 [0, 1, 2, 'H', 'e', 'l', 'o']
622 Use keywords to update specific node attributes for every node.
624 >>> G.add_nodes_from([1, 2], size=10)
625 >>> G.add_nodes_from([3, 4], weight=0.4)
627 Use (node, attrdict) tuples to update attributes for specific nodes.
629 >>> G.add_nodes_from([(1, dict(size=11)), (2, {"color": "blue"})])
630 >>> G.nodes[1]["size"]
631 11
632 >>> H = nx.Graph()
633 >>> H.add_nodes_from(G.nodes(data=True))
634 >>> H.nodes[1]["size"]
635 11
637 Evaluate an iterator over a graph if using it to modify the same graph
639 >>> G = nx.Graph([(0, 1), (1, 2), (3, 4)])
640 >>> # wrong way - will raise RuntimeError
641 >>> # G.add_nodes_from(n + 1 for n in G.nodes)
642 >>> # correct way
643 >>> G.add_nodes_from(list(n + 1 for n in G.nodes))
644 """
645 for n in nodes_for_adding:
646 try:
647 newnode = n not in self._node
648 newdict = attr
649 except TypeError:
650 n, ndict = n
651 newnode = n not in self._node
652 newdict = attr.copy()
653 newdict.update(ndict)
654 if newnode:
655 if n is None:
656 raise ValueError("None cannot be a node")
657 self._adj[n] = self.adjlist_inner_dict_factory()
658 self._node[n] = self.node_attr_dict_factory()
659 self._node[n].update(newdict)
660 nx._clear_cache(self)
662 def remove_node(self, n):
663 """Remove node n.
665 Removes the node n and all adjacent edges.
666 Attempting to remove a nonexistent node will raise an exception.
668 Parameters
669 ----------
670 n : node
671 A node in the graph
673 Raises
674 ------
675 NetworkXError
676 If n is not in the graph.
678 See Also
679 --------
680 remove_nodes_from
682 Examples
683 --------
684 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
685 >>> list(G.edges)
686 [(0, 1), (1, 2)]
687 >>> G.remove_node(1)
688 >>> list(G.edges)
689 []
691 """
692 adj = self._adj
693 try:
694 nbrs = list(adj[n]) # list handles self-loops (allows mutation)
695 del self._node[n]
696 except KeyError as err: # NetworkXError if n not in self
697 raise NetworkXError(f"The node {n} is not in the graph.") from err
698 for u in nbrs:
699 del adj[u][n] # remove all edges n-u in graph
700 del adj[n] # now remove node
701 nx._clear_cache(self)
703 def remove_nodes_from(self, nodes):
704 """Remove multiple nodes.
706 Parameters
707 ----------
708 nodes : iterable container
709 A container of nodes (list, dict, set, etc.). If a node
710 in the container is not in the graph it is silently
711 ignored.
713 See Also
714 --------
715 remove_node
717 Notes
718 -----
719 When removing nodes from an iterator over the graph you are changing,
720 a `RuntimeError` will be raised with message:
721 `RuntimeError: dictionary changed size during iteration`. This
722 happens when the graph's underlying dictionary is modified during
723 iteration. To avoid this error, evaluate the iterator into a separate
724 object, e.g. by using `list(iterator_of_nodes)`, and pass this
725 object to `G.remove_nodes_from`.
727 Examples
728 --------
729 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
730 >>> e = list(G.nodes)
731 >>> e
732 [0, 1, 2]
733 >>> G.remove_nodes_from(e)
734 >>> list(G.nodes)
735 []
737 Evaluate an iterator over a graph if using it to modify the same graph
739 >>> G = nx.Graph([(0, 1), (1, 2), (3, 4)])
740 >>> # this command will fail, as the graph's dict is modified during iteration
741 >>> # G.remove_nodes_from(n for n in G.nodes if n < 2)
742 >>> # this command will work, since the dictionary underlying graph is not modified
743 >>> G.remove_nodes_from(list(n for n in G.nodes if n < 2))
744 """
745 adj = self._adj
746 for n in nodes:
747 try:
748 del self._node[n]
749 for u in list(adj[n]): # list handles self-loops
750 del adj[u][n] # (allows mutation of dict in loop)
751 del adj[n]
752 except KeyError:
753 pass
754 nx._clear_cache(self)
756 @cached_property
757 def nodes(self):
758 """A NodeView of the Graph as G.nodes or G.nodes().
760 Can be used as `G.nodes` for data lookup and for set-like operations.
761 Can also be used as `G.nodes(data='color', default=None)` to return a
762 NodeDataView which reports specific node data but no set operations.
763 It presents a dict-like interface as well with `G.nodes.items()`
764 iterating over `(node, nodedata)` 2-tuples and `G.nodes[3]['foo']`
765 providing the value of the `foo` attribute for node `3`. In addition,
766 a view `G.nodes.data('foo')` provides a dict-like interface to the
767 `foo` attribute of each node. `G.nodes.data('foo', default=1)`
768 provides a default for nodes that do not have attribute `foo`.
770 Parameters
771 ----------
772 data : string or bool, optional (default=False)
773 The node attribute returned in 2-tuple (n, ddict[data]).
774 If True, return entire node attribute dict as (n, ddict).
775 If False, return just the nodes n.
777 default : value, optional (default=None)
778 Value used for nodes that don't have the requested attribute.
779 Only relevant if data is not True or False.
781 Returns
782 -------
783 NodeView
784 Allows set-like operations over the nodes as well as node
785 attribute dict lookup and calling to get a NodeDataView.
786 A NodeDataView iterates over `(n, data)` and has no set operations.
787 A NodeView iterates over `n` and includes set operations.
789 When called, if data is False, an iterator over nodes.
790 Otherwise an iterator of 2-tuples (node, attribute value)
791 where the attribute is specified in `data`.
792 If data is True then the attribute becomes the
793 entire data dictionary.
795 Notes
796 -----
797 If your node data is not needed, it is simpler and equivalent
798 to use the expression ``for n in G``, or ``list(G)``.
800 Examples
801 --------
802 There are two simple ways of getting a list of all nodes in the graph:
804 >>> G = nx.path_graph(3)
805 >>> list(G.nodes)
806 [0, 1, 2]
807 >>> list(G)
808 [0, 1, 2]
810 To get the node data along with the nodes:
812 >>> G.add_node(1, time="5pm")
813 >>> G.nodes[0]["foo"] = "bar"
814 >>> list(G.nodes(data=True))
815 [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})]
816 >>> list(G.nodes.data())
817 [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})]
819 >>> list(G.nodes(data="foo"))
820 [(0, 'bar'), (1, None), (2, None)]
821 >>> list(G.nodes.data("foo"))
822 [(0, 'bar'), (1, None), (2, None)]
824 >>> list(G.nodes(data="time"))
825 [(0, None), (1, '5pm'), (2, None)]
826 >>> list(G.nodes.data("time"))
827 [(0, None), (1, '5pm'), (2, None)]
829 >>> list(G.nodes(data="time", default="Not Available"))
830 [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')]
831 >>> list(G.nodes.data("time", default="Not Available"))
832 [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')]
834 If some of your nodes have an attribute and the rest are assumed
835 to have a default attribute value you can create a dictionary
836 from node/attribute pairs using the `default` keyword argument
837 to guarantee the value is never None::
839 >>> G = nx.Graph()
840 >>> G.add_node(0)
841 >>> G.add_node(1, weight=2)
842 >>> G.add_node(2, weight=3)
843 >>> dict(G.nodes(data="weight", default=1))
844 {0: 1, 1: 2, 2: 3}
846 """
847 return NodeView(self)
849 def number_of_nodes(self):
850 """Returns the number of nodes in the graph.
852 Returns
853 -------
854 nnodes : int
855 The number of nodes in the graph.
857 See Also
858 --------
859 order: identical method
860 __len__: identical method
862 Examples
863 --------
864 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
865 >>> G.number_of_nodes()
866 3
867 """
868 return len(self._node)
870 def order(self):
871 """Returns the number of nodes in the graph.
873 Returns
874 -------
875 nnodes : int
876 The number of nodes in the graph.
878 See Also
879 --------
880 number_of_nodes: identical method
881 __len__: identical method
883 Examples
884 --------
885 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
886 >>> G.order()
887 3
888 """
889 return len(self._node)
891 def has_node(self, n):
892 """Returns True if the graph contains the node n.
894 Identical to `n in G`
896 Parameters
897 ----------
898 n : node
900 Examples
901 --------
902 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
903 >>> G.has_node(0)
904 True
906 It is more readable and simpler to use
908 >>> 0 in G
909 True
911 """
912 try:
913 return n in self._node
914 except TypeError:
915 return False
917 def add_edge(self, u_of_edge, v_of_edge, **attr):
918 """Add an edge between u and v.
920 The nodes u and v will be automatically added if they are
921 not already in the graph.
923 Edge attributes can be specified with keywords or by directly
924 accessing the edge's attribute dictionary. See examples below.
926 Parameters
927 ----------
928 u_of_edge, v_of_edge : nodes
929 Nodes can be, for example, strings or numbers.
930 Nodes must be hashable (and not None) Python objects.
931 attr : keyword arguments, optional
932 Edge data (or labels or objects) can be assigned using
933 keyword arguments.
935 See Also
936 --------
937 add_edges_from : add a collection of edges
939 Notes
940 -----
941 Adding an edge that already exists updates the edge data.
943 Many NetworkX algorithms designed for weighted graphs use
944 an edge attribute (by default `weight`) to hold a numerical value.
946 Examples
947 --------
948 The following all add the edge e=(1, 2) to graph G:
950 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
951 >>> e = (1, 2)
952 >>> G.add_edge(1, 2) # explicit two-node form
953 >>> G.add_edge(*e) # single edge as tuple of two nodes
954 >>> G.add_edges_from([(1, 2)]) # add edges from iterable container
956 Associate data to edges using keywords:
958 >>> G.add_edge(1, 2, weight=3)
959 >>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7)
961 For non-string attribute keys, use subscript notation.
963 >>> G.add_edge(1, 2)
964 >>> G[1][2].update({0: 5})
965 >>> G.edges[1, 2].update({0: 5})
966 """
967 u, v = u_of_edge, v_of_edge
968 # add nodes
969 if u not in self._node:
970 if u is None:
971 raise ValueError("None cannot be a node")
972 self._adj[u] = self.adjlist_inner_dict_factory()
973 self._node[u] = self.node_attr_dict_factory()
974 if v not in self._node:
975 if v is None:
976 raise ValueError("None cannot be a node")
977 self._adj[v] = self.adjlist_inner_dict_factory()
978 self._node[v] = self.node_attr_dict_factory()
979 # add the edge
980 datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
981 datadict.update(attr)
982 self._adj[u][v] = datadict
983 self._adj[v][u] = datadict
984 nx._clear_cache(self)
986 def add_edges_from(self, ebunch_to_add, **attr):
987 """Add all the edges in ebunch_to_add.
989 Parameters
990 ----------
991 ebunch_to_add : container of edges
992 Each edge given in the container will be added to the
993 graph. The edges must be given as 2-tuples (u, v) or
994 3-tuples (u, v, d) where d is a dictionary containing edge data.
995 attr : keyword arguments, optional
996 Edge data (or labels or objects) can be assigned using
997 keyword arguments.
999 See Also
1000 --------
1001 add_edge : add a single edge
1002 add_weighted_edges_from : convenient way to add weighted edges
1004 Notes
1005 -----
1006 Adding the same edge twice has no effect but any edge data
1007 will be updated when each duplicate edge is added.
1009 Edge attributes specified in an ebunch take precedence over
1010 attributes specified via keyword arguments.
1012 When adding edges from an iterator over the graph you are changing,
1013 a `RuntimeError` can be raised with message:
1014 `RuntimeError: dictionary changed size during iteration`. This
1015 happens when the graph's underlying dictionary is modified during
1016 iteration. To avoid this error, evaluate the iterator into a separate
1017 object, e.g. by using `list(iterator_of_edges)`, and pass this
1018 object to `G.add_edges_from`.
1020 Examples
1021 --------
1022 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1023 >>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples
1024 >>> e = zip(range(0, 3), range(1, 4))
1025 >>> G.add_edges_from(e) # Add the path graph 0-1-2-3
1027 Associate data to edges
1029 >>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
1030 >>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898")
1032 Evaluate an iterator over a graph if using it to modify the same graph
1034 >>> G = nx.Graph([(1, 2), (2, 3), (3, 4)])
1035 >>> # Grow graph by one new node, adding edges to all existing nodes.
1036 >>> # wrong way - will raise RuntimeError
1037 >>> # G.add_edges_from(((5, n) for n in G.nodes))
1038 >>> # correct way - note that there will be no self-edge for node 5
1039 >>> G.add_edges_from(list((5, n) for n in G.nodes))
1040 """
1041 for e in ebunch_to_add:
1042 ne = len(e)
1043 if ne == 3:
1044 u, v, dd = e
1045 elif ne == 2:
1046 u, v = e
1047 dd = {} # doesn't need edge_attr_dict_factory
1048 else:
1049 raise NetworkXError(f"Edge tuple {e} must be a 2-tuple or 3-tuple.")
1050 if u not in self._node:
1051 if u is None:
1052 raise ValueError("None cannot be a node")
1053 self._adj[u] = self.adjlist_inner_dict_factory()
1054 self._node[u] = self.node_attr_dict_factory()
1055 if v not in self._node:
1056 if v is None:
1057 raise ValueError("None cannot be a node")
1058 self._adj[v] = self.adjlist_inner_dict_factory()
1059 self._node[v] = self.node_attr_dict_factory()
1060 datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
1061 datadict.update(attr)
1062 datadict.update(dd)
1063 self._adj[u][v] = datadict
1064 self._adj[v][u] = datadict
1065 nx._clear_cache(self)
1067 def add_weighted_edges_from(self, ebunch_to_add, weight="weight", **attr):
1068 """Add weighted edges in `ebunch_to_add` with specified weight attr
1070 Parameters
1071 ----------
1072 ebunch_to_add : container of edges
1073 Each edge given in the list or container will be added
1074 to the graph. The edges must be given as 3-tuples (u, v, w)
1075 where w is a number.
1076 weight : string, optional (default= 'weight')
1077 The attribute name for the edge weights to be added.
1078 attr : keyword arguments, optional (default= no attributes)
1079 Edge attributes to add/update for all edges.
1081 See Also
1082 --------
1083 add_edge : add a single edge
1084 add_edges_from : add multiple edges
1086 Notes
1087 -----
1088 Adding the same edge twice for Graph/DiGraph simply updates
1089 the edge data. For MultiGraph/MultiDiGraph, duplicate edges
1090 are stored.
1092 When adding edges from an iterator over the graph you are changing,
1093 a `RuntimeError` can be raised with message:
1094 `RuntimeError: dictionary changed size during iteration`. This
1095 happens when the graph's underlying dictionary is modified during
1096 iteration. To avoid this error, evaluate the iterator into a separate
1097 object, e.g. by using `list(iterator_of_edges)`, and pass this
1098 object to `G.add_weighted_edges_from`.
1100 Examples
1101 --------
1102 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1103 >>> G.add_weighted_edges_from([(0, 1, 3.0), (1, 2, 7.5)])
1105 Evaluate an iterator over edges before passing it
1107 >>> G = nx.Graph([(1, 2), (2, 3), (3, 4)])
1108 >>> weight = 0.1
1109 >>> # Grow graph by one new node, adding edges to all existing nodes.
1110 >>> # wrong way - will raise RuntimeError
1111 >>> # G.add_weighted_edges_from(((5, n, weight) for n in G.nodes))
1112 >>> # correct way - note that there will be no self-edge for node 5
1113 >>> G.add_weighted_edges_from(list((5, n, weight) for n in G.nodes))
1114 """
1115 self.add_edges_from(((u, v, {weight: d}) for u, v, d in ebunch_to_add), **attr)
1116 nx._clear_cache(self)
1118 def remove_edge(self, u, v):
1119 """Remove the edge between u and v.
1121 Parameters
1122 ----------
1123 u, v : nodes
1124 Remove the edge between nodes u and v.
1126 Raises
1127 ------
1128 NetworkXError
1129 If there is not an edge between u and v.
1131 See Also
1132 --------
1133 remove_edges_from : remove a collection of edges
1135 Examples
1136 --------
1137 >>> G = nx.path_graph(4) # or DiGraph, etc
1138 >>> G.remove_edge(0, 1)
1139 >>> e = (1, 2)
1140 >>> G.remove_edge(*e) # unpacks e from an edge tuple
1141 >>> e = (2, 3, {"weight": 7}) # an edge with attribute data
1142 >>> G.remove_edge(*e[:2]) # select first part of edge tuple
1143 """
1144 try:
1145 del self._adj[u][v]
1146 if u != v: # self-loop needs only one entry removed
1147 del self._adj[v][u]
1148 except KeyError as err:
1149 raise NetworkXError(f"The edge {u}-{v} is not in the graph") from err
1150 nx._clear_cache(self)
1152 def remove_edges_from(self, ebunch):
1153 """Remove all edges specified in ebunch.
1155 Parameters
1156 ----------
1157 ebunch: list or container of edge tuples
1158 Each edge given in the list or container will be removed
1159 from the graph. The edges can be:
1161 - 2-tuples (u, v) edge between u and v.
1162 - 3-tuples (u, v, k) where k is ignored.
1164 See Also
1165 --------
1166 remove_edge : remove a single edge
1168 Notes
1169 -----
1170 Will fail silently if an edge in ebunch is not in the graph.
1172 Examples
1173 --------
1174 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1175 >>> ebunch = [(1, 2), (2, 3)]
1176 >>> G.remove_edges_from(ebunch)
1177 """
1178 adj = self._adj
1179 for e in ebunch:
1180 u, v = e[:2] # ignore edge data if present
1181 if u in adj and v in adj[u]:
1182 del adj[u][v]
1183 if u != v: # self loop needs only one entry removed
1184 del adj[v][u]
1185 nx._clear_cache(self)
1187 def update(self, edges=None, nodes=None):
1188 """Update the graph using nodes/edges/graphs as input.
1190 Like dict.update, this method takes a graph as input, adding the
1191 graph's nodes and edges to this graph. It can also take two inputs:
1192 edges and nodes. Finally it can take either edges or nodes.
1193 To specify only nodes the keyword `nodes` must be used.
1195 The collections of edges and nodes are treated similarly to
1196 the add_edges_from/add_nodes_from methods. When iterated, they
1197 should yield 2-tuples (u, v) or 3-tuples (u, v, datadict).
1199 Parameters
1200 ----------
1201 edges : Graph object, collection of edges, or None
1202 The first parameter can be a graph or some edges. If it has
1203 attributes `nodes` and `edges`, then it is taken to be a
1204 Graph-like object and those attributes are used as collections
1205 of nodes and edges to be added to the graph.
1206 If the first parameter does not have those attributes, it is
1207 treated as a collection of edges and added to the graph.
1208 If the first argument is None, no edges are added.
1209 nodes : collection of nodes, or None
1210 The second parameter is treated as a collection of nodes
1211 to be added to the graph unless it is None.
1212 If `edges is None` and `nodes is None` an exception is raised.
1213 If the first parameter is a Graph, then `nodes` is ignored.
1215 Examples
1216 --------
1217 >>> G = nx.path_graph(5)
1218 >>> G.update(nx.complete_graph(range(4, 10)))
1219 >>> from itertools import combinations
1220 >>> edges = (
1221 ... (u, v, {"power": u * v})
1222 ... for u, v in combinations(range(10, 20), 2)
1223 ... if u * v < 225
1224 ... )
1225 >>> nodes = [1000] # for singleton, use a container
1226 >>> G.update(edges, nodes)
1228 Notes
1229 -----
1230 It you want to update the graph using an adjacency structure
1231 it is straightforward to obtain the edges/nodes from adjacency.
1232 The following examples provide common cases, your adjacency may
1233 be slightly different and require tweaks of these examples::
1235 >>> # dict-of-set/list/tuple
1236 >>> adj = {1: {2, 3}, 2: {1, 3}, 3: {1, 2}}
1237 >>> e = [(u, v) for u, nbrs in adj.items() for v in nbrs]
1238 >>> G.update(edges=e, nodes=adj)
1240 >>> DG = nx.DiGraph()
1241 >>> # dict-of-dict-of-attribute
1242 >>> adj = {1: {2: 1.3, 3: 0.7}, 2: {1: 1.4}, 3: {1: 0.7}}
1243 >>> e = [
1244 ... (u, v, {"weight": d})
1245 ... for u, nbrs in adj.items()
1246 ... for v, d in nbrs.items()
1247 ... ]
1248 >>> DG.update(edges=e, nodes=adj)
1250 >>> # dict-of-dict-of-dict
1251 >>> adj = {1: {2: {"weight": 1.3}, 3: {"color": 0.7, "weight": 1.2}}}
1252 >>> e = [
1253 ... (u, v, {"weight": d})
1254 ... for u, nbrs in adj.items()
1255 ... for v, d in nbrs.items()
1256 ... ]
1257 >>> DG.update(edges=e, nodes=adj)
1259 >>> # predecessor adjacency (dict-of-set)
1260 >>> pred = {1: {2, 3}, 2: {3}, 3: {3}}
1261 >>> e = [(v, u) for u, nbrs in pred.items() for v in nbrs]
1263 >>> # MultiGraph dict-of-dict-of-dict-of-attribute
1264 >>> MDG = nx.MultiDiGraph()
1265 >>> adj = {
1266 ... 1: {2: {0: {"weight": 1.3}, 1: {"weight": 1.2}}},
1267 ... 3: {2: {0: {"weight": 0.7}}},
1268 ... }
1269 >>> e = [
1270 ... (u, v, ekey, d)
1271 ... for u, nbrs in adj.items()
1272 ... for v, keydict in nbrs.items()
1273 ... for ekey, d in keydict.items()
1274 ... ]
1275 >>> MDG.update(edges=e)
1277 See Also
1278 --------
1279 add_edges_from: add multiple edges to a graph
1280 add_nodes_from: add multiple nodes to a graph
1281 """
1282 if edges is not None:
1283 if nodes is not None:
1284 self.add_nodes_from(nodes)
1285 self.add_edges_from(edges)
1286 else:
1287 # check if edges is a Graph object
1288 try:
1289 graph_nodes = edges.nodes
1290 graph_edges = edges.edges
1291 except AttributeError:
1292 # edge not Graph-like
1293 self.add_edges_from(edges)
1294 else: # edges is Graph-like
1295 self.add_nodes_from(graph_nodes.data())
1296 self.add_edges_from(graph_edges.data())
1297 self.graph.update(edges.graph)
1298 elif nodes is not None:
1299 self.add_nodes_from(nodes)
1300 else:
1301 raise NetworkXError("update needs nodes or edges input")
1303 def has_edge(self, u, v):
1304 """Returns True if the edge (u, v) is in the graph.
1306 This is the same as `v in G[u]` without KeyError exceptions.
1308 Parameters
1309 ----------
1310 u, v : nodes
1311 Nodes can be, for example, strings or numbers.
1312 Nodes must be hashable (and not None) Python objects.
1314 Returns
1315 -------
1316 edge_ind : bool
1317 True if edge is in the graph, False otherwise.
1319 Examples
1320 --------
1321 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1322 >>> G.has_edge(0, 1) # using two nodes
1323 True
1324 >>> e = (0, 1)
1325 >>> G.has_edge(*e) # e is a 2-tuple (u, v)
1326 True
1327 >>> e = (0, 1, {"weight": 7})
1328 >>> G.has_edge(*e[:2]) # e is a 3-tuple (u, v, data_dictionary)
1329 True
1331 The following syntax are equivalent:
1333 >>> G.has_edge(0, 1)
1334 True
1335 >>> 1 in G[0] # though this gives KeyError if 0 not in G
1336 True
1338 """
1339 try:
1340 return v in self._adj[u]
1341 except KeyError:
1342 return False
1344 def neighbors(self, n):
1345 """Returns an iterator over all neighbors of node n.
1347 This is identical to `iter(G[n])`
1349 Parameters
1350 ----------
1351 n : node
1352 A node in the graph
1354 Returns
1355 -------
1356 neighbors : iterator
1357 An iterator over all neighbors of node n
1359 Raises
1360 ------
1361 NetworkXError
1362 If the node n is not in the graph.
1364 Examples
1365 --------
1366 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1367 >>> [n for n in G.neighbors(0)]
1368 [1]
1370 Notes
1371 -----
1372 Alternate ways to access the neighbors are ``G.adj[n]`` or ``G[n]``:
1374 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1375 >>> G.add_edge("a", "b", weight=7)
1376 >>> G["a"]
1377 AtlasView({'b': {'weight': 7}})
1378 >>> G = nx.path_graph(4)
1379 >>> [n for n in G[0]]
1380 [1]
1381 """
1382 try:
1383 return iter(self._adj[n])
1384 except KeyError as err:
1385 raise NetworkXError(f"The node {n} is not in the graph.") from err
1387 @cached_property
1388 def edges(self):
1389 """An EdgeView of the Graph as G.edges or G.edges().
1391 edges(self, nbunch=None, data=False, default=None)
1393 The EdgeView provides set-like operations on the edge-tuples
1394 as well as edge attribute lookup. When called, it also provides
1395 an EdgeDataView object which allows control of access to edge
1396 attributes (but does not provide set-like operations).
1397 Hence, `G.edges[u, v]['color']` provides the value of the color
1398 attribute for edge `(u, v)` while
1399 `for (u, v, c) in G.edges.data('color', default='red'):`
1400 iterates through all the edges yielding the color attribute
1401 with default `'red'` if no color attribute exists.
1403 Parameters
1404 ----------
1405 nbunch : single node, container, or all nodes (default= all nodes)
1406 The view will only report edges from these nodes.
1407 data : string or bool, optional (default=False)
1408 The edge attribute returned in 3-tuple (u, v, ddict[data]).
1409 If True, return edge attribute dict in 3-tuple (u, v, ddict).
1410 If False, return 2-tuple (u, v).
1411 default : value, optional (default=None)
1412 Value used for edges that don't have the requested attribute.
1413 Only relevant if data is not True or False.
1415 Returns
1416 -------
1417 edges : EdgeView
1418 A view of edge attributes, usually it iterates over (u, v)
1419 or (u, v, d) tuples of edges, but can also be used for
1420 attribute lookup as `edges[u, v]['foo']`.
1422 Notes
1423 -----
1424 Nodes in nbunch that are not in the graph will be (quietly) ignored.
1425 For directed graphs this returns the out-edges.
1427 Examples
1428 --------
1429 >>> G = nx.path_graph(3) # or MultiGraph, etc
1430 >>> G.add_edge(2, 3, weight=5)
1431 >>> [e for e in G.edges]
1432 [(0, 1), (1, 2), (2, 3)]
1433 >>> G.edges.data() # default data is {} (empty dict)
1434 EdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})])
1435 >>> G.edges.data("weight", default=1)
1436 EdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)])
1437 >>> G.edges([0, 3]) # only edges from these nodes
1438 EdgeDataView([(0, 1), (3, 2)])
1439 >>> G.edges(0) # only edges from node 0
1440 EdgeDataView([(0, 1)])
1441 """
1442 return EdgeView(self)
1444 def get_edge_data(self, u, v, default=None):
1445 """Returns the attribute dictionary associated with edge (u, v).
1447 This is identical to `G[u][v]` except the default is returned
1448 instead of an exception if the edge doesn't exist.
1450 Parameters
1451 ----------
1452 u, v : nodes
1453 default: any Python object (default=None)
1454 Value to return if the edge (u, v) is not found.
1456 Returns
1457 -------
1458 edge_dict : dictionary
1459 The edge attribute dictionary.
1461 Examples
1462 --------
1463 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1464 >>> G[0][1]
1465 {}
1467 Warning: Assigning to `G[u][v]` is not permitted.
1468 But it is safe to assign attributes `G[u][v]['foo']`
1470 >>> G[0][1]["weight"] = 7
1471 >>> G[0][1]["weight"]
1472 7
1473 >>> G[1][0]["weight"]
1474 7
1476 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1477 >>> G.get_edge_data(0, 1) # default edge data is {}
1478 {}
1479 >>> e = (0, 1)
1480 >>> G.get_edge_data(*e) # tuple form
1481 {}
1482 >>> G.get_edge_data("a", "b", default=0) # edge not in graph, return 0
1483 0
1484 """
1485 try:
1486 return self._adj[u][v]
1487 except KeyError:
1488 return default
1490 def adjacency(self):
1491 """Returns an iterator over (node, adjacency dict) tuples for all nodes.
1493 For directed graphs, only outgoing neighbors/adjacencies are included.
1495 Returns
1496 -------
1497 adj_iter : iterator
1498 An iterator over (node, adjacency dictionary) for all nodes in
1499 the graph.
1501 Examples
1502 --------
1503 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1504 >>> [(n, nbrdict) for n, nbrdict in G.adjacency()]
1505 [(0, {1: {}}), (1, {0: {}, 2: {}}), (2, {1: {}, 3: {}}), (3, {2: {}})]
1507 """
1508 return iter(self._adj.items())
1510 @cached_property
1511 def degree(self):
1512 """A DegreeView for the Graph as G.degree or G.degree().
1514 The node degree is the number of edges adjacent to the node.
1515 The weighted node degree is the sum of the edge weights for
1516 edges incident to that node.
1518 This object provides an iterator for (node, degree) as well as
1519 lookup for the degree for a single node.
1521 Parameters
1522 ----------
1523 nbunch : single node, container, or all nodes (default= all nodes)
1524 The view will only report edges incident to these nodes.
1526 weight : string or None, optional (default=None)
1527 The name of an edge attribute that holds the numerical value used
1528 as a weight. If None, then each edge has weight 1.
1529 The degree is the sum of the edge weights adjacent to the node.
1531 Returns
1532 -------
1533 DegreeView or int
1534 If multiple nodes are requested (the default), returns a `DegreeView`
1535 mapping nodes to their degree.
1536 If a single node is requested, returns the degree of the node as an integer.
1538 Examples
1539 --------
1540 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1541 >>> G.degree[0] # node 0 has degree 1
1542 1
1543 >>> list(G.degree([0, 1, 2]))
1544 [(0, 1), (1, 2), (2, 2)]
1545 """
1546 return DegreeView(self)
1548 def clear(self):
1549 """Remove all nodes and edges from the graph.
1551 This also removes the name, and all graph, node, and edge attributes.
1553 Examples
1554 --------
1555 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1556 >>> G.clear()
1557 >>> list(G.nodes)
1558 []
1559 >>> list(G.edges)
1560 []
1562 """
1563 self._adj.clear()
1564 self._node.clear()
1565 self.graph.clear()
1566 nx._clear_cache(self)
1568 def clear_edges(self):
1569 """Remove all edges from the graph without altering nodes.
1571 Examples
1572 --------
1573 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1574 >>> G.clear_edges()
1575 >>> list(G.nodes)
1576 [0, 1, 2, 3]
1577 >>> list(G.edges)
1578 []
1579 """
1580 for nbr_dict in self._adj.values():
1581 nbr_dict.clear()
1582 nx._clear_cache(self)
1584 def is_multigraph(self):
1585 """Returns True if graph is a multigraph, False otherwise."""
1586 return False
1588 def is_directed(self):
1589 """Returns True if graph is directed, False otherwise."""
1590 return False
1592 def copy(self, as_view=False):
1593 """Returns a copy of the graph.
1595 The copy method by default returns an independent shallow copy
1596 of the graph and attributes. That is, if an attribute is a
1597 container, that container is shared by the original an the copy.
1598 Use Python's `copy.deepcopy` for new containers.
1600 If `as_view` is True then a view is returned instead of a copy.
1602 Notes
1603 -----
1604 All copies reproduce the graph structure, but data attributes
1605 may be handled in different ways. There are four types of copies
1606 of a graph that people might want.
1608 Deepcopy -- A "deepcopy" copies the graph structure as well as
1609 all data attributes and any objects they might contain.
1610 The entire graph object is new so that changes in the copy
1611 do not affect the original object. (see Python's copy.deepcopy)
1613 Data Reference (Shallow) -- For a shallow copy the graph structure
1614 is copied but the edge, node and graph attribute dicts are
1615 references to those in the original graph. This saves
1616 time and memory but could cause confusion if you change an attribute
1617 in one graph and it changes the attribute in the other.
1618 NetworkX does not provide this level of shallow copy.
1620 Independent Shallow -- This copy creates new independent attribute
1621 dicts and then does a shallow copy of the attributes. That is, any
1622 attributes that are containers are shared between the new graph
1623 and the original. This is exactly what `dict.copy()` provides.
1624 You can obtain this style copy using:
1626 >>> G = nx.path_graph(5)
1627 >>> H = G.copy()
1628 >>> H = G.copy(as_view=False)
1629 >>> H = nx.Graph(G)
1630 >>> H = G.__class__(G)
1632 Fresh Data -- For fresh data, the graph structure is copied while
1633 new empty data attribute dicts are created. The resulting graph
1634 is independent of the original and it has no edge, node or graph
1635 attributes. Fresh copies are not enabled. Instead use:
1637 >>> H = G.__class__()
1638 >>> H.add_nodes_from(G)
1639 >>> H.add_edges_from(G.edges)
1641 View -- Inspired by dict-views, graph-views act like read-only
1642 versions of the original graph, providing a copy of the original
1643 structure without requiring any memory for copying the information.
1645 See the Python copy module for more information on shallow
1646 and deep copies, https://docs.python.org/3/library/copy.html.
1648 Parameters
1649 ----------
1650 as_view : bool, optional (default=False)
1651 If True, the returned graph-view provides a read-only view
1652 of the original graph without actually copying any data.
1654 Returns
1655 -------
1656 G : Graph
1657 A copy of the graph.
1659 See Also
1660 --------
1661 to_directed: return a directed copy of the graph.
1663 Examples
1664 --------
1665 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1666 >>> H = G.copy()
1668 """
1669 if as_view is True:
1670 return nx.graphviews.generic_graph_view(self)
1671 G = self.__class__()
1672 G.graph.update(self.graph)
1673 G.add_nodes_from((n, d.copy()) for n, d in self._node.items())
1674 G.add_edges_from(
1675 (u, v, datadict.copy())
1676 for u, nbrs in self._adj.items()
1677 for v, datadict in nbrs.items()
1678 )
1679 return G
1681 def to_directed(self, as_view=False):
1682 """Returns a directed representation of the graph.
1684 Returns
1685 -------
1686 G : DiGraph
1687 A directed graph with the same name, same nodes, and with
1688 each edge (u, v, data) replaced by two directed edges
1689 (u, v, data) and (v, u, data).
1691 Notes
1692 -----
1693 This returns a "deepcopy" of the edge, node, and
1694 graph attributes which attempts to completely copy
1695 all of the data and references.
1697 This is in contrast to the similar D=DiGraph(G) which returns a
1698 shallow copy of the data.
1700 See the Python copy module for more information on shallow
1701 and deep copies, https://docs.python.org/3/library/copy.html.
1703 Warning: If you have subclassed Graph to use dict-like objects
1704 in the data structure, those changes do not transfer to the
1705 DiGraph created by this method.
1707 Examples
1708 --------
1709 >>> G = nx.Graph() # or MultiGraph, etc
1710 >>> G.add_edge(0, 1)
1711 >>> H = G.to_directed()
1712 >>> list(H.edges)
1713 [(0, 1), (1, 0)]
1715 If already directed, return a (deep) copy
1717 >>> G = nx.DiGraph() # or MultiDiGraph, etc
1718 >>> G.add_edge(0, 1)
1719 >>> H = G.to_directed()
1720 >>> list(H.edges)
1721 [(0, 1)]
1722 """
1723 graph_class = self.to_directed_class()
1724 if as_view is True:
1725 return nx.graphviews.generic_graph_view(self, graph_class)
1726 # deepcopy when not a view
1727 G = graph_class()
1728 G.graph.update(deepcopy(self.graph))
1729 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1730 G.add_edges_from(
1731 (u, v, deepcopy(data))
1732 for u, nbrs in self._adj.items()
1733 for v, data in nbrs.items()
1734 )
1735 return G
1737 def to_undirected(self, as_view=False):
1738 """Returns an undirected copy of the graph.
1740 Parameters
1741 ----------
1742 as_view : bool (optional, default=False)
1743 If True return a view of the original undirected graph.
1745 Returns
1746 -------
1747 G : Graph/MultiGraph
1748 A deepcopy of the graph.
1750 See Also
1751 --------
1752 Graph, copy, add_edge, add_edges_from
1754 Notes
1755 -----
1756 This returns a "deepcopy" of the edge, node, and
1757 graph attributes which attempts to completely copy
1758 all of the data and references.
1760 This is in contrast to the similar `G = nx.DiGraph(D)` which returns a
1761 shallow copy of the data.
1763 See the Python copy module for more information on shallow
1764 and deep copies, https://docs.python.org/3/library/copy.html.
1766 Warning: If you have subclassed DiGraph to use dict-like objects
1767 in the data structure, those changes do not transfer to the
1768 Graph created by this method.
1770 Examples
1771 --------
1772 >>> G = nx.path_graph(2) # or MultiGraph, etc
1773 >>> H = G.to_directed()
1774 >>> list(H.edges)
1775 [(0, 1), (1, 0)]
1776 >>> G2 = H.to_undirected()
1777 >>> list(G2.edges)
1778 [(0, 1)]
1779 """
1780 graph_class = self.to_undirected_class()
1781 if as_view is True:
1782 return nx.graphviews.generic_graph_view(self, graph_class)
1783 # deepcopy when not a view
1784 G = graph_class()
1785 G.graph.update(deepcopy(self.graph))
1786 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1787 G.add_edges_from(
1788 (u, v, deepcopy(d))
1789 for u, nbrs in self._adj.items()
1790 for v, d in nbrs.items()
1791 )
1792 return G
1794 def subgraph(self, nodes):
1795 """Returns a SubGraph view of the subgraph induced on `nodes`.
1797 The induced subgraph of the graph contains the nodes in `nodes`
1798 and the edges between those nodes.
1800 Parameters
1801 ----------
1802 nodes : list, iterable
1803 A container of nodes which will be iterated through once.
1805 Returns
1806 -------
1807 G : SubGraph View
1808 A subgraph view of the graph. The graph structure cannot be
1809 changed but node/edge attributes can and are shared with the
1810 original graph.
1812 Notes
1813 -----
1814 The graph, edge and node attributes are shared with the original graph.
1815 Changes to the graph structure is ruled out by the view, but changes
1816 to attributes are reflected in the original graph.
1818 To create a subgraph with its own copy of the edge/node attributes use:
1819 G.subgraph(nodes).copy()
1821 For an inplace reduction of a graph to a subgraph you can remove nodes:
1822 G.remove_nodes_from([n for n in G if n not in set(nodes)])
1824 Subgraph views are sometimes NOT what you want. In most cases where
1825 you want to do more than simply look at the induced edges, it makes
1826 more sense to just create the subgraph as its own graph with code like:
1828 ::
1830 # Create a subgraph SG based on a (possibly multigraph) G
1831 SG = G.__class__()
1832 SG.add_nodes_from((n, G.nodes[n]) for n in largest_wcc)
1833 if SG.is_multigraph():
1834 SG.add_edges_from(
1835 (n, nbr, key, d)
1836 for n, nbrs in G.adj.items()
1837 if n in largest_wcc
1838 for nbr, keydict in nbrs.items()
1839 if nbr in largest_wcc
1840 for key, d in keydict.items()
1841 )
1842 else:
1843 SG.add_edges_from(
1844 (n, nbr, d)
1845 for n, nbrs in G.adj.items()
1846 if n in largest_wcc
1847 for nbr, d in nbrs.items()
1848 if nbr in largest_wcc
1849 )
1850 SG.graph.update(G.graph)
1852 Subgraphs are not guaranteed to preserve the order of nodes or edges
1853 as they appear in the original graph. For example:
1855 >>> G = nx.Graph()
1856 >>> G.add_nodes_from(reversed(range(10)))
1857 >>> list(G)
1858 [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
1859 >>> list(G.subgraph([1, 3, 2]))
1860 [1, 2, 3]
1862 Examples
1863 --------
1864 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1865 >>> H = G.subgraph([0, 1, 2])
1866 >>> list(H.edges)
1867 [(0, 1), (1, 2)]
1868 """
1869 induced_nodes = nx.filters.show_nodes(self.nbunch_iter(nodes))
1870 # if already a subgraph, don't make a chain
1871 subgraph = nx.subgraph_view
1872 if hasattr(self, "_NODE_OK"):
1873 return subgraph(
1874 self._graph, filter_node=induced_nodes, filter_edge=self._EDGE_OK
1875 )
1876 return subgraph(self, filter_node=induced_nodes)
1878 def edge_subgraph(self, edges):
1879 """Returns the subgraph induced by the specified edges.
1881 The induced subgraph contains each edge in `edges` and each
1882 node incident to any one of those edges.
1884 Parameters
1885 ----------
1886 edges : iterable
1887 An iterable of edges in this graph.
1889 Returns
1890 -------
1891 G : Graph
1892 An edge-induced subgraph of this graph with the same edge
1893 attributes.
1895 Notes
1896 -----
1897 The graph, edge, and node attributes in the returned subgraph
1898 view are references to the corresponding attributes in the original
1899 graph. The view is read-only.
1901 To create a full graph version of the subgraph with its own copy
1902 of the edge or node attributes, use::
1904 G.edge_subgraph(edges).copy()
1906 Examples
1907 --------
1908 >>> G = nx.path_graph(5)
1909 >>> H = G.edge_subgraph([(0, 1), (3, 4)])
1910 >>> list(H.nodes)
1911 [0, 1, 3, 4]
1912 >>> list(H.edges)
1913 [(0, 1), (3, 4)]
1915 """
1916 return nx.edge_subgraph(self, edges)
1918 def size(self, weight=None):
1919 """Returns the number of edges or total of all edge weights.
1921 Parameters
1922 ----------
1923 weight : string or None, optional (default=None)
1924 The edge attribute that holds the numerical value used
1925 as a weight. If None, then each edge has weight 1.
1927 Returns
1928 -------
1929 size : numeric
1930 The number of edges or
1931 (if weight keyword is provided) the total weight sum.
1933 If weight is None, returns an int. Otherwise a float
1934 (or more general numeric if the weights are more general).
1936 See Also
1937 --------
1938 number_of_edges
1940 Examples
1941 --------
1942 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1943 >>> G.size()
1944 3
1946 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1947 >>> G.add_edge("a", "b", weight=2)
1948 >>> G.add_edge("b", "c", weight=4)
1949 >>> G.size()
1950 2
1951 >>> G.size(weight="weight")
1952 6.0
1953 """
1954 s = sum(d for v, d in self.degree(weight=weight))
1955 # If `weight` is None, the sum of the degrees is guaranteed to be
1956 # even, so we can perform integer division and hence return an
1957 # integer. Otherwise, the sum of the weighted degrees is not
1958 # guaranteed to be an integer, so we perform "real" division.
1959 return s // 2 if weight is None else s / 2
1961 def number_of_edges(self, u=None, v=None):
1962 """Returns the number of edges between two nodes.
1964 Parameters
1965 ----------
1966 u, v : nodes, optional (default=all edges)
1967 If u and v are specified, return the number of edges between
1968 u and v. Otherwise return the total number of all edges.
1970 Returns
1971 -------
1972 nedges : int
1973 The number of edges in the graph. If nodes `u` and `v` are
1974 specified return the number of edges between those nodes. If
1975 the graph is directed, this only returns the number of edges
1976 from `u` to `v`.
1978 See Also
1979 --------
1980 size
1982 Examples
1983 --------
1984 For undirected graphs, this method counts the total number of
1985 edges in the graph:
1987 >>> G = nx.path_graph(4)
1988 >>> G.number_of_edges()
1989 3
1991 If you specify two nodes, this counts the total number of edges
1992 joining the two nodes:
1994 >>> G.number_of_edges(0, 1)
1995 1
1997 For directed graphs, this method can count the total number of
1998 directed edges from `u` to `v`:
2000 >>> G = nx.DiGraph()
2001 >>> G.add_edge(0, 1)
2002 >>> G.add_edge(1, 0)
2003 >>> G.number_of_edges(0, 1)
2004 1
2006 """
2007 if u is None:
2008 return int(self.size())
2009 if v in self._adj[u]:
2010 return 1
2011 return 0
2013 def nbunch_iter(self, nbunch=None):
2014 """Returns an iterator over nodes contained in nbunch that are
2015 also in the graph.
2017 The nodes in an iterable nbunch are checked for membership in the graph
2018 and if not are silently ignored.
2020 Parameters
2021 ----------
2022 nbunch : single node, container, or all nodes (default= all nodes)
2023 The view will only report edges incident to these nodes.
2025 Returns
2026 -------
2027 niter : iterator
2028 An iterator over nodes in nbunch that are also in the graph.
2029 If nbunch is None, iterate over all nodes in the graph.
2031 Raises
2032 ------
2033 NetworkXError
2034 If nbunch is not a node or sequence of nodes.
2035 If a node in nbunch is not hashable.
2037 See Also
2038 --------
2039 Graph.__iter__
2041 Notes
2042 -----
2043 When nbunch is an iterator, the returned iterator yields values
2044 directly from nbunch, becoming exhausted when nbunch is exhausted.
2046 To test whether nbunch is a single node, one can use
2047 "if nbunch in self:", even after processing with this routine.
2049 If nbunch is not a node or a (possibly empty) sequence/iterator
2050 or None, a :exc:`NetworkXError` is raised. Also, if any object in
2051 nbunch is not hashable, a :exc:`NetworkXError` is raised.
2052 """
2053 if nbunch is None: # include all nodes via iterator
2054 bunch = iter(self._adj)
2055 elif nbunch in self: # if nbunch is a single node
2056 bunch = iter([nbunch])
2057 else: # if nbunch is a sequence of nodes
2059 def bunch_iter(nlist, adj):
2060 try:
2061 for n in nlist:
2062 if n in adj:
2063 yield n
2064 except TypeError as err:
2065 exc, message = err, err.args[0]
2066 # capture error for non-sequence/iterator nbunch.
2067 if "iter" in message:
2068 exc = NetworkXError(
2069 "nbunch is not a node or a sequence of nodes."
2070 )
2071 # capture single nodes that are not in the graph.
2072 if "object is not iterable" in message:
2073 exc = NetworkXError(f"Node {nbunch} is not in the graph.")
2074 # capture error for unhashable node.
2075 if "hashable" in message:
2076 exc = NetworkXError(
2077 f"Node {n} in sequence nbunch is not a valid node."
2078 )
2079 raise exc
2081 bunch = bunch_iter(nbunch, self._adj)
2082 return bunch