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 MultiGraph."""
3from copy import deepcopy
4from functools import cached_property
6import networkx as nx
7from networkx import NetworkXError, convert
8from networkx.classes.coreviews import MultiAdjacencyView
9from networkx.classes.graph import Graph
10from networkx.classes.reportviews import MultiDegreeView, MultiEdgeView
12__all__ = ["MultiGraph"]
15class MultiGraph(Graph):
16 """
17 An undirected graph class that can store multiedges.
19 Multiedges are multiple edges between two nodes. Each edge
20 can hold optional data or attributes.
22 A MultiGraph holds undirected edges. Self loops are allowed.
24 Nodes can be arbitrary (hashable) Python objects with optional
25 key/value attributes. By convention `None` is not used as a node.
27 Edges are represented as links between nodes with optional
28 key/value attributes, in a MultiGraph each edge has a key to
29 distinguish between multiple edges that have the same source and
30 destination nodes.
32 Parameters
33 ----------
34 incoming_graph_data : input graph (optional, default: None)
35 Data to initialize graph. If None (default) an empty
36 graph is created. The data can be any format that is supported
37 by the to_networkx_graph() function, currently including edge list,
38 dict of dicts, dict of lists, NetworkX graph, 2D NumPy array,
39 SciPy sparse array, or PyGraphviz graph.
41 multigraph_input : bool or None (default None)
42 Note: Only used when `incoming_graph_data` is a dict.
43 If True, `incoming_graph_data` is assumed to be a
44 dict-of-dict-of-dict-of-dict structure keyed by
45 node to neighbor to edge keys to edge data for multi-edges.
46 A NetworkXError is raised if this is not the case.
47 If False, :func:`to_networkx_graph` is used to try to determine
48 the dict's graph data structure as either a dict-of-dict-of-dict
49 keyed by node to neighbor to edge data, or a dict-of-iterable
50 keyed by node to neighbors.
51 If None, the treatment for True is tried, but if it fails,
52 the treatment for False is tried.
54 attr : keyword arguments, optional (default= no attributes)
55 Attributes to add to graph as key=value pairs.
57 See Also
58 --------
59 Graph
60 DiGraph
61 MultiDiGraph
63 Examples
64 --------
65 Create an empty graph structure (a "null graph") with no nodes and
66 no edges.
68 >>> G = nx.MultiGraph()
70 G can be grown in several ways.
72 **Nodes:**
74 Add one node at a time:
76 >>> G.add_node(1)
78 Add the nodes from any container (a list, dict, set or
79 even the lines from a file or the nodes from another graph).
81 >>> G.add_nodes_from([2, 3])
82 >>> G.add_nodes_from(range(100, 110))
83 >>> H = nx.path_graph(10)
84 >>> G.add_nodes_from(H)
86 In addition to strings and integers any hashable Python object
87 (except None) can represent a node, e.g. a customized node object,
88 or even another Graph.
90 >>> G.add_node(H)
92 **Edges:**
94 G can also be grown by adding edges.
96 Add one edge,
98 >>> key = G.add_edge(1, 2)
100 a list of edges,
102 >>> keys = G.add_edges_from([(1, 2), (1, 3)])
104 or a collection of edges,
106 >>> keys = G.add_edges_from(H.edges)
108 If some edges connect nodes not yet in the graph, the nodes
109 are added automatically. If an edge already exists, an additional
110 edge is created and stored using a key to identify the edge.
111 By default the key is the lowest unused integer.
113 >>> keys = G.add_edges_from([(4, 5, {"route": 28}), (4, 5, {"route": 37})])
114 >>> G[4]
115 AdjacencyView({3: {0: {}}, 5: {0: {}, 1: {'route': 28}, 2: {'route': 37}}})
117 **Attributes:**
119 Each graph, node, and edge can hold key/value attribute pairs
120 in an associated attribute dictionary (the keys must be hashable).
121 By default these are empty, but can be added or changed using
122 add_edge, add_node or direct manipulation of the attribute
123 dictionaries named graph, node and edge respectively.
125 >>> G = nx.MultiGraph(day="Friday")
126 >>> G.graph
127 {'day': 'Friday'}
129 Add node attributes using add_node(), add_nodes_from() or G.nodes
131 >>> G.add_node(1, time="5pm")
132 >>> G.add_nodes_from([3], time="2pm")
133 >>> G.nodes[1]
134 {'time': '5pm'}
135 >>> G.nodes[1]["room"] = 714
136 >>> del G.nodes[1]["room"] # remove attribute
137 >>> list(G.nodes(data=True))
138 [(1, {'time': '5pm'}), (3, {'time': '2pm'})]
140 Add edge attributes using add_edge(), add_edges_from(), subscript
141 notation, or G.edges.
143 >>> key = G.add_edge(1, 2, weight=4.7)
144 >>> keys = G.add_edges_from([(3, 4), (4, 5)], color="red")
145 >>> keys = G.add_edges_from([(1, 2, {"color": "blue"}), (2, 3, {"weight": 8})])
146 >>> G[1][2][0]["weight"] = 4.7
147 >>> G.edges[1, 2, 0]["weight"] = 4
149 Warning: we protect the graph data structure by making `G.edges[1,
150 2, 0]` a read-only dict-like structure. However, you can assign to
151 attributes in e.g. `G.edges[1, 2, 0]`. Thus, use 2 sets of brackets
152 to add/change data attributes: `G.edges[1, 2, 0]['weight'] = 4`.
154 **Shortcuts:**
156 Many common graph features allow python syntax to speed reporting.
158 >>> 1 in G # check if node in graph
159 True
160 >>> [n for n in G if n < 3] # iterate through nodes
161 [1, 2]
162 >>> len(G) # number of nodes in graph
163 5
164 >>> G[1] # adjacency dict-like view mapping neighbor -> edge key -> edge attributes
165 AdjacencyView({2: {0: {'weight': 4}, 1: {'color': 'blue'}}})
167 Often the best way to traverse all edges of a graph is via the neighbors.
168 The neighbors are reported as an adjacency-dict `G.adj` or `G.adjacency()`.
170 >>> for n, nbrsdict in G.adjacency():
171 ... for nbr, keydict in nbrsdict.items():
172 ... for key, eattr in keydict.items():
173 ... if "weight" in eattr:
174 ... # Do something useful with the edges
175 ... pass
177 But the edges() method is often more convenient:
179 >>> for u, v, keys, weight in G.edges(data="weight", keys=True):
180 ... if weight is not None:
181 ... # Do something useful with the edges
182 ... pass
184 **Reporting:**
186 Simple graph information is obtained using methods and object-attributes.
187 Reporting usually provides views instead of containers to reduce memory
188 usage. The views update as the graph is updated similarly to dict-views.
189 The objects `nodes`, `edges` and `adj` provide access to data attributes
190 via lookup (e.g. `nodes[n]`, `edges[u, v, k]`, `adj[u][v]`) and iteration
191 (e.g. `nodes.items()`, `nodes.data('color')`,
192 `nodes.data('color', default='blue')` and similarly for `edges`)
193 Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`.
195 For details on these and other miscellaneous methods, see below.
197 **Subclasses (Advanced):**
199 The MultiGraph class uses a dict-of-dict-of-dict-of-dict data structure.
200 The outer dict (node_dict) holds adjacency information keyed by node.
201 The next dict (adjlist_dict) represents the adjacency information
202 and holds edge_key dicts keyed by neighbor. The edge_key dict holds
203 each edge_attr dict keyed by edge key. The inner dict
204 (edge_attr_dict) represents the edge data and holds edge attribute
205 values keyed by attribute names.
207 Each of these four dicts in the dict-of-dict-of-dict-of-dict
208 structure can be replaced by a user defined dict-like object.
209 In general, the dict-like features should be maintained but
210 extra features can be added. To replace one of the dicts create
211 a new graph class by changing the class(!) variable holding the
212 factory for that dict-like structure. The variable names are
213 node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory,
214 adjlist_outer_dict_factory, edge_key_dict_factory, edge_attr_dict_factory
215 and graph_attr_dict_factory.
217 node_dict_factory : function, (default: dict)
218 Factory function to be used to create the dict containing node
219 attributes, keyed by node id.
220 It should require no arguments and return a dict-like object
222 node_attr_dict_factory: function, (default: dict)
223 Factory function to be used to create the node attribute
224 dict which holds attribute values keyed by attribute name.
225 It should require no arguments and return a dict-like object
227 adjlist_outer_dict_factory : function, (default: dict)
228 Factory function to be used to create the outer-most dict
229 in the data structure that holds adjacency info keyed by node.
230 It should require no arguments and return a dict-like object.
232 adjlist_inner_dict_factory : function, (default: dict)
233 Factory function to be used to create the adjacency list
234 dict which holds multiedge key dicts keyed by neighbor.
235 It should require no arguments and return a dict-like object.
237 edge_key_dict_factory : function, (default: dict)
238 Factory function to be used to create the edge key dict
239 which holds edge data keyed by edge key.
240 It should require no arguments and return a dict-like object.
242 edge_attr_dict_factory : function, (default: dict)
243 Factory function to be used to create the edge attribute
244 dict which holds attribute values keyed by attribute name.
245 It should require no arguments and return a dict-like object.
247 graph_attr_dict_factory : function, (default: dict)
248 Factory function to be used to create the graph attribute
249 dict which holds attribute values keyed by attribute name.
250 It should require no arguments and return a dict-like object.
252 Typically, if your extension doesn't impact the data structure all
253 methods will inherited without issue except: `to_directed/to_undirected`.
254 By default these methods create a DiGraph/Graph class and you probably
255 want them to create your extension of a DiGraph/Graph. To facilitate
256 this we define two class variables that you can set in your subclass.
258 to_directed_class : callable, (default: DiGraph or MultiDiGraph)
259 Class to create a new graph structure in the `to_directed` method.
260 If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used.
262 to_undirected_class : callable, (default: Graph or MultiGraph)
263 Class to create a new graph structure in the `to_undirected` method.
264 If `None`, a NetworkX class (Graph or MultiGraph) is used.
266 **Subclassing Example**
268 Create a low memory graph class that effectively disallows edge
269 attributes by using a single attribute dict for all edges.
270 This reduces the memory used, but you lose edge attributes.
272 >>> class ThinGraph(nx.Graph):
273 ... all_edge_dict = {"weight": 1}
274 ...
275 ... def single_edge_dict(self):
276 ... return self.all_edge_dict
277 ...
278 ... edge_attr_dict_factory = single_edge_dict
279 >>> G = ThinGraph()
280 >>> G.add_edge(2, 1)
281 >>> G[2][1]
282 {'weight': 1}
283 >>> G.add_edge(2, 2)
284 >>> G[2][1] is G[2][2]
285 True
286 """
288 # node_dict_factory = dict # already assigned in Graph
289 # adjlist_outer_dict_factory = dict
290 # adjlist_inner_dict_factory = dict
291 edge_key_dict_factory = dict
292 # edge_attr_dict_factory = dict
294 def to_directed_class(self):
295 """Returns the class to use for empty directed copies.
297 If you subclass the base classes, use this to designate
298 what directed class to use for `to_directed()` copies.
299 """
300 return nx.MultiDiGraph
302 def to_undirected_class(self):
303 """Returns the class to use for empty undirected copies.
305 If you subclass the base classes, use this to designate
306 what directed class to use for `to_directed()` copies.
307 """
308 return MultiGraph
310 # This __new__ method just does what Python itself does automatically.
311 # We include it here as part of the dispatchable/backend interface.
312 # If your goal is to understand how the graph classes work, you can ignore
313 # this method, even when subclassing the base classes. If you are subclassing
314 # in order to provide a backend that allows class instantiation, this method
315 # can be overridden to return your own backend graph class.
316 @nx._dispatchable(name="multigraph__new__", graphs=None, returns_graph=True)
317 def __new__(cls, incoming_graph_data=None, multigraph_input=None, **attr):
318 return object.__new__(cls)
320 def __init__(self, incoming_graph_data=None, multigraph_input=None, **attr):
321 """Initialize a graph with edges, name, or graph attributes.
323 Parameters
324 ----------
325 incoming_graph_data : input graph
326 Data to initialize graph. If incoming_graph_data=None (default)
327 an empty graph is created. The data can be an edge list, or any
328 NetworkX graph object. If the corresponding optional Python
329 packages are installed the data can also be a 2D NumPy array, a
330 SciPy sparse array, or a PyGraphviz graph.
332 multigraph_input : bool or None (default None)
333 Note: Only used when `incoming_graph_data` is a dict.
334 If True, `incoming_graph_data` is assumed to be a
335 dict-of-dict-of-dict-of-dict structure keyed by
336 node to neighbor to edge keys to edge data for multi-edges.
337 A NetworkXError is raised if this is not the case.
338 If False, :func:`to_networkx_graph` is used to try to determine
339 the dict's graph data structure as either a dict-of-dict-of-dict
340 keyed by node to neighbor to edge data, or a dict-of-iterable
341 keyed by node to neighbors.
342 If None, the treatment for True is tried, but if it fails,
343 the treatment for False is tried.
345 attr : keyword arguments, optional (default= no attributes)
346 Attributes to add to graph as key=value pairs.
348 See Also
349 --------
350 convert
352 Examples
353 --------
354 >>> G = nx.MultiGraph()
355 >>> G = nx.MultiGraph(name="my graph")
356 >>> e = [(1, 2), (1, 2), (2, 3), (3, 4)] # list of edges
357 >>> G = nx.MultiGraph(e)
359 Arbitrary graph attribute pairs (key=value) may be assigned
361 >>> G = nx.MultiGraph(e, day="Friday")
362 >>> G.graph
363 {'day': 'Friday'}
365 """
366 attr.pop("backend", None) # Ignore explicit `backend="networkx"`
367 # multigraph_input can be None/True/False. So check "is not False"
368 if isinstance(incoming_graph_data, dict) and multigraph_input is not False:
369 Graph.__init__(self)
370 try:
371 convert.from_dict_of_dicts(
372 incoming_graph_data, create_using=self, multigraph_input=True
373 )
374 self.graph.update(attr)
375 except Exception as err:
376 if multigraph_input is True:
377 raise nx.NetworkXError(
378 f"converting multigraph_input raised:\n{type(err)}: {err}"
379 )
380 Graph.__init__(self, incoming_graph_data, **attr)
381 else:
382 Graph.__init__(self, incoming_graph_data, **attr)
384 @cached_property
385 def adj(self):
386 """Graph adjacency object holding the neighbors of each node.
388 This object is a read-only dict-like structure with node keys
389 and neighbor-dict values. The neighbor-dict is keyed by neighbor
390 to the edgekey-data-dict. So `G.adj[3][2][0]['color'] = 'blue'` sets
391 the color of the edge `(3, 2, 0)` to `"blue"`.
393 Iterating over G.adj behaves like a dict. Useful idioms include
394 `for nbr, edgesdict in G.adj[n].items():`.
396 The neighbor information is also provided by subscripting the graph.
398 Examples
399 --------
400 >>> e = [(1, 2), (1, 2), (1, 3), (3, 4)] # list of edges
401 >>> G = nx.MultiGraph(e)
402 >>> G.edges[1, 2, 0]["weight"] = 3
403 >>> result = set()
404 >>> for edgekey, data in G[1][2].items():
405 ... result.add(data.get("weight", 1))
406 >>> result
407 {1, 3}
409 For directed graphs, `G.adj` holds outgoing (successor) info.
410 """
411 return MultiAdjacencyView(self._adj)
413 def new_edge_key(self, u, v):
414 """Returns an unused key for edges between nodes `u` and `v`.
416 The nodes `u` and `v` do not need to be already in the graph.
418 Notes
419 -----
420 In the standard MultiGraph class the new key is the number of existing
421 edges between `u` and `v` (increased if necessary to ensure unused).
422 The first edge will have key 0, then 1, etc. If an edge is removed
423 further new_edge_keys may not be in this order.
425 Parameters
426 ----------
427 u, v : nodes
429 Returns
430 -------
431 key : int
432 """
433 try:
434 keydict = self._adj[u][v]
435 except KeyError:
436 return 0
437 key = len(keydict)
438 while key in keydict:
439 key += 1
440 return key
442 def add_edge(self, u_for_edge, v_for_edge, key=None, **attr):
443 """Add an edge between u and v.
445 The nodes u and v will be automatically added if they are
446 not already in the graph.
448 Edge attributes can be specified with keywords or by directly
449 accessing the edge's attribute dictionary. See examples below.
451 Parameters
452 ----------
453 u_for_edge, v_for_edge : nodes
454 Nodes can be, for example, strings or numbers.
455 Nodes must be hashable (and not None) Python objects.
456 key : hashable identifier, optional (default=lowest unused integer)
457 Used to distinguish multiedges between a pair of nodes.
458 attr : keyword arguments, optional
459 Edge data (or labels or objects) can be assigned using
460 keyword arguments.
462 Returns
463 -------
464 The edge key assigned to the edge.
466 See Also
467 --------
468 add_edges_from : add a collection of edges
470 Notes
471 -----
472 To replace/update edge data, use the optional key argument
473 to identify a unique edge. Otherwise a new edge will be created.
475 NetworkX algorithms designed for weighted graphs cannot use
476 multigraphs directly because it is not clear how to handle
477 multiedge weights. Convert to Graph using edge attribute
478 'weight' to enable weighted graph algorithms.
480 Default keys are generated using the method `new_edge_key()`.
481 This method can be overridden by subclassing the base class and
482 providing a custom `new_edge_key()` method.
484 Examples
485 --------
486 The following each add an additional edge e=(1, 2) to graph G:
488 >>> G = nx.MultiGraph()
489 >>> e = (1, 2)
490 >>> ekey = G.add_edge(1, 2) # explicit two-node form
491 >>> G.add_edge(*e) # single edge as tuple of two nodes
492 1
493 >>> G.add_edges_from([(1, 2)]) # add edges from iterable container
494 [2]
496 Associate data to edges using keywords:
498 >>> ekey = G.add_edge(1, 2, weight=3)
499 >>> ekey = G.add_edge(1, 2, key=0, weight=4) # update data for key=0
500 >>> ekey = G.add_edge(1, 3, weight=7, capacity=15, length=342.7)
502 For non-string attribute keys, use subscript notation.
504 >>> ekey = G.add_edge(1, 2)
505 >>> G[1][2][0].update({0: 5})
506 >>> G.edges[1, 2, 0].update({0: 5})
507 """
508 u, v = u_for_edge, v_for_edge
509 # add nodes
510 if u not in self._adj:
511 if u is None:
512 raise ValueError("None cannot be a node")
513 self._adj[u] = self.adjlist_inner_dict_factory()
514 self._node[u] = self.node_attr_dict_factory()
515 if v not in self._adj:
516 if v is None:
517 raise ValueError("None cannot be a node")
518 self._adj[v] = self.adjlist_inner_dict_factory()
519 self._node[v] = self.node_attr_dict_factory()
520 if key is None:
521 key = self.new_edge_key(u, v)
522 if v in self._adj[u]:
523 keydict = self._adj[u][v]
524 datadict = keydict.get(key, self.edge_attr_dict_factory())
525 datadict.update(attr)
526 keydict[key] = datadict
527 else:
528 # selfloops work this way without special treatment
529 datadict = self.edge_attr_dict_factory()
530 datadict.update(attr)
531 keydict = self.edge_key_dict_factory()
532 keydict[key] = datadict
533 self._adj[u][v] = keydict
534 self._adj[v][u] = keydict
535 nx._clear_cache(self)
536 return key
538 def add_edges_from(self, ebunch_to_add, **attr):
539 """Add all the edges in ebunch_to_add.
541 Parameters
542 ----------
543 ebunch_to_add : container of edges
544 Each edge given in the container will be added to the
545 graph. The edges can be:
547 - 2-tuples (u, v) or
548 - 3-tuples (u, v, d) for an edge data dict d, or
549 - 3-tuples (u, v, k) for not iterable key k, or
550 - 4-tuples (u, v, k, d) for an edge with data and key k
552 attr : keyword arguments, optional
553 Edge data (or labels or objects) can be assigned using
554 keyword arguments.
556 Returns
557 -------
558 A list of edge keys assigned to the edges in `ebunch`.
560 See Also
561 --------
562 add_edge : add a single edge
563 add_weighted_edges_from : convenient way to add weighted edges
565 Notes
566 -----
567 Adding the same edge twice has no effect but any edge data
568 will be updated when each duplicate edge is added.
570 Edge attributes specified in an ebunch take precedence over
571 attributes specified via keyword arguments.
573 Default keys are generated using the method ``new_edge_key()``.
574 This method can be overridden by subclassing the base class and
575 providing a custom ``new_edge_key()`` method.
577 When adding edges from an iterator over the graph you are changing,
578 a `RuntimeError` can be raised with message:
579 `RuntimeError: dictionary changed size during iteration`. This
580 happens when the graph's underlying dictionary is modified during
581 iteration. To avoid this error, evaluate the iterator into a separate
582 object, e.g. by using `list(iterator_of_edges)`, and pass this
583 object to `G.add_edges_from`.
585 Examples
586 --------
587 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
588 >>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples
589 >>> e = zip(range(0, 3), range(1, 4))
590 >>> G.add_edges_from(e) # Add the path graph 0-1-2-3
592 Associate data to edges
594 >>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
595 >>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898")
597 Evaluate an iterator over a graph if using it to modify the same graph
599 >>> G = nx.MultiGraph([(1, 2), (2, 3), (3, 4)])
600 >>> # Grow graph by one new node, adding edges to all existing nodes.
601 >>> # wrong way - will raise RuntimeError
602 >>> # G.add_edges_from(((5, n) for n in G.nodes))
603 >>> # right way - note that there will be no self-edge for node 5
604 >>> assigned_keys = G.add_edges_from(list((5, n) for n in G.nodes))
605 """
606 keylist = []
607 for e in ebunch_to_add:
608 ne = len(e)
609 if ne == 4:
610 u, v, key, dd = e
611 elif ne == 3:
612 u, v, dd = e
613 key = None
614 elif ne == 2:
615 u, v = e
616 dd = {}
617 key = None
618 else:
619 msg = f"Edge tuple {e} must be a 2-tuple, 3-tuple or 4-tuple."
620 raise NetworkXError(msg)
621 ddd = {}
622 ddd.update(attr)
623 try:
624 ddd.update(dd)
625 except (TypeError, ValueError):
626 if ne != 3:
627 raise
628 key = dd # ne == 3 with 3rd value not dict, must be a key
629 key = self.add_edge(u, v, key)
630 self[u][v][key].update(ddd)
631 keylist.append(key)
632 nx._clear_cache(self)
633 return keylist
635 def remove_edge(self, u, v, key=None):
636 """Remove an edge between u and v.
638 Parameters
639 ----------
640 u, v : nodes
641 Remove an edge between nodes u and v.
642 key : hashable identifier, optional (default=None)
643 Used to distinguish multiple edges between a pair of nodes.
644 If None, remove a single edge between u and v. If there are
645 multiple edges, removes the last edge added in terms of
646 insertion order.
648 Raises
649 ------
650 NetworkXError
651 If there is not an edge between u and v, or
652 if there is no edge with the specified key.
654 See Also
655 --------
656 remove_edges_from : remove a collection of edges
658 Examples
659 --------
660 >>> G = nx.MultiGraph()
661 >>> nx.add_path(G, [0, 1, 2, 3])
662 >>> G.remove_edge(0, 1)
663 >>> e = (1, 2)
664 >>> G.remove_edge(*e) # unpacks e from an edge tuple
666 For multiple edges
668 >>> G = nx.MultiGraph() # or MultiDiGraph, etc
669 >>> G.add_edges_from([(1, 2), (1, 2), (1, 2)]) # key_list returned
670 [0, 1, 2]
672 When ``key=None`` (the default), edges are removed in the opposite
673 order that they were added:
675 >>> G.remove_edge(1, 2)
676 >>> G.edges(keys=True)
677 MultiEdgeView([(1, 2, 0), (1, 2, 1)])
678 >>> G.remove_edge(2, 1) # edges are not directed
679 >>> G.edges(keys=True)
680 MultiEdgeView([(1, 2, 0)])
682 For edges with keys
684 >>> G = nx.MultiGraph()
685 >>> G.add_edge(1, 2, key="first")
686 'first'
687 >>> G.add_edge(1, 2, key="second")
688 'second'
689 >>> G.remove_edge(1, 2, key="first")
690 >>> G.edges(keys=True)
691 MultiEdgeView([(1, 2, 'second')])
693 """
694 try:
695 d = self._adj[u][v]
696 except KeyError as err:
697 raise NetworkXError(f"The edge {u}-{v} is not in the graph.") from err
698 # remove the edge with specified data
699 if key is None:
700 d.popitem()
701 else:
702 try:
703 del d[key]
704 except KeyError as err:
705 msg = f"The edge {u}-{v} with key {key} is not in the graph."
706 raise NetworkXError(msg) from err
707 if len(d) == 0:
708 # remove the key entries if last edge
709 del self._adj[u][v]
710 if u != v: # check for selfloop
711 del self._adj[v][u]
712 nx._clear_cache(self)
714 def remove_edges_from(self, ebunch):
715 """Remove all edges specified in ebunch.
717 Parameters
718 ----------
719 ebunch: list or container of edge tuples
720 Each edge given in the list or container will be removed
721 from the graph. The edges can be:
723 - 2-tuples (u, v) A single edge between u and v is removed.
724 - 3-tuples (u, v, key) The edge identified by key is removed.
725 - 4-tuples (u, v, key, data) where data is ignored.
727 See Also
728 --------
729 remove_edge : remove a single edge
731 Notes
732 -----
733 Will fail silently if an edge in ebunch is not in the graph.
735 Examples
736 --------
737 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
738 >>> ebunch = [(1, 2), (2, 3)]
739 >>> G.remove_edges_from(ebunch)
741 Removing multiple copies of edges
743 >>> G = nx.MultiGraph()
744 >>> keys = G.add_edges_from([(1, 2), (1, 2), (1, 2)])
745 >>> G.remove_edges_from([(1, 2), (2, 1)]) # edges aren't directed
746 >>> list(G.edges())
747 [(1, 2)]
748 >>> G.remove_edges_from([(1, 2), (1, 2)]) # silently ignore extra copy
749 >>> list(G.edges) # now empty graph
750 []
752 When the edge is a 2-tuple ``(u, v)`` but there are multiple edges between
753 u and v in the graph, the most recent edge (in terms of insertion
754 order) is removed.
756 >>> G = nx.MultiGraph()
757 >>> for key in ("x", "y", "a"):
758 ... k = G.add_edge(0, 1, key=key)
759 >>> G.edges(keys=True)
760 MultiEdgeView([(0, 1, 'x'), (0, 1, 'y'), (0, 1, 'a')])
761 >>> G.remove_edges_from([(0, 1)])
762 >>> G.edges(keys=True)
763 MultiEdgeView([(0, 1, 'x'), (0, 1, 'y')])
765 """
766 for e in ebunch:
767 try:
768 self.remove_edge(*e[:3])
769 except NetworkXError:
770 pass
771 nx._clear_cache(self)
773 def has_edge(self, u, v, key=None):
774 """Returns True if the graph has an edge between nodes u and v.
776 This is the same as `v in G[u] or key in G[u][v]`
777 without KeyError exceptions.
779 Parameters
780 ----------
781 u, v : nodes
782 Nodes can be, for example, strings or numbers.
784 key : hashable identifier, optional (default=None)
785 If specified return True only if the edge with
786 key is found.
788 Returns
789 -------
790 edge_ind : bool
791 True if edge is in the graph, False otherwise.
793 Examples
794 --------
795 Can be called either using two nodes u, v, an edge tuple (u, v),
796 or an edge tuple (u, v, key).
798 >>> G = nx.MultiGraph() # or MultiDiGraph
799 >>> nx.add_path(G, [0, 1, 2, 3])
800 >>> G.has_edge(0, 1) # using two nodes
801 True
802 >>> e = (0, 1)
803 >>> G.has_edge(*e) # e is a 2-tuple (u, v)
804 True
805 >>> G.add_edge(0, 1, key="a")
806 'a'
807 >>> G.has_edge(0, 1, key="a") # specify key
808 True
809 >>> G.has_edge(1, 0, key="a") # edges aren't directed
810 True
811 >>> e = (0, 1, "a")
812 >>> G.has_edge(*e) # e is a 3-tuple (u, v, 'a')
813 True
815 The following syntax are equivalent:
817 >>> G.has_edge(0, 1)
818 True
819 >>> 1 in G[0] # though this gives :exc:`KeyError` if 0 not in G
820 True
821 >>> 0 in G[1] # other order; also gives :exc:`KeyError` if 0 not in G
822 True
824 """
825 try:
826 if key is None:
827 return v in self._adj[u]
828 else:
829 return key in self._adj[u][v]
830 except KeyError:
831 return False
833 @cached_property
834 def edges(self):
835 """Returns an iterator over the edges.
837 edges(self, nbunch=None, data=False, keys=False, default=None)
839 The MultiEdgeView provides set-like operations on the edge-tuples
840 as well as edge attribute lookup. When called, it also provides
841 an EdgeDataView object which allows control of access to edge
842 attributes (but does not provide set-like operations).
843 Hence, ``G.edges[u, v, k]['color']`` provides the value of the color
844 attribute for the edge from ``u`` to ``v`` with key ``k`` while
845 ``for (u, v, k, c) in G.edges(data='color', keys=True, default="red"):``
846 iterates through all the edges yielding the color attribute with
847 default `'red'` if no color attribute exists.
849 Edges are returned as tuples with optional data and keys
850 in the order (node, neighbor, key, data). If ``keys=True`` is not
851 provided, the tuples will just be (node, neighbor, data), but
852 multiple tuples with the same node and neighbor will be generated
853 when multiple edges exist between two nodes.
855 Parameters
856 ----------
857 nbunch : single node, container, or all nodes (default= all nodes)
858 The view will only report edges from these nodes.
859 data : string or bool, optional (default=False)
860 The edge attribute returned in 3-tuple (u, v, ddict[data]).
861 If True, return edge attribute dict in 3-tuple (u, v, ddict).
862 If False, return 2-tuple (u, v).
863 keys : bool, optional (default=False)
864 If True, return edge keys with each edge, creating (u, v, k)
865 tuples or (u, v, k, d) tuples if data is also requested.
866 default : value, optional (default=None)
867 Value used for edges that don't have the requested attribute.
868 Only relevant if data is not True or False.
870 Returns
871 -------
872 edges : MultiEdgeView
873 A view of edge attributes, usually it iterates over (u, v)
874 (u, v, k) or (u, v, k, d) tuples of edges, but can also be
875 used for attribute lookup as ``edges[u, v, k]['foo']``.
877 Notes
878 -----
879 Nodes in nbunch that are not in the graph will be (quietly) ignored.
880 For directed graphs this returns the out-edges.
882 Examples
883 --------
884 >>> G = nx.MultiGraph()
885 >>> nx.add_path(G, [0, 1, 2])
886 >>> key = G.add_edge(2, 3, weight=5)
887 >>> key2 = G.add_edge(2, 1, weight=2) # multi-edge
888 >>> [e for e in G.edges()]
889 [(0, 1), (1, 2), (1, 2), (2, 3)]
890 >>> G.edges.data() # default data is {} (empty dict)
891 MultiEdgeDataView([(0, 1, {}), (1, 2, {}), (1, 2, {'weight': 2}), (2, 3, {'weight': 5})])
892 >>> G.edges.data("weight", default=1)
893 MultiEdgeDataView([(0, 1, 1), (1, 2, 1), (1, 2, 2), (2, 3, 5)])
894 >>> G.edges(keys=True) # default keys are integers
895 MultiEdgeView([(0, 1, 0), (1, 2, 0), (1, 2, 1), (2, 3, 0)])
896 >>> G.edges.data(keys=True)
897 MultiEdgeDataView([(0, 1, 0, {}), (1, 2, 0, {}), (1, 2, 1, {'weight': 2}), (2, 3, 0, {'weight': 5})])
898 >>> G.edges.data("weight", default=1, keys=True)
899 MultiEdgeDataView([(0, 1, 0, 1), (1, 2, 0, 1), (1, 2, 1, 2), (2, 3, 0, 5)])
900 >>> G.edges([0, 3]) # Note ordering of tuples from listed sources
901 MultiEdgeDataView([(0, 1), (3, 2)])
902 >>> G.edges([0, 3, 2, 1]) # Note ordering of tuples
903 MultiEdgeDataView([(0, 1), (3, 2), (2, 1), (2, 1)])
904 >>> G.edges(0)
905 MultiEdgeDataView([(0, 1)])
906 """
907 return MultiEdgeView(self)
909 def get_edge_data(self, u, v, key=None, default=None):
910 """Returns the attribute dictionary associated with edge (u, v,
911 key).
913 If a key is not provided, returns a dictionary mapping edge keys
914 to attribute dictionaries for each edge between u and v.
916 This is identical to `G[u][v][key]` except the default is returned
917 instead of an exception is the edge doesn't exist.
919 Parameters
920 ----------
921 u, v : nodes
923 default : any Python object (default=None)
924 Value to return if the specific edge (u, v, key) is not
925 found, OR if there are no edges between u and v and no key
926 is specified.
928 key : hashable identifier, optional (default=None)
929 Return data only for the edge with specified key, as an
930 attribute dictionary (rather than a dictionary mapping keys
931 to attribute dictionaries).
933 Returns
934 -------
935 edge_dict : dictionary
936 The edge attribute dictionary, OR a dictionary mapping edge
937 keys to attribute dictionaries for each of those edges if no
938 specific key is provided (even if there's only one edge
939 between u and v).
941 Examples
942 --------
943 >>> G = nx.MultiGraph() # or MultiDiGraph
944 >>> key = G.add_edge(0, 1, key="a", weight=7)
945 >>> G[0][1]["a"] # key='a'
946 {'weight': 7}
947 >>> G.edges[0, 1, "a"] # key='a'
948 {'weight': 7}
950 Warning: we protect the graph data structure by making
951 `G.edges` and `G[1][2]` read-only dict-like structures.
952 However, you can assign values to attributes in e.g.
953 `G.edges[1, 2, 'a']` or `G[1][2]['a']` using an additional
954 bracket as shown next. You need to specify all edge info
955 to assign to the edge data associated with an edge.
957 >>> G[0][1]["a"]["weight"] = 10
958 >>> G.edges[0, 1, "a"]["weight"] = 10
959 >>> G[0][1]["a"]["weight"]
960 10
961 >>> G.edges[1, 0, "a"]["weight"]
962 10
964 >>> G = nx.MultiGraph() # or MultiDiGraph
965 >>> nx.add_path(G, [0, 1, 2, 3])
966 >>> G.edges[0, 1, 0]["weight"] = 5
967 >>> G.get_edge_data(0, 1)
968 {0: {'weight': 5}}
969 >>> e = (0, 1)
970 >>> G.get_edge_data(*e) # tuple form
971 {0: {'weight': 5}}
972 >>> G.get_edge_data(3, 0) # edge not in graph, returns None
973 >>> G.get_edge_data(3, 0, default=0) # edge not in graph, return default
974 0
975 >>> G.get_edge_data(1, 0, 0) # specific key gives back
976 {'weight': 5}
977 """
978 try:
979 if key is None:
980 return self._adj[u][v]
981 else:
982 return self._adj[u][v][key]
983 except KeyError:
984 return default
986 @cached_property
987 def degree(self):
988 """A DegreeView for the Graph as G.degree or G.degree().
990 The node degree is the number of edges adjacent to the node.
991 The weighted node degree is the sum of the edge weights for
992 edges incident to that node.
994 This object provides an iterator for (node, degree) as well as
995 lookup for the degree for a single node.
997 Parameters
998 ----------
999 nbunch : single node, container, or all nodes (default= all nodes)
1000 The view will only report edges incident to these nodes.
1002 weight : string or None, optional (default=None)
1003 The name of an edge attribute that holds the numerical value used
1004 as a weight. If None, then each edge has weight 1.
1005 The degree is the sum of the edge weights adjacent to the node.
1007 Returns
1008 -------
1009 MultiDegreeView or int
1010 If multiple nodes are requested (the default), returns a `MultiDegreeView`
1011 mapping nodes to their degree.
1012 If a single node is requested, returns the degree of the node as an integer.
1014 Examples
1015 --------
1016 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1017 >>> nx.add_path(G, [0, 1, 2, 3])
1018 >>> G.degree(0) # node 0 with degree 1
1019 1
1020 >>> list(G.degree([0, 1]))
1021 [(0, 1), (1, 2)]
1023 """
1024 return MultiDegreeView(self)
1026 def is_multigraph(self):
1027 """Returns True if graph is a multigraph, False otherwise."""
1028 return True
1030 def is_directed(self):
1031 """Returns True if graph is directed, False otherwise."""
1032 return False
1034 def copy(self, as_view=False):
1035 """Returns a copy of the graph.
1037 The copy method by default returns an independent shallow copy
1038 of the graph and attributes. That is, if an attribute is a
1039 container, that container is shared by the original an the copy.
1040 Use Python's `copy.deepcopy` for new containers.
1042 If `as_view` is True then a view is returned instead of a copy.
1044 Notes
1045 -----
1046 All copies reproduce the graph structure, but data attributes
1047 may be handled in different ways. There are four types of copies
1048 of a graph that people might want.
1050 Deepcopy -- A "deepcopy" copies the graph structure as well as
1051 all data attributes and any objects they might contain.
1052 The entire graph object is new so that changes in the copy
1053 do not affect the original object. (see Python's copy.deepcopy)
1055 Data Reference (Shallow) -- For a shallow copy the graph structure
1056 is copied but the edge, node and graph attribute dicts are
1057 references to those in the original graph. This saves
1058 time and memory but could cause confusion if you change an attribute
1059 in one graph and it changes the attribute in the other.
1060 NetworkX does not provide this level of shallow copy.
1062 Independent Shallow -- This copy creates new independent attribute
1063 dicts and then does a shallow copy of the attributes. That is, any
1064 attributes that are containers are shared between the new graph
1065 and the original. This is exactly what `dict.copy()` provides.
1066 You can obtain this style copy using:
1068 >>> G = nx.path_graph(5)
1069 >>> H = G.copy()
1070 >>> H = G.copy(as_view=False)
1071 >>> H = nx.Graph(G)
1072 >>> H = G.__class__(G)
1074 Fresh Data -- For fresh data, the graph structure is copied while
1075 new empty data attribute dicts are created. The resulting graph
1076 is independent of the original and it has no edge, node or graph
1077 attributes. Fresh copies are not enabled. Instead use:
1079 >>> H = G.__class__()
1080 >>> H.add_nodes_from(G)
1081 >>> H.add_edges_from(G.edges)
1083 View -- Inspired by dict-views, graph-views act like read-only
1084 versions of the original graph, providing a copy of the original
1085 structure without requiring any memory for copying the information.
1087 See the Python copy module for more information on shallow
1088 and deep copies, https://docs.python.org/3/library/copy.html.
1090 Parameters
1091 ----------
1092 as_view : bool, optional (default=False)
1093 If True, the returned graph-view provides a read-only view
1094 of the original graph without actually copying any data.
1096 Returns
1097 -------
1098 G : Graph
1099 A copy of the graph.
1101 See Also
1102 --------
1103 to_directed: return a directed copy of the graph.
1105 Examples
1106 --------
1107 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
1108 >>> H = G.copy()
1110 """
1111 if as_view is True:
1112 return nx.graphviews.generic_graph_view(self)
1113 G = self.__class__()
1114 G.graph.update(self.graph)
1115 G.add_nodes_from((n, d.copy()) for n, d in self._node.items())
1116 G.add_edges_from(
1117 (u, v, key, datadict.copy())
1118 for u, nbrs in self._adj.items()
1119 for v, keydict in nbrs.items()
1120 for key, datadict in keydict.items()
1121 )
1122 return G
1124 def to_directed(self, as_view=False):
1125 """Returns a directed representation of the graph.
1127 Returns
1128 -------
1129 G : MultiDiGraph
1130 A directed graph with the same name, same nodes, and with
1131 each edge (u, v, k, data) replaced by two directed edges
1132 (u, v, k, data) and (v, u, k, data).
1134 Notes
1135 -----
1136 This returns a "deepcopy" of the edge, node, and
1137 graph attributes which attempts to completely copy
1138 all of the data and references.
1140 This is in contrast to the similar D=MultiDiGraph(G) which
1141 returns a shallow copy of the data.
1143 See the Python copy module for more information on shallow
1144 and deep copies, https://docs.python.org/3/library/copy.html.
1146 Warning: If you have subclassed MultiGraph to use dict-like objects
1147 in the data structure, those changes do not transfer to the
1148 MultiDiGraph created by this method.
1150 Examples
1151 --------
1152 >>> G = nx.MultiGraph()
1153 >>> G.add_edge(0, 1)
1154 0
1155 >>> G.add_edge(0, 1)
1156 1
1157 >>> H = G.to_directed()
1158 >>> list(H.edges)
1159 [(0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1)]
1161 If already directed, return a (deep) copy
1163 >>> G = nx.MultiDiGraph()
1164 >>> G.add_edge(0, 1)
1165 0
1166 >>> H = G.to_directed()
1167 >>> list(H.edges)
1168 [(0, 1, 0)]
1169 """
1170 graph_class = self.to_directed_class()
1171 if as_view is True:
1172 return nx.graphviews.generic_graph_view(self, graph_class)
1173 # deepcopy when not a view
1174 G = graph_class()
1175 G.graph.update(deepcopy(self.graph))
1176 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1177 G.add_edges_from(
1178 (u, v, key, deepcopy(datadict))
1179 for u, nbrs in self.adj.items()
1180 for v, keydict in nbrs.items()
1181 for key, datadict in keydict.items()
1182 )
1183 return G
1185 def to_undirected(self, as_view=False):
1186 """Returns an undirected copy of the graph.
1188 Returns
1189 -------
1190 G : Graph/MultiGraph
1191 A deepcopy of the graph.
1193 See Also
1194 --------
1195 copy, add_edge, add_edges_from
1197 Notes
1198 -----
1199 This returns a "deepcopy" of the edge, node, and
1200 graph attributes which attempts to completely copy
1201 all of the data and references.
1203 This is in contrast to the similar `G = nx.MultiGraph(D)`
1204 which returns a shallow copy of the data.
1206 See the Python copy module for more information on shallow
1207 and deep copies, https://docs.python.org/3/library/copy.html.
1209 Warning: If you have subclassed MultiGraph to use dict-like
1210 objects in the data structure, those changes do not transfer
1211 to the MultiGraph created by this method.
1213 Examples
1214 --------
1215 >>> G = nx.MultiGraph([(0, 1), (0, 1), (1, 2)])
1216 >>> H = G.to_directed()
1217 >>> list(H.edges)
1218 [(0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 2, 0), (2, 1, 0)]
1219 >>> G2 = H.to_undirected()
1220 >>> list(G2.edges)
1221 [(0, 1, 0), (0, 1, 1), (1, 2, 0)]
1222 """
1223 graph_class = self.to_undirected_class()
1224 if as_view is True:
1225 return nx.graphviews.generic_graph_view(self, graph_class)
1226 # deepcopy when not a view
1227 G = graph_class()
1228 G.graph.update(deepcopy(self.graph))
1229 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
1230 G.add_edges_from(
1231 (u, v, key, deepcopy(datadict))
1232 for u, nbrs in self._adj.items()
1233 for v, keydict in nbrs.items()
1234 for key, datadict in keydict.items()
1235 )
1236 return G
1238 def number_of_edges(self, u=None, v=None):
1239 """Returns the number of edges between two nodes.
1241 Parameters
1242 ----------
1243 u, v : nodes, optional (Default=all edges)
1244 If u and v are specified, return the number of edges between
1245 u and v. Otherwise return the total number of all edges.
1247 Returns
1248 -------
1249 nedges : int
1250 The number of edges in the graph. If nodes `u` and `v` are
1251 specified return the number of edges between those nodes. If
1252 the graph is directed, this only returns the number of edges
1253 from `u` to `v`.
1255 See Also
1256 --------
1257 size
1259 Examples
1260 --------
1261 For undirected multigraphs, this method counts the total number
1262 of edges in the graph::
1264 >>> G = nx.MultiGraph()
1265 >>> G.add_edges_from([(0, 1), (0, 1), (1, 2)])
1266 [0, 1, 0]
1267 >>> G.number_of_edges()
1268 3
1270 If you specify two nodes, this counts the total number of edges
1271 joining the two nodes::
1273 >>> G.number_of_edges(0, 1)
1274 2
1276 For directed multigraphs, this method can count the total number
1277 of directed edges from `u` to `v`::
1279 >>> G = nx.MultiDiGraph()
1280 >>> G.add_edges_from([(0, 1), (0, 1), (1, 0)])
1281 [0, 1, 0]
1282 >>> G.number_of_edges(0, 1)
1283 2
1284 >>> G.number_of_edges(1, 0)
1285 1
1287 """
1288 if u is None:
1289 return self.size()
1290 try:
1291 edgedata = self._adj[u][v]
1292 except KeyError:
1293 return 0 # no such edge
1294 return len(edgedata)