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 def __init__(self, incoming_graph_data=None, **attr):
340 """Initialize a graph with edges, name, or graph attributes.
342 Parameters
343 ----------
344 incoming_graph_data : input graph (optional, default: None)
345 Data to initialize graph. If None (default) an empty
346 graph is created. The data can be an edge list, or any
347 NetworkX graph object. If the corresponding optional Python
348 packages are installed the data can also be a 2D NumPy array, a
349 SciPy sparse array, or a PyGraphviz graph.
351 attr : keyword arguments, optional (default= no attributes)
352 Attributes to add to graph as key=value pairs.
354 See Also
355 --------
356 convert
358 Examples
359 --------
360 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
361 >>> G = nx.Graph(name="my graph")
362 >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges
363 >>> G = nx.Graph(e)
365 Arbitrary graph attribute pairs (key=value) may be assigned
367 >>> G = nx.Graph(e, day="Friday")
368 >>> G.graph
369 {'day': 'Friday'}
371 """
372 self.graph = self.graph_attr_dict_factory() # dictionary for graph attributes
373 self._node = self.node_dict_factory() # empty node attribute dict
374 self._adj = self.adjlist_outer_dict_factory() # empty adjacency dict
375 self.__networkx_cache__ = {}
376 # attempt to load graph with data
377 if incoming_graph_data is not None:
378 convert.to_networkx_graph(incoming_graph_data, create_using=self)
379 # load graph attributes (must be after convert)
380 self.graph.update(attr)
382 @cached_property
383 def adj(self):
384 """Graph adjacency object holding the neighbors of each node.
386 This object is a read-only dict-like structure with node keys
387 and neighbor-dict values. The neighbor-dict is keyed by neighbor
388 to the edge-data-dict. So `G.adj[3][2]['color'] = 'blue'` sets
389 the color of the edge `(3, 2)` to `"blue"`.
391 Iterating over G.adj behaves like a dict. Useful idioms include
392 `for nbr, datadict in G.adj[n].items():`.
394 The neighbor information is also provided by subscripting the graph.
395 So `for nbr, foovalue in G[node].data('foo', default=1):` works.
397 For directed graphs, `G.adj` holds outgoing (successor) info.
398 """
399 return AdjacencyView(self._adj)
401 @property
402 def name(self):
403 """String identifier of the graph.
405 This graph attribute appears in the attribute dict G.graph
406 keyed by the string `"name"`. as well as an attribute (technically
407 a property) `G.name`. This is entirely user controlled.
408 """
409 return self.graph.get("name", "")
411 @name.setter
412 def name(self, s):
413 self.graph["name"] = s
414 nx._clear_cache(self)
416 def __str__(self):
417 """Returns a short summary of the graph.
419 Returns
420 -------
421 info : string
422 Graph information including the graph name (if any), graph type, and the
423 number of nodes and edges.
425 Examples
426 --------
427 >>> G = nx.Graph(name="foo")
428 >>> str(G)
429 "Graph named 'foo' with 0 nodes and 0 edges"
431 >>> G = nx.path_graph(3)
432 >>> str(G)
433 'Graph with 3 nodes and 2 edges'
435 """
436 return "".join(
437 [
438 type(self).__name__,
439 f" named {self.name!r}" if self.name else "",
440 f" with {self.number_of_nodes()} nodes and {self.number_of_edges()} edges",
441 ]
442 )
444 def __iter__(self):
445 """Iterate over the nodes. Use: 'for n in G'.
447 Returns
448 -------
449 niter : iterator
450 An iterator over all nodes in the graph.
452 Examples
453 --------
454 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
455 >>> [n for n in G]
456 [0, 1, 2, 3]
457 >>> list(G)
458 [0, 1, 2, 3]
459 """
460 return iter(self._node)
462 def __contains__(self, n):
463 """Returns True if n is a node, False otherwise. Use: 'n in G'.
465 Examples
466 --------
467 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
468 >>> 1 in G
469 True
470 """
471 try:
472 return n in self._node
473 except TypeError:
474 return False
476 def __len__(self):
477 """Returns the number of nodes in the graph. Use: 'len(G)'.
479 Returns
480 -------
481 nnodes : int
482 The number of nodes in the graph.
484 See Also
485 --------
486 number_of_nodes: identical method
487 order: identical method
489 Examples
490 --------
491 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
492 >>> len(G)
493 4
495 """
496 return len(self._node)
498 def __getitem__(self, n):
499 """Returns a dict of neighbors of node n. Use: 'G[n]'.
501 Parameters
502 ----------
503 n : node
504 A node in the graph.
506 Returns
507 -------
508 adj_dict : dictionary
509 The adjacency dictionary for nodes connected to n.
511 Notes
512 -----
513 G[n] is the same as G.adj[n] and similar to G.neighbors(n)
514 (which is an iterator over G.adj[n])
516 Examples
517 --------
518 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
519 >>> G[0]
520 AtlasView({1: {}})
521 """
522 return self.adj[n]
524 def add_node(self, node_for_adding, **attr):
525 """Add a single node `node_for_adding` and update node attributes.
527 Parameters
528 ----------
529 node_for_adding : node
530 A node can be any hashable Python object except None.
531 attr : keyword arguments, optional
532 Set or change node attributes using key=value.
534 See Also
535 --------
536 add_nodes_from
538 Examples
539 --------
540 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
541 >>> G.add_node(1)
542 >>> G.add_node("Hello")
543 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
544 >>> G.add_node(K3)
545 >>> G.number_of_nodes()
546 3
548 Use keywords set/change node attributes:
550 >>> G.add_node(1, size=10)
551 >>> G.add_node(3, weight=0.4, UTM=("13S", 382871, 3972649))
553 Notes
554 -----
555 A hashable object is one that can be used as a key in a Python
556 dictionary. This includes strings, numbers, tuples of strings
557 and numbers, etc.
559 On many platforms hashable items also include mutables such as
560 NetworkX Graphs, though one should be careful that the hash
561 doesn't change on mutables.
562 """
563 if node_for_adding not in self._node:
564 if node_for_adding is None:
565 raise ValueError("None cannot be a node")
566 self._adj[node_for_adding] = self.adjlist_inner_dict_factory()
567 attr_dict = self._node[node_for_adding] = self.node_attr_dict_factory()
568 attr_dict.update(attr)
569 else: # update attr even if node already exists
570 self._node[node_for_adding].update(attr)
571 nx._clear_cache(self)
573 def add_nodes_from(self, nodes_for_adding, **attr):
574 """Add multiple nodes.
576 Parameters
577 ----------
578 nodes_for_adding : iterable container
579 A container of nodes (list, dict, set, etc.).
580 OR
581 A container of (node, attribute dict) tuples.
582 Node attributes are updated using the attribute dict.
583 attr : keyword arguments, optional (default= no attributes)
584 Update attributes for all nodes in nodes.
585 Node attributes specified in nodes as a tuple take
586 precedence over attributes specified via keyword arguments.
588 See Also
589 --------
590 add_node
592 Notes
593 -----
594 When adding nodes from an iterator over the graph you are changing,
595 a `RuntimeError` can be raised with message:
596 `RuntimeError: dictionary changed size during iteration`. This
597 happens when the graph's underlying dictionary is modified during
598 iteration. To avoid this error, evaluate the iterator into a separate
599 object, e.g. by using `list(iterator_of_nodes)`, and pass this
600 object to `G.add_nodes_from`.
602 Examples
603 --------
604 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
605 >>> G.add_nodes_from("Hello")
606 >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)])
607 >>> G.add_nodes_from(K3)
608 >>> sorted(G.nodes(), key=str)
609 [0, 1, 2, 'H', 'e', 'l', 'o']
611 Use keywords to update specific node attributes for every node.
613 >>> G.add_nodes_from([1, 2], size=10)
614 >>> G.add_nodes_from([3, 4], weight=0.4)
616 Use (node, attrdict) tuples to update attributes for specific nodes.
618 >>> G.add_nodes_from([(1, dict(size=11)), (2, {"color": "blue"})])
619 >>> G.nodes[1]["size"]
620 11
621 >>> H = nx.Graph()
622 >>> H.add_nodes_from(G.nodes(data=True))
623 >>> H.nodes[1]["size"]
624 11
626 Evaluate an iterator over a graph if using it to modify the same graph
628 >>> G = nx.Graph([(0, 1), (1, 2), (3, 4)])
629 >>> # wrong way - will raise RuntimeError
630 >>> # G.add_nodes_from(n + 1 for n in G.nodes)
631 >>> # correct way
632 >>> G.add_nodes_from(list(n + 1 for n in G.nodes))
633 """
634 for n in nodes_for_adding:
635 try:
636 newnode = n not in self._node
637 newdict = attr
638 except TypeError:
639 n, ndict = n
640 newnode = n not in self._node
641 newdict = attr.copy()
642 newdict.update(ndict)
643 if newnode:
644 if n is None:
645 raise ValueError("None cannot be a node")
646 self._adj[n] = self.adjlist_inner_dict_factory()
647 self._node[n] = self.node_attr_dict_factory()
648 self._node[n].update(newdict)
649 nx._clear_cache(self)
651 def remove_node(self, n):
652 """Remove node n.
654 Removes the node n and all adjacent edges.
655 Attempting to remove a nonexistent node will raise an exception.
657 Parameters
658 ----------
659 n : node
660 A node in the graph
662 Raises
663 ------
664 NetworkXError
665 If n is not in the graph.
667 See Also
668 --------
669 remove_nodes_from
671 Examples
672 --------
673 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
674 >>> list(G.edges)
675 [(0, 1), (1, 2)]
676 >>> G.remove_node(1)
677 >>> list(G.edges)
678 []
680 """
681 adj = self._adj
682 try:
683 nbrs = list(adj[n]) # list handles self-loops (allows mutation)
684 del self._node[n]
685 except KeyError as err: # NetworkXError if n not in self
686 raise NetworkXError(f"The node {n} is not in the graph.") from err
687 for u in nbrs:
688 del adj[u][n] # remove all edges n-u in graph
689 del adj[n] # now remove node
690 nx._clear_cache(self)
692 def remove_nodes_from(self, nodes):
693 """Remove multiple nodes.
695 Parameters
696 ----------
697 nodes : iterable container
698 A container of nodes (list, dict, set, etc.). If a node
699 in the container is not in the graph it is silently
700 ignored.
702 See Also
703 --------
704 remove_node
706 Notes
707 -----
708 When removing nodes from an iterator over the graph you are changing,
709 a `RuntimeError` will be raised with message:
710 `RuntimeError: dictionary changed size during iteration`. This
711 happens when the graph's underlying dictionary is modified during
712 iteration. To avoid this error, evaluate the iterator into a separate
713 object, e.g. by using `list(iterator_of_nodes)`, and pass this
714 object to `G.remove_nodes_from`.
716 Examples
717 --------
718 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
719 >>> e = list(G.nodes)
720 >>> e
721 [0, 1, 2]
722 >>> G.remove_nodes_from(e)
723 >>> list(G.nodes)
724 []
726 Evaluate an iterator over a graph if using it to modify the same graph
728 >>> G = nx.Graph([(0, 1), (1, 2), (3, 4)])
729 >>> # this command will fail, as the graph's dict is modified during iteration
730 >>> # G.remove_nodes_from(n for n in G.nodes if n < 2)
731 >>> # this command will work, since the dictionary underlying graph is not modified
732 >>> G.remove_nodes_from(list(n for n in G.nodes if n < 2))
733 """
734 adj = self._adj
735 for n in nodes:
736 try:
737 del self._node[n]
738 for u in list(adj[n]): # list handles self-loops
739 del adj[u][n] # (allows mutation of dict in loop)
740 del adj[n]
741 except KeyError:
742 pass
743 nx._clear_cache(self)
745 @cached_property
746 def nodes(self):
747 """A NodeView of the Graph as G.nodes or G.nodes().
749 Can be used as `G.nodes` for data lookup and for set-like operations.
750 Can also be used as `G.nodes(data='color', default=None)` to return a
751 NodeDataView which reports specific node data but no set operations.
752 It presents a dict-like interface as well with `G.nodes.items()`
753 iterating over `(node, nodedata)` 2-tuples and `G.nodes[3]['foo']`
754 providing the value of the `foo` attribute for node `3`. In addition,
755 a view `G.nodes.data('foo')` provides a dict-like interface to the
756 `foo` attribute of each node. `G.nodes.data('foo', default=1)`
757 provides a default for nodes that do not have attribute `foo`.
759 Parameters
760 ----------
761 data : string or bool, optional (default=False)
762 The node attribute returned in 2-tuple (n, ddict[data]).
763 If True, return entire node attribute dict as (n, ddict).
764 If False, return just the nodes n.
766 default : value, optional (default=None)
767 Value used for nodes that don't have the requested attribute.
768 Only relevant if data is not True or False.
770 Returns
771 -------
772 NodeView
773 Allows set-like operations over the nodes as well as node
774 attribute dict lookup and calling to get a NodeDataView.
775 A NodeDataView iterates over `(n, data)` and has no set operations.
776 A NodeView iterates over `n` and includes set operations.
778 When called, if data is False, an iterator over nodes.
779 Otherwise an iterator of 2-tuples (node, attribute value)
780 where the attribute is specified in `data`.
781 If data is True then the attribute becomes the
782 entire data dictionary.
784 Notes
785 -----
786 If your node data is not needed, it is simpler and equivalent
787 to use the expression ``for n in G``, or ``list(G)``.
789 Examples
790 --------
791 There are two simple ways of getting a list of all nodes in the graph:
793 >>> G = nx.path_graph(3)
794 >>> list(G.nodes)
795 [0, 1, 2]
796 >>> list(G)
797 [0, 1, 2]
799 To get the node data along with the nodes:
801 >>> G.add_node(1, time="5pm")
802 >>> G.nodes[0]["foo"] = "bar"
803 >>> list(G.nodes(data=True))
804 [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})]
805 >>> list(G.nodes.data())
806 [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})]
808 >>> list(G.nodes(data="foo"))
809 [(0, 'bar'), (1, None), (2, None)]
810 >>> list(G.nodes.data("foo"))
811 [(0, 'bar'), (1, None), (2, None)]
813 >>> list(G.nodes(data="time"))
814 [(0, None), (1, '5pm'), (2, None)]
815 >>> list(G.nodes.data("time"))
816 [(0, None), (1, '5pm'), (2, None)]
818 >>> list(G.nodes(data="time", default="Not Available"))
819 [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')]
820 >>> list(G.nodes.data("time", default="Not Available"))
821 [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')]
823 If some of your nodes have an attribute and the rest are assumed
824 to have a default attribute value you can create a dictionary
825 from node/attribute pairs using the `default` keyword argument
826 to guarantee the value is never None::
828 >>> G = nx.Graph()
829 >>> G.add_node(0)
830 >>> G.add_node(1, weight=2)
831 >>> G.add_node(2, weight=3)
832 >>> dict(G.nodes(data="weight", default=1))
833 {0: 1, 1: 2, 2: 3}
835 """
836 return NodeView(self)
838 def number_of_nodes(self):
839 """Returns the number of nodes in the graph.
841 Returns
842 -------
843 nnodes : int
844 The number of nodes in the graph.
846 See Also
847 --------
848 order: identical method
849 __len__: identical method
851 Examples
852 --------
853 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
854 >>> G.number_of_nodes()
855 3
856 """
857 return len(self._node)
859 def order(self):
860 """Returns the number of nodes in the graph.
862 Returns
863 -------
864 nnodes : int
865 The number of nodes in the graph.
867 See Also
868 --------
869 number_of_nodes: identical method
870 __len__: identical method
872 Examples
873 --------
874 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
875 >>> G.order()
876 3
877 """
878 return len(self._node)
880 def has_node(self, n):
881 """Returns True if the graph contains the node n.
883 Identical to `n in G`
885 Parameters
886 ----------
887 n : node
889 Examples
890 --------
891 >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc
892 >>> G.has_node(0)
893 True
895 It is more readable and simpler to use
897 >>> 0 in G
898 True
900 """
901 try:
902 return n in self._node
903 except TypeError:
904 return False
906 def add_edge(self, u_of_edge, v_of_edge, **attr):
907 """Add an edge between u and v.
909 The nodes u and v will be automatically added if they are
910 not already in the graph.
912 Edge attributes can be specified with keywords or by directly
913 accessing the edge's attribute dictionary. See examples below.
915 Parameters
916 ----------
917 u_of_edge, v_of_edge : nodes
918 Nodes can be, for example, strings or numbers.
919 Nodes must be hashable (and not None) Python objects.
920 attr : keyword arguments, optional
921 Edge data (or labels or objects) can be assigned using
922 keyword arguments.
924 See Also
925 --------
926 add_edges_from : add a collection of edges
928 Notes
929 -----
930 Adding an edge that already exists updates the edge data.
932 Many NetworkX algorithms designed for weighted graphs use
933 an edge attribute (by default `weight`) to hold a numerical value.
935 Examples
936 --------
937 The following all add the edge e=(1, 2) to graph G:
939 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
940 >>> e = (1, 2)
941 >>> G.add_edge(1, 2) # explicit two-node form
942 >>> G.add_edge(*e) # single edge as tuple of two nodes
943 >>> G.add_edges_from([(1, 2)]) # add edges from iterable container
945 Associate data to edges using keywords:
947 >>> G.add_edge(1, 2, weight=3)
948 >>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7)
950 For non-string attribute keys, use subscript notation.
952 >>> G.add_edge(1, 2)
953 >>> G[1][2].update({0: 5})
954 >>> G.edges[1, 2].update({0: 5})
955 """
956 u, v = u_of_edge, v_of_edge
957 # add nodes
958 if u not in self._node:
959 if u is None:
960 raise ValueError("None cannot be a node")
961 self._adj[u] = self.adjlist_inner_dict_factory()
962 self._node[u] = self.node_attr_dict_factory()
963 if v not in self._node:
964 if v is None:
965 raise ValueError("None cannot be a node")
966 self._adj[v] = self.adjlist_inner_dict_factory()
967 self._node[v] = self.node_attr_dict_factory()
968 # add the edge
969 datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
970 datadict.update(attr)
971 self._adj[u][v] = datadict
972 self._adj[v][u] = datadict
973 nx._clear_cache(self)
975 def add_edges_from(self, ebunch_to_add, **attr):
976 """Add all the edges in ebunch_to_add.
978 Parameters
979 ----------
980 ebunch_to_add : container of edges
981 Each edge given in the container will be added to the
982 graph. The edges must be given as 2-tuples (u, v) or
983 3-tuples (u, v, d) where d is a dictionary containing edge data.
984 attr : keyword arguments, optional
985 Edge data (or labels or objects) can be assigned using
986 keyword arguments.
988 See Also
989 --------
990 add_edge : add a single edge
991 add_weighted_edges_from : convenient way to add weighted edges
993 Notes
994 -----
995 Adding the same edge twice has no effect but any edge data
996 will be updated when each duplicate edge is added.
998 Edge attributes specified in an ebunch take precedence over
999 attributes specified via keyword arguments.
1001 When adding edges from an iterator over the graph you are changing,
1002 a `RuntimeError` can be raised with message:
1003 `RuntimeError: dictionary changed size during iteration`. This
1004 happens when the graph's underlying dictionary is modified during
1005 iteration. To avoid this error, evaluate the iterator into a separate
1006 object, e.g. by using `list(iterator_of_edges)`, and pass this
1007 object to `G.add_edges_from`.
1009 Examples
1010 --------
1011 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1012 >>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples
1013 >>> e = zip(range(0, 3), range(1, 4))
1014 >>> G.add_edges_from(e) # Add the path graph 0-1-2-3
1016 Associate data to edges
1018 >>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
1019 >>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898")
1021 Evaluate an iterator over a graph if using it to modify the same graph
1023 >>> G = nx.Graph([(1, 2), (2, 3), (3, 4)])
1024 >>> # Grow graph by one new node, adding edges to all existing nodes.
1025 >>> # wrong way - will raise RuntimeError
1026 >>> # G.add_edges_from(((5, n) for n in G.nodes))
1027 >>> # correct way - note that there will be no self-edge for node 5
1028 >>> G.add_edges_from(list((5, n) for n in G.nodes))
1029 """
1030 for e in ebunch_to_add:
1031 ne = len(e)
1032 if ne == 3:
1033 u, v, dd = e
1034 elif ne == 2:
1035 u, v = e
1036 dd = {} # doesn't need edge_attr_dict_factory
1037 else:
1038 raise NetworkXError(f"Edge tuple {e} must be a 2-tuple or 3-tuple.")
1039 if u not in self._node:
1040 if u is None:
1041 raise ValueError("None cannot be a node")
1042 self._adj[u] = self.adjlist_inner_dict_factory()
1043 self._node[u] = self.node_attr_dict_factory()
1044 if v not in self._node:
1045 if v is None:
1046 raise ValueError("None cannot be a node")
1047 self._adj[v] = self.adjlist_inner_dict_factory()
1048 self._node[v] = self.node_attr_dict_factory()
1049 datadict = self._adj[u].get(v, self.edge_attr_dict_factory())
1050 datadict.update(attr)
1051 datadict.update(dd)
1052 self._adj[u][v] = datadict
1053 self._adj[v][u] = datadict
1054 nx._clear_cache(self)
1056 def add_weighted_edges_from(self, ebunch_to_add, weight="weight", **attr):
1057 """Add weighted edges in `ebunch_to_add` with specified weight attr
1059 Parameters
1060 ----------
1061 ebunch_to_add : container of edges
1062 Each edge given in the list or container will be added
1063 to the graph. The edges must be given as 3-tuples (u, v, w)
1064 where w is a number.
1065 weight : string, optional (default= 'weight')
1066 The attribute name for the edge weights to be added.
1067 attr : keyword arguments, optional (default= no attributes)
1068 Edge attributes to add/update for all edges.
1070 See Also
1071 --------
1072 add_edge : add a single edge
1073 add_edges_from : add multiple edges
1075 Notes
1076 -----
1077 Adding the same edge twice for Graph/DiGraph simply updates
1078 the edge data. For MultiGraph/MultiDiGraph, duplicate edges
1079 are stored.
1081 When adding edges from an iterator over the graph you are changing,
1082 a `RuntimeError` can be raised with message:
1083 `RuntimeError: dictionary changed size during iteration`. This
1084 happens when the graph's underlying dictionary is modified during
1085 iteration. To avoid this error, evaluate the iterator into a separate
1086 object, e.g. by using `list(iterator_of_edges)`, and pass this
1087 object to `G.add_weighted_edges_from`.
1089 Examples
1090 --------
1091 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1092 >>> G.add_weighted_edges_from([(0, 1, 3.0), (1, 2, 7.5)])
1094 Evaluate an iterator over edges before passing it
1096 >>> G = nx.Graph([(1, 2), (2, 3), (3, 4)])
1097 >>> weight = 0.1
1098 >>> # Grow graph by one new node, adding edges to all existing nodes.
1099 >>> # wrong way - will raise RuntimeError
1100 >>> # G.add_weighted_edges_from(((5, n, weight) for n in G.nodes))
1101 >>> # correct way - note that there will be no self-edge for node 5
1102 >>> G.add_weighted_edges_from(list((5, n, weight) for n in G.nodes))
1103 """
1104 self.add_edges_from(((u, v, {weight: d}) for u, v, d in ebunch_to_add), **attr)
1105 nx._clear_cache(self)
1107 def remove_edge(self, u, v):
1108 """Remove the edge between u and v.
1110 Parameters
1111 ----------
1112 u, v : nodes
1113 Remove the edge between nodes u and v.
1115 Raises
1116 ------
1117 NetworkXError
1118 If there is not an edge between u and v.
1120 See Also
1121 --------
1122 remove_edges_from : remove a collection of edges
1124 Examples
1125 --------
1126 >>> G = nx.path_graph(4) # or DiGraph, etc
1127 >>> G.remove_edge(0, 1)
1128 >>> e = (1, 2)
1129 >>> G.remove_edge(*e) # unpacks e from an edge tuple
1130 >>> e = (2, 3, {"weight": 7}) # an edge with attribute data
1131 >>> G.remove_edge(*e[:2]) # select first part of edge tuple
1132 """
1133 try:
1134 del self._adj[u][v]
1135 if u != v: # self-loop needs only one entry removed
1136 del self._adj[v][u]
1137 except KeyError as err:
1138 raise NetworkXError(f"The edge {u}-{v} is not in the graph") from err
1139 nx._clear_cache(self)
1141 def remove_edges_from(self, ebunch):
1142 """Remove all edges specified in ebunch.
1144 Parameters
1145 ----------
1146 ebunch: list or container of edge tuples
1147 Each edge given in the list or container will be removed
1148 from the graph. The edges can be:
1150 - 2-tuples (u, v) edge between u and v.
1151 - 3-tuples (u, v, k) where k is ignored.
1153 See Also
1154 --------
1155 remove_edge : remove a single edge
1157 Notes
1158 -----
1159 Will fail silently if an edge in ebunch is not in the graph.
1161 Examples
1162 --------
1163 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1164 >>> ebunch = [(1, 2), (2, 3)]
1165 >>> G.remove_edges_from(ebunch)
1166 """
1167 adj = self._adj
1168 for e in ebunch:
1169 u, v = e[:2] # ignore edge data if present
1170 if u in adj and v in adj[u]:
1171 del adj[u][v]
1172 if u != v: # self loop needs only one entry removed
1173 del adj[v][u]
1174 nx._clear_cache(self)
1176 def update(self, edges=None, nodes=None):
1177 """Update the graph using nodes/edges/graphs as input.
1179 Like dict.update, this method takes a graph as input, adding the
1180 graph's nodes and edges to this graph. It can also take two inputs:
1181 edges and nodes. Finally it can take either edges or nodes.
1182 To specify only nodes the keyword `nodes` must be used.
1184 The collections of edges and nodes are treated similarly to
1185 the add_edges_from/add_nodes_from methods. When iterated, they
1186 should yield 2-tuples (u, v) or 3-tuples (u, v, datadict).
1188 Parameters
1189 ----------
1190 edges : Graph object, collection of edges, or None
1191 The first parameter can be a graph or some edges. If it has
1192 attributes `nodes` and `edges`, then it is taken to be a
1193 Graph-like object and those attributes are used as collections
1194 of nodes and edges to be added to the graph.
1195 If the first parameter does not have those attributes, it is
1196 treated as a collection of edges and added to the graph.
1197 If the first argument is None, no edges are added.
1198 nodes : collection of nodes, or None
1199 The second parameter is treated as a collection of nodes
1200 to be added to the graph unless it is None.
1201 If `edges is None` and `nodes is None` an exception is raised.
1202 If the first parameter is a Graph, then `nodes` is ignored.
1204 Examples
1205 --------
1206 >>> G = nx.path_graph(5)
1207 >>> G.update(nx.complete_graph(range(4, 10)))
1208 >>> from itertools import combinations
1209 >>> edges = (
1210 ... (u, v, {"power": u * v})
1211 ... for u, v in combinations(range(10, 20), 2)
1212 ... if u * v < 225
1213 ... )
1214 >>> nodes = [1000] # for singleton, use a container
1215 >>> G.update(edges, nodes)
1217 Notes
1218 -----
1219 It you want to update the graph using an adjacency structure
1220 it is straightforward to obtain the edges/nodes from adjacency.
1221 The following examples provide common cases, your adjacency may
1222 be slightly different and require tweaks of these examples::
1224 >>> # dict-of-set/list/tuple
1225 >>> adj = {1: {2, 3}, 2: {1, 3}, 3: {1, 2}}
1226 >>> e = [(u, v) for u, nbrs in adj.items() for v in nbrs]
1227 >>> G.update(edges=e, nodes=adj)
1229 >>> DG = nx.DiGraph()
1230 >>> # dict-of-dict-of-attribute
1231 >>> adj = {1: {2: 1.3, 3: 0.7}, 2: {1: 1.4}, 3: {1: 0.7}}
1232 >>> e = [
1233 ... (u, v, {"weight": d})
1234 ... for u, nbrs in adj.items()
1235 ... for v, d in nbrs.items()
1236 ... ]
1237 >>> DG.update(edges=e, nodes=adj)
1239 >>> # dict-of-dict-of-dict
1240 >>> adj = {1: {2: {"weight": 1.3}, 3: {"color": 0.7, "weight": 1.2}}}
1241 >>> e = [
1242 ... (u, v, {"weight": d})
1243 ... for u, nbrs in adj.items()
1244 ... for v, d in nbrs.items()
1245 ... ]
1246 >>> DG.update(edges=e, nodes=adj)
1248 >>> # predecessor adjacency (dict-of-set)
1249 >>> pred = {1: {2, 3}, 2: {3}, 3: {3}}
1250 >>> e = [(v, u) for u, nbrs in pred.items() for v in nbrs]
1252 >>> # MultiGraph dict-of-dict-of-dict-of-attribute
1253 >>> MDG = nx.MultiDiGraph()
1254 >>> adj = {
1255 ... 1: {2: {0: {"weight": 1.3}, 1: {"weight": 1.2}}},
1256 ... 3: {2: {0: {"weight": 0.7}}},
1257 ... }
1258 >>> e = [
1259 ... (u, v, ekey, d)
1260 ... for u, nbrs in adj.items()
1261 ... for v, keydict in nbrs.items()
1262 ... for ekey, d in keydict.items()
1263 ... ]
1264 >>> MDG.update(edges=e)
1266 See Also
1267 --------
1268 add_edges_from: add multiple edges to a graph
1269 add_nodes_from: add multiple nodes to a graph
1270 """
1271 if edges is not None:
1272 if nodes is not None:
1273 self.add_nodes_from(nodes)
1274 self.add_edges_from(edges)
1275 else:
1276 # check if edges is a Graph object
1277 try:
1278 graph_nodes = edges.nodes
1279 graph_edges = edges.edges
1280 except AttributeError:
1281 # edge not Graph-like
1282 self.add_edges_from(edges)
1283 else: # edges is Graph-like
1284 self.add_nodes_from(graph_nodes.data())
1285 self.add_edges_from(graph_edges.data())
1286 self.graph.update(edges.graph)
1287 elif nodes is not None:
1288 self.add_nodes_from(nodes)
1289 else:
1290 raise NetworkXError("update needs nodes or edges input")
1292 def has_edge(self, u, v):
1293 """Returns True if the edge (u, v) is in the graph.
1295 This is the same as `v in G[u]` without KeyError exceptions.
1297 Parameters
1298 ----------
1299 u, v : nodes
1300 Nodes can be, for example, strings or numbers.
1301 Nodes must be hashable (and not None) Python objects.
1303 Returns
1304 -------
1305 edge_ind : bool
1306 True if edge is in the graph, False otherwise.
1308 Examples
1309 --------
1310 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1311 >>> G.has_edge(0, 1) # using two nodes
1312 True
1313 >>> e = (0, 1)
1314 >>> G.has_edge(*e) # e is a 2-tuple (u, v)
1315 True
1316 >>> e = (0, 1, {"weight": 7})
1317 >>> G.has_edge(*e[:2]) # e is a 3-tuple (u, v, data_dictionary)
1318 True
1320 The following syntax are equivalent:
1322 >>> G.has_edge(0, 1)
1323 True
1324 >>> 1 in G[0] # though this gives KeyError if 0 not in G
1325 True
1327 """
1328 try:
1329 return v in self._adj[u]
1330 except KeyError:
1331 return False
1333 def neighbors(self, n):
1334 """Returns an iterator over all neighbors of node n.
1336 This is identical to `iter(G[n])`
1338 Parameters
1339 ----------
1340 n : node
1341 A node in the graph
1343 Returns
1344 -------
1345 neighbors : iterator
1346 An iterator over all neighbors of node n
1348 Raises
1349 ------
1350 NetworkXError
1351 If the node n is not in the graph.
1353 Examples
1354 --------
1355 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1356 >>> [n for n in G.neighbors(0)]
1357 [1]
1359 Notes
1360 -----
1361 Alternate ways to access the neighbors are ``G.adj[n]`` or ``G[n]``:
1363 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1364 >>> G.add_edge("a", "b", weight=7)
1365 >>> G["a"]
1366 AtlasView({'b': {'weight': 7}})
1367 >>> G = nx.path_graph(4)
1368 >>> [n for n in G[0]]
1369 [1]
1370 """
1371 try:
1372 return iter(self._adj[n])
1373 except KeyError as err:
1374 raise NetworkXError(f"The node {n} is not in the graph.") from err
1376 @cached_property
1377 def edges(self):
1378 """An EdgeView of the Graph as G.edges or G.edges().
1380 edges(self, nbunch=None, data=False, default=None)
1382 The EdgeView provides set-like operations on the edge-tuples
1383 as well as edge attribute lookup. When called, it also provides
1384 an EdgeDataView object which allows control of access to edge
1385 attributes (but does not provide set-like operations).
1386 Hence, `G.edges[u, v]['color']` provides the value of the color
1387 attribute for edge `(u, v)` while
1388 `for (u, v, c) in G.edges.data('color', default='red'):`
1389 iterates through all the edges yielding the color attribute
1390 with default `'red'` if no color attribute exists.
1392 Parameters
1393 ----------
1394 nbunch : single node, container, or all nodes (default= all nodes)
1395 The view will only report edges from these nodes.
1396 data : string or bool, optional (default=False)
1397 The edge attribute returned in 3-tuple (u, v, ddict[data]).
1398 If True, return edge attribute dict in 3-tuple (u, v, ddict).
1399 If False, return 2-tuple (u, v).
1400 default : value, optional (default=None)
1401 Value used for edges that don't have the requested attribute.
1402 Only relevant if data is not True or False.
1404 Returns
1405 -------
1406 edges : EdgeView
1407 A view of edge attributes, usually it iterates over (u, v)
1408 or (u, v, d) tuples of edges, but can also be used for
1409 attribute lookup as `edges[u, v]['foo']`.
1411 Notes
1412 -----
1413 Nodes in nbunch that are not in the graph will be (quietly) ignored.
1414 For directed graphs this returns the out-edges.
1416 Examples
1417 --------
1418 >>> G = nx.path_graph(3) # or MultiGraph, etc
1419 >>> G.add_edge(2, 3, weight=5)
1420 >>> [e for e in G.edges]
1421 [(0, 1), (1, 2), (2, 3)]
1422 >>> G.edges.data() # default data is {} (empty dict)
1423 EdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})])
1424 >>> G.edges.data("weight", default=1)
1425 EdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)])
1426 >>> G.edges([0, 3]) # only edges from these nodes
1427 EdgeDataView([(0, 1), (3, 2)])
1428 >>> G.edges(0) # only edges from node 0
1429 EdgeDataView([(0, 1)])
1430 """
1431 return EdgeView(self)
1433 def get_edge_data(self, u, v, default=None):
1434 """Returns the attribute dictionary associated with edge (u, v).
1436 This is identical to `G[u][v]` except the default is returned
1437 instead of an exception if the edge doesn't exist.
1439 Parameters
1440 ----------
1441 u, v : nodes
1442 default: any Python object (default=None)
1443 Value to return if the edge (u, v) is not found.
1445 Returns
1446 -------
1447 edge_dict : dictionary
1448 The edge attribute dictionary.
1450 Examples
1451 --------
1452 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1453 >>> G[0][1]
1454 {}
1456 Warning: Assigning to `G[u][v]` is not permitted.
1457 But it is safe to assign attributes `G[u][v]['foo']`
1459 >>> G[0][1]["weight"] = 7
1460 >>> G[0][1]["weight"]
1461 7
1462 >>> G[1][0]["weight"]
1463 7
1465 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1466 >>> G.get_edge_data(0, 1) # default edge data is {}
1467 {}
1468 >>> e = (0, 1)
1469 >>> G.get_edge_data(*e) # tuple form
1470 {}
1471 >>> G.get_edge_data("a", "b", default=0) # edge not in graph, return 0
1472 0
1473 """
1474 try:
1475 return self._adj[u][v]
1476 except KeyError:
1477 return default
1479 def adjacency(self):
1480 """Returns an iterator over (node, adjacency dict) tuples for all nodes.
1482 For directed graphs, only outgoing neighbors/adjacencies are included.
1484 Returns
1485 -------
1486 adj_iter : iterator
1487 An iterator over (node, adjacency dictionary) for all nodes in
1488 the graph.
1490 Examples
1491 --------
1492 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1493 >>> [(n, nbrdict) for n, nbrdict in G.adjacency()]
1494 [(0, {1: {}}), (1, {0: {}, 2: {}}), (2, {1: {}, 3: {}}), (3, {2: {}})]
1496 """
1497 return iter(self._adj.items())
1499 @cached_property
1500 def degree(self):
1501 """A DegreeView for the Graph as G.degree or G.degree().
1503 The node degree is the number of edges adjacent to the node.
1504 The weighted node degree is the sum of the edge weights for
1505 edges incident to that node.
1507 This object provides an iterator for (node, degree) as well as
1508 lookup for the degree for a single node.
1510 Parameters
1511 ----------
1512 nbunch : single node, container, or all nodes (default= all nodes)
1513 The view will only report edges incident to these nodes.
1515 weight : string or None, optional (default=None)
1516 The name of an edge attribute that holds the numerical value used
1517 as a weight. If None, then each edge has weight 1.
1518 The degree is the sum of the edge weights adjacent to the node.
1520 Returns
1521 -------
1522 DegreeView or int
1523 If multiple nodes are requested (the default), returns a `DegreeView`
1524 mapping nodes to their degree.
1525 If a single node is requested, returns the degree of the node as an integer.
1527 Examples
1528 --------
1529 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1530 >>> G.degree[0] # node 0 has degree 1
1531 1
1532 >>> list(G.degree([0, 1, 2]))
1533 [(0, 1), (1, 2), (2, 2)]
1534 """
1535 return DegreeView(self)
1537 def clear(self):
1538 """Remove all nodes and edges from the graph.
1540 This also removes the name, and all graph, node, and edge attributes.
1542 Examples
1543 --------
1544 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1545 >>> G.clear()
1546 >>> list(G.nodes)
1547 []
1548 >>> list(G.edges)
1549 []
1551 """
1552 self._adj.clear()
1553 self._node.clear()
1554 self.graph.clear()
1555 nx._clear_cache(self)
1557 def clear_edges(self):
1558 """Remove all edges from the graph without altering nodes.
1560 Examples
1561 --------
1562 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1563 >>> G.clear_edges()
1564 >>> list(G.nodes)
1565 [0, 1, 2, 3]
1566 >>> list(G.edges)
1567 []
1568 """
1569 for nbr_dict in self._adj.values():
1570 nbr_dict.clear()
1571 nx._clear_cache(self)
1573 def is_multigraph(self):
1574 """Returns True if graph is a multigraph, False otherwise."""
1575 return False
1577 def is_directed(self):
1578 """Returns True if graph is directed, False otherwise."""
1579 return False
1581 def copy(self, as_view=False):
1582 """Returns a copy of the graph.
1584 The copy method by default returns an independent shallow copy
1585 of the graph and attributes. That is, if an attribute is a
1586 container, that container is shared by the original an the copy.
1587 Use Python's `copy.deepcopy` for new containers.
1589 If `as_view` is True then a view is returned instead of a copy.
1591 Notes
1592 -----
1593 All copies reproduce the graph structure, but data attributes
1594 may be handled in different ways. There are four types of copies
1595 of a graph that people might want.
1597 Deepcopy -- A "deepcopy" copies the graph structure as well as
1598 all data attributes and any objects they might contain.
1599 The entire graph object is new so that changes in the copy
1600 do not affect the original object. (see Python's copy.deepcopy)
1602 Data Reference (Shallow) -- For a shallow copy the graph structure
1603 is copied but the edge, node and graph attribute dicts are
1604 references to those in the original graph. This saves
1605 time and memory but could cause confusion if you change an attribute
1606 in one graph and it changes the attribute in the other.
1607 NetworkX does not provide this level of shallow copy.
1609 Independent Shallow -- This copy creates new independent attribute
1610 dicts and then does a shallow copy of the attributes. That is, any
1611 attributes that are containers are shared between the new graph
1612 and the original. This is exactly what `dict.copy()` provides.
1613 You can obtain this style copy using:
1615 >>> G = nx.path_graph(5)
1616 >>> H = G.copy()
1617 >>> H = G.copy(as_view=False)
1618 >>> H = nx.Graph(G)
1619 >>> H = G.__class__(G)
1621 Fresh Data -- For fresh data, the graph structure is copied while
1622 new empty data attribute dicts are created. The resulting graph
1623 is independent of the original and it has no edge, node or graph
1624 attributes. Fresh copies are not enabled. Instead use:
1626 >>> H = G.__class__()
1627 >>> H.add_nodes_from(G)
1628 >>> H.add_edges_from(G.edges)
1630 View -- Inspired by dict-views, graph-views act like read-only
1631 versions of the original graph, providing a copy of the original
1632 structure without requiring any memory for copying the information.
1634 See the Python copy module for more information on shallow
1635 and deep copies, https://docs.python.org/3/library/copy.html.
1637 Parameters
1638 ----------
1639 as_view : bool, optional (default=False)
1640 If True, the returned graph-view provides a read-only view
1641 of the original graph without actually copying any data.
1643 Returns
1644 -------
1645 G : Graph
1646 A copy of the graph.
1648 See Also
1649 --------
1650 to_directed: return a directed copy of the graph.
1652 Examples
1653 --------
1654 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1655 >>> H = G.copy()
1657 """
1658 if as_view is True:
1659 return nx.graphviews.generic_graph_view(self)
1660 G = self.__class__()
1661 G.graph.update(self.graph)
1662 G.add_nodes_from((n, d.copy()) for n, d in self._node.items())
1663 G.add_edges_from(
1664 (u, v, datadict.copy())
1665 for u, nbrs in self._adj.items()
1666 for v, datadict in nbrs.items()
1667 )
1668 return G
1670 def to_directed(self, as_view=False):
1671 """Returns a directed representation of the graph.
1673 Returns
1674 -------
1675 G : DiGraph
1676 A directed graph with the same name, same nodes, and with
1677 each edge (u, v, data) replaced by two directed edges
1678 (u, v, data) and (v, u, data).
1680 Notes
1681 -----
1682 This returns a "deepcopy" of the edge, node, and
1683 graph attributes which attempts to completely copy
1684 all of the data and references.
1686 This is in contrast to the similar D=DiGraph(G) which returns a
1687 shallow copy of the data.
1689 See the Python copy module for more information on shallow
1690 and deep copies, https://docs.python.org/3/library/copy.html.
1692 Warning: If you have subclassed Graph to use dict-like objects
1693 in the data structure, those changes do not transfer to the
1694 DiGraph created by this method.
1696 Examples
1697 --------
1698 >>> G = nx.Graph() # or MultiGraph, etc
1699 >>> G.add_edge(0, 1)
1700 >>> H = G.to_directed()
1701 >>> list(H.edges)
1702 [(0, 1), (1, 0)]
1704 If already directed, return a (deep) copy
1706 >>> G = nx.DiGraph() # or MultiDiGraph, etc
1707 >>> G.add_edge(0, 1)
1708 >>> H = G.to_directed()
1709 >>> list(H.edges)
1710 [(0, 1)]
1711 """
1712 graph_class = self.to_directed_class()
1713 if as_view is True:
1714 return nx.graphviews.generic_graph_view(self, graph_class)
1715 # deepcopy when not a view
1716 G = graph_class()
1717 G.graph.update(deepcopy(self.graph))
1718 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1719 G.add_edges_from(
1720 (u, v, deepcopy(data))
1721 for u, nbrs in self._adj.items()
1722 for v, data in nbrs.items()
1723 )
1724 return G
1726 def to_undirected(self, as_view=False):
1727 """Returns an undirected copy of the graph.
1729 Parameters
1730 ----------
1731 as_view : bool (optional, default=False)
1732 If True return a view of the original undirected graph.
1734 Returns
1735 -------
1736 G : Graph/MultiGraph
1737 A deepcopy of the graph.
1739 See Also
1740 --------
1741 Graph, copy, add_edge, add_edges_from
1743 Notes
1744 -----
1745 This returns a "deepcopy" of the edge, node, and
1746 graph attributes which attempts to completely copy
1747 all of the data and references.
1749 This is in contrast to the similar `G = nx.DiGraph(D)` which returns a
1750 shallow copy of the data.
1752 See the Python copy module for more information on shallow
1753 and deep copies, https://docs.python.org/3/library/copy.html.
1755 Warning: If you have subclassed DiGraph to use dict-like objects
1756 in the data structure, those changes do not transfer to the
1757 Graph created by this method.
1759 Examples
1760 --------
1761 >>> G = nx.path_graph(2) # or MultiGraph, etc
1762 >>> H = G.to_directed()
1763 >>> list(H.edges)
1764 [(0, 1), (1, 0)]
1765 >>> G2 = H.to_undirected()
1766 >>> list(G2.edges)
1767 [(0, 1)]
1768 """
1769 graph_class = self.to_undirected_class()
1770 if as_view is True:
1771 return nx.graphviews.generic_graph_view(self, graph_class)
1772 # deepcopy when not a view
1773 G = graph_class()
1774 G.graph.update(deepcopy(self.graph))
1775 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1776 G.add_edges_from(
1777 (u, v, deepcopy(d))
1778 for u, nbrs in self._adj.items()
1779 for v, d in nbrs.items()
1780 )
1781 return G
1783 def subgraph(self, nodes):
1784 """Returns a SubGraph view of the subgraph induced on `nodes`.
1786 The induced subgraph of the graph contains the nodes in `nodes`
1787 and the edges between those nodes.
1789 Parameters
1790 ----------
1791 nodes : list, iterable
1792 A container of nodes which will be iterated through once.
1794 Returns
1795 -------
1796 G : SubGraph View
1797 A subgraph view of the graph. The graph structure cannot be
1798 changed but node/edge attributes can and are shared with the
1799 original graph.
1801 Notes
1802 -----
1803 The graph, edge and node attributes are shared with the original graph.
1804 Changes to the graph structure is ruled out by the view, but changes
1805 to attributes are reflected in the original graph.
1807 To create a subgraph with its own copy of the edge/node attributes use:
1808 G.subgraph(nodes).copy()
1810 For an inplace reduction of a graph to a subgraph you can remove nodes:
1811 G.remove_nodes_from([n for n in G if n not in set(nodes)])
1813 Subgraph views are sometimes NOT what you want. In most cases where
1814 you want to do more than simply look at the induced edges, it makes
1815 more sense to just create the subgraph as its own graph with code like:
1817 ::
1819 # Create a subgraph SG based on a (possibly multigraph) G
1820 SG = G.__class__()
1821 SG.add_nodes_from((n, G.nodes[n]) for n in largest_wcc)
1822 if SG.is_multigraph():
1823 SG.add_edges_from(
1824 (n, nbr, key, d)
1825 for n, nbrs in G.adj.items()
1826 if n in largest_wcc
1827 for nbr, keydict in nbrs.items()
1828 if nbr in largest_wcc
1829 for key, d in keydict.items()
1830 )
1831 else:
1832 SG.add_edges_from(
1833 (n, nbr, d)
1834 for n, nbrs in G.adj.items()
1835 if n in largest_wcc
1836 for nbr, d in nbrs.items()
1837 if nbr in largest_wcc
1838 )
1839 SG.graph.update(G.graph)
1841 Subgraphs are not guaranteed to preserve the order of nodes or edges
1842 as they appear in the original graph. For example:
1844 >>> G = nx.Graph()
1845 >>> G.add_nodes_from(reversed(range(10)))
1846 >>> list(G)
1847 [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
1848 >>> list(G.subgraph([1, 3, 2]))
1849 [1, 2, 3]
1851 Examples
1852 --------
1853 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1854 >>> H = G.subgraph([0, 1, 2])
1855 >>> list(H.edges)
1856 [(0, 1), (1, 2)]
1857 """
1858 induced_nodes = nx.filters.show_nodes(self.nbunch_iter(nodes))
1859 # if already a subgraph, don't make a chain
1860 subgraph = nx.subgraph_view
1861 if hasattr(self, "_NODE_OK"):
1862 return subgraph(
1863 self._graph, filter_node=induced_nodes, filter_edge=self._EDGE_OK
1864 )
1865 return subgraph(self, filter_node=induced_nodes)
1867 def edge_subgraph(self, edges):
1868 """Returns the subgraph induced by the specified edges.
1870 The induced subgraph contains each edge in `edges` and each
1871 node incident to any one of those edges.
1873 Parameters
1874 ----------
1875 edges : iterable
1876 An iterable of edges in this graph.
1878 Returns
1879 -------
1880 G : Graph
1881 An edge-induced subgraph of this graph with the same edge
1882 attributes.
1884 Notes
1885 -----
1886 The graph, edge, and node attributes in the returned subgraph
1887 view are references to the corresponding attributes in the original
1888 graph. The view is read-only.
1890 To create a full graph version of the subgraph with its own copy
1891 of the edge or node attributes, use::
1893 G.edge_subgraph(edges).copy()
1895 Examples
1896 --------
1897 >>> G = nx.path_graph(5)
1898 >>> H = G.edge_subgraph([(0, 1), (3, 4)])
1899 >>> list(H.nodes)
1900 [0, 1, 3, 4]
1901 >>> list(H.edges)
1902 [(0, 1), (3, 4)]
1904 """
1905 return nx.edge_subgraph(self, edges)
1907 def size(self, weight=None):
1908 """Returns the number of edges or total of all edge weights.
1910 Parameters
1911 ----------
1912 weight : string or None, optional (default=None)
1913 The edge attribute that holds the numerical value used
1914 as a weight. If None, then each edge has weight 1.
1916 Returns
1917 -------
1918 size : numeric
1919 The number of edges or
1920 (if weight keyword is provided) the total weight sum.
1922 If weight is None, returns an int. Otherwise a float
1923 (or more general numeric if the weights are more general).
1925 See Also
1926 --------
1927 number_of_edges
1929 Examples
1930 --------
1931 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1932 >>> G.size()
1933 3
1935 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1936 >>> G.add_edge("a", "b", weight=2)
1937 >>> G.add_edge("b", "c", weight=4)
1938 >>> G.size()
1939 2
1940 >>> G.size(weight="weight")
1941 6.0
1942 """
1943 s = sum(d for v, d in self.degree(weight=weight))
1944 # If `weight` is None, the sum of the degrees is guaranteed to be
1945 # even, so we can perform integer division and hence return an
1946 # integer. Otherwise, the sum of the weighted degrees is not
1947 # guaranteed to be an integer, so we perform "real" division.
1948 return s // 2 if weight is None else s / 2
1950 def number_of_edges(self, u=None, v=None):
1951 """Returns the number of edges between two nodes.
1953 Parameters
1954 ----------
1955 u, v : nodes, optional (default=all edges)
1956 If u and v are specified, return the number of edges between
1957 u and v. Otherwise return the total number of all edges.
1959 Returns
1960 -------
1961 nedges : int
1962 The number of edges in the graph. If nodes `u` and `v` are
1963 specified return the number of edges between those nodes. If
1964 the graph is directed, this only returns the number of edges
1965 from `u` to `v`.
1967 See Also
1968 --------
1969 size
1971 Examples
1972 --------
1973 For undirected graphs, this method counts the total number of
1974 edges in the graph:
1976 >>> G = nx.path_graph(4)
1977 >>> G.number_of_edges()
1978 3
1980 If you specify two nodes, this counts the total number of edges
1981 joining the two nodes:
1983 >>> G.number_of_edges(0, 1)
1984 1
1986 For directed graphs, this method can count the total number of
1987 directed edges from `u` to `v`:
1989 >>> G = nx.DiGraph()
1990 >>> G.add_edge(0, 1)
1991 >>> G.add_edge(1, 0)
1992 >>> G.number_of_edges(0, 1)
1993 1
1995 """
1996 if u is None:
1997 return int(self.size())
1998 if v in self._adj[u]:
1999 return 1
2000 return 0
2002 def nbunch_iter(self, nbunch=None):
2003 """Returns an iterator over nodes contained in nbunch that are
2004 also in the graph.
2006 The nodes in an iterable nbunch are checked for membership in the graph
2007 and if not are silently ignored.
2009 Parameters
2010 ----------
2011 nbunch : single node, container, or all nodes (default= all nodes)
2012 The view will only report edges incident to these nodes.
2014 Returns
2015 -------
2016 niter : iterator
2017 An iterator over nodes in nbunch that are also in the graph.
2018 If nbunch is None, iterate over all nodes in the graph.
2020 Raises
2021 ------
2022 NetworkXError
2023 If nbunch is not a node or sequence of nodes.
2024 If a node in nbunch is not hashable.
2026 See Also
2027 --------
2028 Graph.__iter__
2030 Notes
2031 -----
2032 When nbunch is an iterator, the returned iterator yields values
2033 directly from nbunch, becoming exhausted when nbunch is exhausted.
2035 To test whether nbunch is a single node, one can use
2036 "if nbunch in self:", even after processing with this routine.
2038 If nbunch is not a node or a (possibly empty) sequence/iterator
2039 or None, a :exc:`NetworkXError` is raised. Also, if any object in
2040 nbunch is not hashable, a :exc:`NetworkXError` is raised.
2041 """
2042 if nbunch is None: # include all nodes via iterator
2043 bunch = iter(self._adj)
2044 elif nbunch in self: # if nbunch is a single node
2045 bunch = iter([nbunch])
2046 else: # if nbunch is a sequence of nodes
2048 def bunch_iter(nlist, adj):
2049 try:
2050 for n in nlist:
2051 if n in adj:
2052 yield n
2053 except TypeError as err:
2054 exc, message = err, err.args[0]
2055 # capture error for non-sequence/iterator nbunch.
2056 if "iter" in message:
2057 exc = NetworkXError(
2058 "nbunch is not a node or a sequence of nodes."
2059 )
2060 # capture single nodes that are not in the graph.
2061 if "object is not iterable" in message:
2062 exc = NetworkXError(f"Node {nbunch} is not in the graph.")
2063 # capture error for unhashable node.
2064 if "hashable" in message:
2065 exc = NetworkXError(
2066 f"Node {n} in sequence nbunch is not a valid node."
2067 )
2068 raise exc
2070 bunch = bunch_iter(nbunch, self._adj)
2071 return bunch