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 MultiDiGraph."""
3from copy import deepcopy
4from functools import cached_property
6import networkx as nx
7from networkx import convert
8from networkx.classes.coreviews import MultiAdjacencyView
9from networkx.classes.digraph import DiGraph
10from networkx.classes.multigraph import MultiGraph
11from networkx.classes.reportviews import (
12 DiMultiDegreeView,
13 InMultiDegreeView,
14 InMultiEdgeView,
15 OutMultiDegreeView,
16 OutMultiEdgeView,
17)
18from networkx.exception import NetworkXError
20__all__ = ["MultiDiGraph"]
23class MultiDiGraph(MultiGraph, DiGraph):
24 """A directed graph class that can store multiedges.
26 Multiedges are multiple edges between two nodes. Each edge
27 can hold optional data or attributes.
29 A MultiDiGraph holds directed edges. Self loops are allowed.
31 Nodes can be arbitrary (hashable) Python objects with optional
32 key/value attributes. By convention `None` is not used as a node.
34 Edges are represented as links between nodes with optional
35 key/value attributes.
37 Parameters
38 ----------
39 incoming_graph_data : input graph (optional, default: None)
40 Data to initialize graph. If None (default) an empty
41 graph is created. The data can be any format that is supported
42 by the to_networkx_graph() function, currently including edge list,
43 dict of dicts, dict of lists, NetworkX graph, 2D NumPy array, SciPy
44 sparse matrix, or PyGraphviz graph.
46 multigraph_input : bool or None (default None)
47 Note: Only used when `incoming_graph_data` is a dict.
48 If True, `incoming_graph_data` is assumed to be a
49 dict-of-dict-of-dict-of-dict structure keyed by
50 node to neighbor to edge keys to edge data for multi-edges.
51 A NetworkXError is raised if this is not the case.
52 If False, :func:`to_networkx_graph` is used to try to determine
53 the dict's graph data structure as either a dict-of-dict-of-dict
54 keyed by node to neighbor to edge data, or a dict-of-iterable
55 keyed by node to neighbors.
56 If None, the treatment for True is tried, but if it fails,
57 the treatment for False is tried.
59 attr : keyword arguments, optional (default= no attributes)
60 Attributes to add to graph as key=value pairs.
62 See Also
63 --------
64 Graph
65 DiGraph
66 MultiGraph
68 Examples
69 --------
70 Create an empty graph structure (a "null graph") with no nodes and
71 no edges.
73 >>> G = nx.MultiDiGraph()
75 G can be grown in several ways.
77 **Nodes:**
79 Add one node at a time:
81 >>> G.add_node(1)
83 Add the nodes from any container (a list, dict, set or
84 even the lines from a file or the nodes from another graph).
86 >>> G.add_nodes_from([2, 3])
87 >>> G.add_nodes_from(range(100, 110))
88 >>> H = nx.path_graph(10)
89 >>> G.add_nodes_from(H)
91 In addition to strings and integers any hashable Python object
92 (except None) can represent a node, e.g. a customized node object,
93 or even another Graph.
95 >>> G.add_node(H)
97 **Edges:**
99 G can also be grown by adding edges.
101 Add one edge,
103 >>> key = G.add_edge(1, 2)
105 a list of edges,
107 >>> keys = G.add_edges_from([(1, 2), (1, 3)])
109 or a collection of edges,
111 >>> keys = G.add_edges_from(H.edges)
113 If some edges connect nodes not yet in the graph, the nodes
114 are added automatically. If an edge already exists, an additional
115 edge is created and stored using a key to identify the edge.
116 By default the key is the lowest unused integer.
118 >>> keys = G.add_edges_from([(4, 5, dict(route=282)), (4, 5, dict(route=37))])
119 >>> G[4]
120 AdjacencyView({5: {0: {}, 1: {'route': 282}, 2: {'route': 37}}})
122 **Attributes:**
124 Each graph, node, and edge can hold key/value attribute pairs
125 in an associated attribute dictionary (the keys must be hashable).
126 By default these are empty, but can be added or changed using
127 add_edge, add_node or direct manipulation of the attribute
128 dictionaries named graph, node and edge respectively.
130 >>> G = nx.MultiDiGraph(day="Friday")
131 >>> G.graph
132 {'day': 'Friday'}
134 Add node attributes using add_node(), add_nodes_from() or G.nodes
136 >>> G.add_node(1, time="5pm")
137 >>> G.add_nodes_from([3], time="2pm")
138 >>> G.nodes[1]
139 {'time': '5pm'}
140 >>> G.nodes[1]["room"] = 714
141 >>> del G.nodes[1]["room"] # remove attribute
142 >>> list(G.nodes(data=True))
143 [(1, {'time': '5pm'}), (3, {'time': '2pm'})]
145 Add edge attributes using add_edge(), add_edges_from(), subscript
146 notation, or G.edges.
148 >>> key = G.add_edge(1, 2, weight=4.7)
149 >>> keys = G.add_edges_from([(3, 4), (4, 5)], color="red")
150 >>> keys = G.add_edges_from([(1, 2, {"color": "blue"}), (2, 3, {"weight": 8})])
151 >>> G[1][2][0]["weight"] = 4.7
152 >>> G.edges[1, 2, 0]["weight"] = 4
154 Warning: we protect the graph data structure by making `G.edges[1,
155 2, 0]` a read-only dict-like structure. However, you can assign to
156 attributes in e.g. `G.edges[1, 2, 0]`. Thus, use 2 sets of brackets
157 to add/change data attributes: `G.edges[1, 2, 0]['weight'] = 4`
158 (for multigraphs the edge key is required: `MG.edges[u, v,
159 key][name] = value`).
161 **Shortcuts:**
163 Many common graph features allow python syntax to speed reporting.
165 >>> 1 in G # check if node in graph
166 True
167 >>> [n for n in G if n < 3] # iterate through nodes
168 [1, 2]
169 >>> len(G) # number of nodes in graph
170 5
171 >>> G[1] # adjacency dict-like view mapping neighbor -> edge key -> edge attributes
172 AdjacencyView({2: {0: {'weight': 4}, 1: {'color': 'blue'}}})
174 Often the best way to traverse all edges of a graph is via the neighbors.
175 The neighbors are available as an adjacency-view `G.adj` object or via
176 the method `G.adjacency()`.
178 >>> for n, nbrsdict in G.adjacency():
179 ... for nbr, keydict in nbrsdict.items():
180 ... for key, eattr in keydict.items():
181 ... if "weight" in eattr:
182 ... # Do something useful with the edges
183 ... pass
185 But the edges() method is often more convenient:
187 >>> for u, v, keys, weight in G.edges(data="weight", keys=True):
188 ... if weight is not None:
189 ... # Do something useful with the edges
190 ... pass
192 **Reporting:**
194 Simple graph information is obtained using methods and object-attributes.
195 Reporting usually provides views instead of containers to reduce memory
196 usage. The views update as the graph is updated similarly to dict-views.
197 The objects `nodes`, `edges` and `adj` provide access to data attributes
198 via lookup (e.g. `nodes[n]`, `edges[u, v, k]`, `adj[u][v]`) and iteration
199 (e.g. `nodes.items()`, `nodes.data('color')`,
200 `nodes.data('color', default='blue')` and similarly for `edges`)
201 Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`.
203 For details on these and other miscellaneous methods, see below.
205 **Subclasses (Advanced):**
207 The MultiDiGraph class uses a dict-of-dict-of-dict-of-dict structure.
208 The outer dict (node_dict) holds adjacency information keyed by node.
209 The next dict (adjlist_dict) represents the adjacency information
210 and holds edge_key dicts keyed by neighbor. The edge_key dict holds
211 each edge_attr dict keyed by edge key. The inner dict
212 (edge_attr_dict) represents the edge data and holds edge attribute
213 values keyed by attribute names.
215 Each of these four dicts in the dict-of-dict-of-dict-of-dict
216 structure can be replaced by a user defined dict-like object.
217 In general, the dict-like features should be maintained but
218 extra features can be added. To replace one of the dicts create
219 a new graph class by changing the class(!) variable holding the
220 factory for that dict-like structure. The variable names are
221 node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory,
222 adjlist_outer_dict_factory, edge_key_dict_factory, edge_attr_dict_factory
223 and graph_attr_dict_factory.
225 node_dict_factory : function, (default: dict)
226 Factory function to be used to create the dict containing node
227 attributes, keyed by node id.
228 It should require no arguments and return a dict-like object
230 node_attr_dict_factory: function, (default: dict)
231 Factory function to be used to create the node attribute
232 dict which holds attribute values keyed by attribute name.
233 It should require no arguments and return a dict-like object
235 adjlist_outer_dict_factory : function, (default: dict)
236 Factory function to be used to create the outer-most dict
237 in the data structure that holds adjacency info keyed by node.
238 It should require no arguments and return a dict-like object.
240 adjlist_inner_dict_factory : function, (default: dict)
241 Factory function to be used to create the adjacency list
242 dict which holds multiedge key dicts keyed by neighbor.
243 It should require no arguments and return a dict-like object.
245 edge_key_dict_factory : function, (default: dict)
246 Factory function to be used to create the edge key dict
247 which holds edge data keyed by edge key.
248 It should require no arguments and return a dict-like object.
250 edge_attr_dict_factory : function, (default: dict)
251 Factory function to be used to create the edge attribute
252 dict which holds attribute values keyed by attribute name.
253 It should require no arguments and return a dict-like object.
255 graph_attr_dict_factory : function, (default: dict)
256 Factory function to be used to create the graph attribute
257 dict which holds attribute values keyed by attribute name.
258 It should require no arguments and return a dict-like object.
260 Typically, if your extension doesn't impact the data structure all
261 methods will inherited without issue except: `to_directed/to_undirected`.
262 By default these methods create a DiGraph/Graph class and you probably
263 want them to create your extension of a DiGraph/Graph. To facilitate
264 this we define two class variables that you can set in your subclass.
266 to_directed_class : callable, (default: DiGraph or MultiDiGraph)
267 Class to create a new graph structure in the `to_directed` method.
268 If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used.
270 to_undirected_class : callable, (default: Graph or MultiGraph)
271 Class to create a new graph structure in the `to_undirected` method.
272 If `None`, a NetworkX class (Graph or MultiGraph) is used.
274 **Subclassing Example**
276 Create a low memory graph class that effectively disallows edge
277 attributes by using a single attribute dict for all edges.
278 This reduces the memory used, but you lose edge attributes.
280 >>> class ThinGraph(nx.Graph):
281 ... all_edge_dict = {"weight": 1}
282 ...
283 ... def single_edge_dict(self):
284 ... return self.all_edge_dict
285 ...
286 ... edge_attr_dict_factory = single_edge_dict
287 >>> G = ThinGraph()
288 >>> G.add_edge(2, 1)
289 >>> G[2][1]
290 {'weight': 1}
291 >>> G.add_edge(2, 2)
292 >>> G[2][1] is G[2][2]
293 True
294 """
296 # node_dict_factory = dict # already assigned in Graph
297 # adjlist_outer_dict_factory = dict
298 # adjlist_inner_dict_factory = dict
299 edge_key_dict_factory = dict
300 # edge_attr_dict_factory = dict
302 # This __new__ method just does what Python itself does automatically.
303 # We include it here as part of the dispatchable/backend interface.
304 # If your goal is to understand how the graph classes work, you can ignore
305 # this method, even when subclassing the base classes. If you are subclassing
306 # in order to provide a backend that allows class instantiation, this method
307 # can be overridden to return your own backend graph class.
308 @nx._dispatchable(name="multidigraph__new__", graphs=None, returns_graph=True)
309 def __new__(cls, incoming_graph_data=None, multigraph_input=None, **attr):
310 return object.__new__(cls)
312 def __init__(self, incoming_graph_data=None, multigraph_input=None, **attr):
313 """Initialize a graph with edges, name, or graph attributes.
315 Parameters
316 ----------
317 incoming_graph_data : input graph
318 Data to initialize graph. If incoming_graph_data=None (default)
319 an empty graph is created. The data can be an edge list, or any
320 NetworkX graph object. If the corresponding optional Python
321 packages are installed the data can also be a 2D NumPy array, a
322 SciPy sparse array, or a PyGraphviz graph.
324 multigraph_input : bool or None (default None)
325 Note: Only used when `incoming_graph_data` is a dict.
326 If True, `incoming_graph_data` is assumed to be a
327 dict-of-dict-of-dict-of-dict structure keyed by
328 node to neighbor to edge keys to edge data for multi-edges.
329 A NetworkXError is raised if this is not the case.
330 If False, :func:`to_networkx_graph` is used to try to determine
331 the dict's graph data structure as either a dict-of-dict-of-dict
332 keyed by node to neighbor to edge data, or a dict-of-iterable
333 keyed by node to neighbors.
334 If None, the treatment for True is tried, but if it fails,
335 the treatment for False is tried.
337 attr : keyword arguments, optional (default= no attributes)
338 Attributes to add to graph as key=value pairs.
340 See Also
341 --------
342 convert
344 Examples
345 --------
346 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
347 >>> G = nx.Graph(name="my graph")
348 >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges
349 >>> G = nx.Graph(e)
351 Arbitrary graph attribute pairs (key=value) may be assigned
353 >>> G = nx.Graph(e, day="Friday")
354 >>> G.graph
355 {'day': 'Friday'}
357 """
358 attr.pop("backend", None) # Ignore explicit `backend="networkx"`
359 # multigraph_input can be None/True/False. So check "is not False"
360 if isinstance(incoming_graph_data, dict) and multigraph_input is not False:
361 DiGraph.__init__(self)
362 try:
363 convert.from_dict_of_dicts(
364 incoming_graph_data, create_using=self, multigraph_input=True
365 )
366 self.graph.update(attr)
367 except Exception as err:
368 if multigraph_input is True:
369 raise nx.NetworkXError(
370 f"converting multigraph_input raised:\n{type(err)}: {err}"
371 )
372 DiGraph.__init__(self, incoming_graph_data, **attr)
373 else:
374 DiGraph.__init__(self, incoming_graph_data, **attr)
376 @cached_property
377 def adj(self):
378 """Graph adjacency object holding the neighbors of each node.
380 This object is a read-only dict-like structure with node keys
381 and neighbor-dict values. The neighbor-dict is keyed by neighbor
382 to the edgekey-dict. So `G.adj[3][2][0]['color'] = 'blue'` sets
383 the color of the edge `(3, 2, 0)` to `"blue"`.
385 Iterating over G.adj behaves like a dict. Useful idioms include
386 `for nbr, datadict in G.adj[n].items():`.
388 The neighbor information is also provided by subscripting the graph.
389 So `for nbr, foovalue in G[node].data('foo', default=1):` works.
391 For directed graphs, `G.adj` holds outgoing (successor) info.
392 """
393 return MultiAdjacencyView(self._succ)
395 @cached_property
396 def succ(self):
397 """Graph adjacency object holding the successors of each node.
399 This object is a read-only dict-like structure with node keys
400 and neighbor-dict values. The neighbor-dict is keyed by neighbor
401 to the edgekey-dict. So `G.adj[3][2][0]['color'] = 'blue'` sets
402 the color of the edge `(3, 2, 0)` to `"blue"`.
404 Iterating over G.adj behaves like a dict. Useful idioms include
405 `for nbr, datadict in G.adj[n].items():`.
407 The neighbor information is also provided by subscripting the graph.
408 So `for nbr, foovalue in G[node].data('foo', default=1):` works.
410 For directed graphs, `G.succ` is identical to `G.adj`.
411 """
412 return MultiAdjacencyView(self._succ)
414 @cached_property
415 def pred(self):
416 """Graph adjacency object holding the predecessors of each node.
418 This object is a read-only dict-like structure with node keys
419 and neighbor-dict values. The neighbor-dict is keyed by neighbor
420 to the edgekey-dict. So `G.adj[3][2][0]['color'] = 'blue'` sets
421 the color of the edge `(3, 2, 0)` to `"blue"`.
423 Iterating over G.adj behaves like a dict. Useful idioms include
424 `for nbr, datadict in G.adj[n].items():`.
425 """
426 return MultiAdjacencyView(self._pred)
428 def add_edge(self, u_for_edge, v_for_edge, key=None, **attr):
429 """Add an edge between u and v.
431 The nodes u and v will be automatically added if they are
432 not already in the graph.
434 Edge attributes can be specified with keywords or by directly
435 accessing the edge's attribute dictionary. See examples below.
437 Parameters
438 ----------
439 u_for_edge, v_for_edge : nodes
440 Nodes can be, for example, strings or numbers.
441 Nodes must be hashable (and not None) Python objects.
442 key : hashable identifier, optional (default=lowest unused integer)
443 Used to distinguish multiedges between a pair of nodes.
444 attr : keyword arguments, optional
445 Edge data (or labels or objects) can be assigned using
446 keyword arguments.
448 Returns
449 -------
450 The edge key assigned to the edge.
452 See Also
453 --------
454 add_edges_from : add a collection of edges
456 Notes
457 -----
458 To replace/update edge data, use the optional key argument
459 to identify a unique edge. Otherwise a new edge will be created.
461 NetworkX algorithms designed for weighted graphs cannot use
462 multigraphs directly because it is not clear how to handle
463 multiedge weights. Convert to Graph using edge attribute
464 'weight' to enable weighted graph algorithms.
466 Default keys are generated using the method `new_edge_key()`.
467 This method can be overridden by subclassing the base class and
468 providing a custom `new_edge_key()` method.
470 Examples
471 --------
472 The following all add the edge e=(1, 2) to graph G:
474 >>> G = nx.MultiDiGraph()
475 >>> e = (1, 2)
476 >>> key = G.add_edge(1, 2) # explicit two-node form
477 >>> G.add_edge(*e) # single edge as tuple of two nodes
478 1
479 >>> G.add_edges_from([(1, 2)]) # add edges from iterable container
480 [2]
482 Associate data to edges using keywords:
484 >>> key = G.add_edge(1, 2, weight=3)
485 >>> key = G.add_edge(1, 2, key=0, weight=4) # update data for key=0
486 >>> key = G.add_edge(1, 3, weight=7, capacity=15, length=342.7)
488 For non-string attribute keys, use subscript notation.
490 >>> ekey = G.add_edge(1, 2)
491 >>> G[1][2][0].update({0: 5})
492 >>> G.edges[1, 2, 0].update({0: 5})
493 """
494 u, v = u_for_edge, v_for_edge
495 # add nodes
496 if u not in self._succ:
497 if u is None:
498 raise ValueError("None cannot be a node")
499 self._succ[u] = self.adjlist_inner_dict_factory()
500 self._pred[u] = self.adjlist_inner_dict_factory()
501 self._node[u] = self.node_attr_dict_factory()
502 if v not in self._succ:
503 if v is None:
504 raise ValueError("None cannot be a node")
505 self._succ[v] = self.adjlist_inner_dict_factory()
506 self._pred[v] = self.adjlist_inner_dict_factory()
507 self._node[v] = self.node_attr_dict_factory()
508 if key is None:
509 key = self.new_edge_key(u, v)
510 if v in self._succ[u]:
511 keydict = self._adj[u][v]
512 datadict = keydict.get(key, self.edge_attr_dict_factory())
513 datadict.update(attr)
514 keydict[key] = datadict
515 else:
516 # selfloops work this way without special treatment
517 datadict = self.edge_attr_dict_factory()
518 datadict.update(attr)
519 keydict = self.edge_key_dict_factory()
520 keydict[key] = datadict
521 self._succ[u][v] = keydict
522 self._pred[v][u] = keydict
523 nx._clear_cache(self)
524 return key
526 def remove_edge(self, u, v, key=None):
527 """Remove an edge between u and v.
529 Parameters
530 ----------
531 u, v : nodes
532 Remove an edge between nodes u and v.
533 key : hashable identifier, optional (default=None)
534 Used to distinguish multiple edges between a pair of nodes.
535 If None, remove a single edge between u and v. If there are
536 multiple edges, removes the last edge added in terms of
537 insertion order.
539 Raises
540 ------
541 NetworkXError
542 If there is not an edge between u and v, or
543 if there is no edge with the specified key.
545 See Also
546 --------
547 remove_edges_from : remove a collection of edges
549 Examples
550 --------
551 >>> G = nx.MultiDiGraph()
552 >>> nx.add_path(G, [0, 1, 2, 3])
553 >>> G.remove_edge(0, 1)
554 >>> e = (1, 2)
555 >>> G.remove_edge(*e) # unpacks e from an edge tuple
557 For multiple edges
559 >>> G = nx.MultiDiGraph()
560 >>> G.add_edges_from([(1, 2), (1, 2), (1, 2)]) # key_list returned
561 [0, 1, 2]
563 When ``key=None`` (the default), edges are removed in the opposite
564 order that they were added:
566 >>> G.remove_edge(1, 2)
567 >>> G.edges(keys=True)
568 OutMultiEdgeView([(1, 2, 0), (1, 2, 1)])
570 For edges with keys
572 >>> G = nx.MultiDiGraph()
573 >>> G.add_edge(1, 2, key="first")
574 'first'
575 >>> G.add_edge(1, 2, key="second")
576 'second'
577 >>> G.remove_edge(1, 2, key="first")
578 >>> G.edges(keys=True)
579 OutMultiEdgeView([(1, 2, 'second')])
581 """
582 try:
583 d = self._adj[u][v]
584 except KeyError as err:
585 raise NetworkXError(f"The edge {u}-{v} is not in the graph.") from err
586 # remove the edge with specified data
587 if key is None:
588 d.popitem()
589 else:
590 try:
591 del d[key]
592 except KeyError as err:
593 msg = f"The edge {u}-{v} with key {key} is not in the graph."
594 raise NetworkXError(msg) from err
595 if len(d) == 0:
596 # remove the key entries if last edge
597 del self._succ[u][v]
598 del self._pred[v][u]
599 nx._clear_cache(self)
601 @cached_property
602 def edges(self):
603 """An OutMultiEdgeView of the Graph as G.edges or G.edges().
605 edges(self, nbunch=None, data=False, keys=False, default=None)
607 The OutMultiEdgeView provides set-like operations on the edge-tuples
608 as well as edge attribute lookup. When called, it also provides
609 an EdgeDataView object which allows control of access to edge
610 attributes (but does not provide set-like operations).
611 Hence, ``G.edges[u, v, k]['color']`` provides the value of the color
612 attribute for the edge from ``u`` to ``v`` with key ``k`` while
613 ``for (u, v, k, c) in G.edges(data='color', default='red', keys=True):``
614 iterates through all the edges yielding the color attribute with
615 default `'red'` if no color attribute exists.
617 Edges are returned as tuples with optional data and keys
618 in the order (node, neighbor, key, data). If ``keys=True`` is not
619 provided, the tuples will just be (node, neighbor, data), but
620 multiple tuples with the same node and neighbor will be
621 generated when multiple edges between two nodes exist.
623 Parameters
624 ----------
625 nbunch : single node, container, or all nodes (default= all nodes)
626 The view will only report edges from these nodes.
627 data : string or bool, optional (default=False)
628 The edge attribute returned in 3-tuple (u, v, ddict[data]).
629 If True, return edge attribute dict in 3-tuple (u, v, ddict).
630 If False, return 2-tuple (u, v).
631 keys : bool, optional (default=False)
632 If True, return edge keys with each edge, creating (u, v, k,
633 d) tuples when data is also requested (the default) and (u,
634 v, k) tuples when data is not requested.
635 default : value, optional (default=None)
636 Value used for edges that don't have the requested attribute.
637 Only relevant if data is not True or False.
639 Returns
640 -------
641 edges : OutMultiEdgeView
642 A view of edge attributes, usually it iterates over (u, v)
643 (u, v, k) or (u, v, k, d) tuples of edges, but can also be
644 used for attribute lookup as ``edges[u, v, k]['foo']``.
646 Notes
647 -----
648 Nodes in nbunch that are not in the graph will be (quietly) ignored.
649 For directed graphs this returns the out-edges.
651 Examples
652 --------
653 >>> G = nx.MultiDiGraph()
654 >>> nx.add_path(G, [0, 1, 2])
655 >>> key = G.add_edge(2, 3, weight=5)
656 >>> key2 = G.add_edge(1, 2) # second edge between these nodes
657 >>> [e for e in G.edges()]
658 [(0, 1), (1, 2), (1, 2), (2, 3)]
659 >>> list(G.edges(data=True)) # default data is {} (empty dict)
660 [(0, 1, {}), (1, 2, {}), (1, 2, {}), (2, 3, {'weight': 5})]
661 >>> list(G.edges(data="weight", default=1))
662 [(0, 1, 1), (1, 2, 1), (1, 2, 1), (2, 3, 5)]
663 >>> list(G.edges(keys=True)) # default keys are integers
664 [(0, 1, 0), (1, 2, 0), (1, 2, 1), (2, 3, 0)]
665 >>> list(G.edges(data=True, keys=True))
666 [(0, 1, 0, {}), (1, 2, 0, {}), (1, 2, 1, {}), (2, 3, 0, {'weight': 5})]
667 >>> list(G.edges(data="weight", default=1, keys=True))
668 [(0, 1, 0, 1), (1, 2, 0, 1), (1, 2, 1, 1), (2, 3, 0, 5)]
669 >>> list(G.edges([0, 2]))
670 [(0, 1), (2, 3)]
671 >>> list(G.edges(0))
672 [(0, 1)]
673 >>> list(G.edges(1))
674 [(1, 2), (1, 2)]
676 See Also
677 --------
678 in_edges, out_edges
679 """
680 return OutMultiEdgeView(self)
682 # alias out_edges to edges
683 @cached_property
684 def out_edges(self):
685 return OutMultiEdgeView(self)
687 out_edges.__doc__ = edges.__doc__
689 @cached_property
690 def in_edges(self):
691 """A view of the in edges of the graph as G.in_edges or G.in_edges().
693 in_edges(self, nbunch=None, data=False, keys=False, default=None)
695 Parameters
696 ----------
697 nbunch : single node, container, or all nodes (default= all nodes)
698 The view will only report edges incident to these nodes.
699 data : string or bool, optional (default=False)
700 The edge attribute returned in 3-tuple (u, v, ddict[data]).
701 If True, return edge attribute dict in 3-tuple (u, v, ddict).
702 If False, return 2-tuple (u, v).
703 keys : bool, optional (default=False)
704 If True, return edge keys with each edge, creating 3-tuples
705 (u, v, k) or with data, 4-tuples (u, v, k, d).
706 default : value, optional (default=None)
707 Value used for edges that don't have the requested attribute.
708 Only relevant if data is not True or False.
710 Returns
711 -------
712 in_edges : InMultiEdgeView or InMultiEdgeDataView
713 A view of edge attributes, usually it iterates over (u, v)
714 or (u, v, k) or (u, v, k, d) tuples of edges, but can also be
715 used for attribute lookup as `edges[u, v, k]['foo']`.
717 See Also
718 --------
719 edges
720 """
721 return InMultiEdgeView(self)
723 @cached_property
724 def degree(self):
725 """A DegreeView for the Graph as G.degree or G.degree().
727 The node degree is the number of edges adjacent to the node.
728 The weighted node degree is the sum of the edge weights for
729 edges incident to that node.
731 This object provides an iterator for (node, degree) as well as
732 lookup for the degree for a single node.
734 Parameters
735 ----------
736 nbunch : single node, container, or all nodes (default= all nodes)
737 The view will only report edges incident to these nodes.
739 weight : string or None, optional (default=None)
740 The name of an edge attribute that holds the numerical value used
741 as a weight. If None, then each edge has weight 1.
742 The degree is the sum of the edge weights adjacent to the node.
744 Returns
745 -------
746 DiMultiDegreeView or int
747 If multiple nodes are requested (the default), returns a `DiMultiDegreeView`
748 mapping nodes to their degree.
749 If a single node is requested, returns the degree of the node as an integer.
751 See Also
752 --------
753 out_degree, in_degree
755 Examples
756 --------
757 >>> G = nx.MultiDiGraph()
758 >>> nx.add_path(G, [0, 1, 2, 3])
759 >>> G.degree(0) # node 0 with degree 1
760 1
761 >>> list(G.degree([0, 1, 2]))
762 [(0, 1), (1, 2), (2, 2)]
763 >>> G.add_edge(0, 1) # parallel edge
764 1
765 >>> list(G.degree([0, 1, 2])) # parallel edges are counted
766 [(0, 2), (1, 3), (2, 2)]
768 """
769 return DiMultiDegreeView(self)
771 @cached_property
772 def in_degree(self):
773 """A DegreeView for (node, in_degree) or in_degree for single node.
775 The node in-degree is the number of edges pointing into the node.
776 The weighted node degree is the sum of the edge weights for
777 edges incident to that node.
779 This object provides an iterator for (node, degree) as well as
780 lookup for the degree for a single node.
782 Parameters
783 ----------
784 nbunch : single node, container, or all nodes (default= all nodes)
785 The view will only report edges incident to these nodes.
787 weight : string or None, optional (default=None)
788 The edge attribute that holds the numerical value used
789 as a weight. If None, then each edge has weight 1.
790 The degree is the sum of the edge weights adjacent to the node.
792 Returns
793 -------
794 If a single node is requested
795 deg : int
796 Degree of the node
798 OR if multiple nodes are requested
799 nd_iter : iterator
800 The iterator returns two-tuples of (node, in-degree).
802 See Also
803 --------
804 degree, out_degree
806 Examples
807 --------
808 >>> G = nx.MultiDiGraph()
809 >>> nx.add_path(G, [0, 1, 2, 3])
810 >>> G.in_degree(0) # node 0 with degree 0
811 0
812 >>> list(G.in_degree([0, 1, 2]))
813 [(0, 0), (1, 1), (2, 1)]
814 >>> G.add_edge(0, 1) # parallel edge
815 1
816 >>> list(G.in_degree([0, 1, 2])) # parallel edges counted
817 [(0, 0), (1, 2), (2, 1)]
819 """
820 return InMultiDegreeView(self)
822 @cached_property
823 def out_degree(self):
824 """Returns an iterator for (node, out-degree) or out-degree for single node.
826 out_degree(self, nbunch=None, weight=None)
828 The node out-degree is the number of edges pointing out of the node.
829 This function returns the out-degree for a single node or an iterator
830 for a bunch of nodes or if nothing is passed as argument.
832 Parameters
833 ----------
834 nbunch : single node, container, or all nodes (default= all nodes)
835 The view will only report edges incident to these nodes.
837 weight : string or None, optional (default=None)
838 The edge attribute that holds the numerical value used
839 as a weight. If None, then each edge has weight 1.
840 The degree is the sum of the edge weights.
842 Returns
843 -------
844 If a single node is requested
845 deg : int
846 Degree of the node
848 OR if multiple nodes are requested
849 nd_iter : iterator
850 The iterator returns two-tuples of (node, out-degree).
852 See Also
853 --------
854 degree, in_degree
856 Examples
857 --------
858 >>> G = nx.MultiDiGraph()
859 >>> nx.add_path(G, [0, 1, 2, 3])
860 >>> G.out_degree(0) # node 0 with degree 1
861 1
862 >>> list(G.out_degree([0, 1, 2]))
863 [(0, 1), (1, 1), (2, 1)]
864 >>> G.add_edge(0, 1) # parallel edge
865 1
866 >>> list(G.out_degree([0, 1, 2])) # counts parallel edges
867 [(0, 2), (1, 1), (2, 1)]
869 """
870 return OutMultiDegreeView(self)
872 def is_multigraph(self):
873 """Returns True if graph is a multigraph, False otherwise."""
874 return True
876 def is_directed(self):
877 """Returns True if graph is directed, False otherwise."""
878 return True
880 def to_undirected(self, reciprocal=False, as_view=False):
881 """Returns an undirected representation of the digraph.
883 Parameters
884 ----------
885 reciprocal : bool (optional)
886 If True only keep edges that appear in both directions
887 in the original digraph.
888 as_view : bool (optional, default=False)
889 If True return an undirected view of the original directed graph.
891 Returns
892 -------
893 G : MultiGraph
894 An undirected graph with the same name and nodes and
895 with edge (u, v, data) if either (u, v, data) or (v, u, data)
896 is in the digraph. If both edges exist in digraph and
897 their edge data is different, only one edge is created
898 with an arbitrary choice of which edge data to use.
899 You must check and correct for this manually if desired.
901 See Also
902 --------
903 MultiGraph, copy, add_edge, add_edges_from
905 Notes
906 -----
907 This returns a "deepcopy" of the edge, node, and
908 graph attributes which attempts to completely copy
909 all of the data and references.
911 This is in contrast to the similar D=MultiDiGraph(G) which
912 returns a shallow copy of the data.
914 See the Python copy module for more information on shallow
915 and deep copies, https://docs.python.org/3/library/copy.html.
917 Warning: If you have subclassed MultiDiGraph to use dict-like
918 objects in the data structure, those changes do not transfer
919 to the MultiGraph created by this method.
921 Examples
922 --------
923 >>> G = nx.path_graph(2) # or MultiGraph, etc
924 >>> H = G.to_directed()
925 >>> list(H.edges)
926 [(0, 1), (1, 0)]
927 >>> G2 = H.to_undirected()
928 >>> list(G2.edges)
929 [(0, 1)]
930 """
931 graph_class = self.to_undirected_class()
932 if as_view is True:
933 return nx.graphviews.generic_graph_view(self, graph_class)
934 # deepcopy when not a view
935 G = graph_class()
936 G.graph.update(deepcopy(self.graph))
937 G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
938 if reciprocal is True:
939 G.add_edges_from(
940 (u, v, key, deepcopy(data))
941 for u, nbrs in self._adj.items()
942 for v, keydict in nbrs.items()
943 for key, data in keydict.items()
944 if v in self._pred[u] and key in self._pred[u][v]
945 )
946 else:
947 G.add_edges_from(
948 (u, v, key, deepcopy(data))
949 for u, nbrs in self._adj.items()
950 for v, keydict in nbrs.items()
951 for key, data in keydict.items()
952 )
953 return G
955 def reverse(self, copy=True):
956 """Returns the reverse of the graph.
958 The reverse is a graph with the same nodes and edges
959 but with the directions of the edges reversed.
961 Parameters
962 ----------
963 copy : bool optional (default=True)
964 If True, return a new DiGraph holding the reversed edges.
965 If False, the reverse graph is created using a view of
966 the original graph.
967 """
968 if copy:
969 H = self.__class__()
970 H.graph.update(deepcopy(self.graph))
971 H.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items())
972 H.add_edges_from(
973 (v, u, k, deepcopy(d))
974 for u, v, k, d in self.edges(keys=True, data=True)
975 )
976 return H
977 return nx.reverse_view(self)