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"""Provides functions for computing minors of a graph."""
3from itertools import chain, combinations, permutations, product
5import networkx as nx
6from networkx import density
7from networkx.exception import NetworkXException
8from networkx.utils import arbitrary_element
10__all__ = [
11 "contracted_edge",
12 "contracted_nodes",
13 "equivalence_classes",
14 "identified_nodes",
15 "quotient_graph",
16]
18chaini = chain.from_iterable
21def equivalence_classes(iterable, relation):
22 """Returns equivalence classes of `relation` when applied to `iterable`.
24 The equivalence classes, or blocks, consist of objects from `iterable`
25 which are all equivalent. They are defined to be equivalent if the
26 `relation` function returns `True` when passed any two objects from that
27 class, and `False` otherwise. To define an equivalence relation the
28 function must be reflexive, symmetric and transitive.
30 Parameters
31 ----------
32 iterable : list, tuple, or set
33 An iterable of elements/nodes.
35 relation : function
36 A Boolean-valued function that implements an equivalence relation
37 (reflexive, symmetric, transitive binary relation) on the elements
38 of `iterable` - it must take two elements and return `True` if
39 they are related, or `False` if not.
41 Returns
42 -------
43 set of frozensets
44 A set of frozensets representing the partition induced by the equivalence
45 relation function `relation` on the elements of `iterable`. Each
46 member set in the return set represents an equivalence class, or
47 block, of the partition.
49 Duplicate elements will be ignored so it makes the most sense for
50 `iterable` to be a :class:`set`.
52 Notes
53 -----
54 This function does not check that `relation` represents an equivalence
55 relation. You can check that your equivalence classes provide a partition
56 using `is_partition`.
58 Examples
59 --------
60 Let `X` be the set of integers from `0` to `9`, and consider an equivalence
61 relation `R` on `X` of congruence modulo `3`: this means that two integers
62 `x` and `y` in `X` are equivalent under `R` if they leave the same
63 remainder when divided by `3`, i.e. `(x - y) mod 3 = 0`.
65 The equivalence classes of this relation are `{0, 3, 6, 9}`, `{1, 4, 7}`,
66 `{2, 5, 8}`: `0`, `3`, `6`, `9` are all divisible by `3` and leave zero
67 remainder; `1`, `4`, `7` leave remainder `1`; while `2`, `5` and `8` leave
68 remainder `2`. We can see this by calling `equivalence_classes` with
69 `X` and a function implementation of `R`.
71 >>> X = set(range(10))
72 >>> def mod3(x, y):
73 ... return (x - y) % 3 == 0
74 >>> equivalence_classes(X, mod3) # doctest: +SKIP
75 {frozenset({1, 4, 7}), frozenset({8, 2, 5}), frozenset({0, 9, 3, 6})}
76 """
77 # For simplicity of implementation, we initialize the return value as a
78 # list of lists, then convert it to a set of sets at the end of the
79 # function.
80 blocks = []
81 # Determine the equivalence class for each element of the iterable.
82 for y in iterable:
83 # Each element y must be in *exactly one* equivalence class.
84 #
85 # Each block is guaranteed to be non-empty
86 for block in blocks:
87 x = arbitrary_element(block)
88 if relation(x, y):
89 block.append(y)
90 break
91 else:
92 # If the element y is not part of any known equivalence class, it
93 # must be in its own, so we create a new singleton equivalence
94 # class for it.
95 blocks.append([y])
96 return {frozenset(block) for block in blocks}
99@nx._dispatchable(edge_attrs="weight", returns_graph=True)
100def quotient_graph(
101 G,
102 partition,
103 edge_relation=None,
104 node_data=None,
105 edge_data=None,
106 weight="weight",
107 relabel=False,
108 create_using=None,
109):
110 """Returns the quotient graph of `G` under the specified equivalence
111 relation on nodes.
113 Parameters
114 ----------
115 G : NetworkX graph
116 The graph for which to return the quotient graph with the
117 specified node relation.
119 partition : function, or dict or list of lists, tuples or sets
120 If a function, this function must represent an equivalence
121 relation on the nodes of `G`. It must take two arguments *u*
122 and *v* and return True exactly when *u* and *v* are in the
123 same equivalence class. The equivalence classes form the nodes
124 in the returned graph.
126 If a dict of lists/tuples/sets, the keys can be any meaningful
127 block labels, but the values must be the block lists/tuples/sets
128 (one list/tuple/set per block), and the blocks must form a valid
129 partition of the nodes of the graph. That is, each node must be
130 in exactly one block of the partition.
132 If a list of sets, the list must form a valid partition of
133 the nodes of the graph. That is, each node must be in exactly
134 one block of the partition.
136 edge_relation : Boolean function with two arguments
137 This function must represent an edge relation on the *blocks* of
138 the `partition` of `G`. It must take two arguments, *B* and *C*,
139 each one a set of nodes, and return True exactly when there should be
140 an edge joining block *B* to block *C* in the returned graph.
142 If `edge_relation` is not specified, it is assumed to be the
143 following relation. Block *B* is related to block *C* if and
144 only if some node in *B* is adjacent to some node in *C*,
145 according to the edge set of `G`.
147 node_data : function
148 This function takes one argument, *B*, a set of nodes in `G`,
149 and must return a dictionary representing the node data
150 attributes to set on the node representing *B* in the quotient graph.
151 If None, the following node attributes will be set:
153 * 'graph', the subgraph of the graph `G` that this block
154 represents,
155 * 'nnodes', the number of nodes in this block,
156 * 'nedges', the number of edges within this block,
157 * 'density', the density of the subgraph of `G` that this
158 block represents.
160 edge_data : function
161 This function takes two arguments, *B* and *C*, each one a set
162 of nodes, and must return a dictionary representing the edge
163 data attributes to set on the edge joining *B* and *C*, should
164 there be an edge joining *B* and *C* in the quotient graph (if
165 no such edge occurs in the quotient graph as determined by
166 `edge_relation`, then the output of this function is ignored).
168 If the quotient graph would be a multigraph, this function is
169 not applied, since the edge data from each edge in the graph
170 `G` appears in the edges of the quotient graph.
172 weight : string or None, optional (default="weight")
173 The name of an edge attribute that holds the numerical value
174 used as a weight. If None then each edge has weight 1.
176 relabel : bool
177 If True, relabel the nodes of the quotient graph to be
178 nonnegative integers. Otherwise, the nodes are identified with
179 :class:`frozenset` instances representing the blocks given in
180 `partition`.
182 create_using : NetworkX graph constructor, optional (default=nx.Graph)
183 Graph type to create. If graph instance, then cleared before populated.
185 Returns
186 -------
187 NetworkX graph
188 The quotient graph of `G` under the equivalence relation
189 specified by `partition`. If the partition were given as a
190 list of :class:`set` instances and `relabel` is False,
191 each node will be a :class:`frozenset` corresponding to the same
192 :class:`set`.
194 Raises
195 ------
196 NetworkXException
197 If the given partition is not a valid partition of the nodes of
198 `G`.
200 Examples
201 --------
202 The quotient graph of the complete bipartite graph under the "same
203 neighbors" equivalence relation is `K_2`. Under this relation, two nodes
204 are equivalent if they are not adjacent but have the same neighbor set.
206 >>> G = nx.complete_bipartite_graph(2, 3)
207 >>> same_neighbors = lambda u, v: (u not in G[v] and v not in G[u] and G[u] == G[v])
208 >>> Q = nx.quotient_graph(G, same_neighbors)
209 >>> K2 = nx.complete_graph(2)
210 >>> nx.is_isomorphic(Q, K2)
211 True
213 The quotient graph of a directed graph under the "same strongly connected
214 component" equivalence relation is the condensation of the graph (see
215 :func:`condensation`). This example comes from the Wikipedia article
216 *`Strongly connected component`_*.
218 >>> G = nx.DiGraph()
219 >>> edges = [
220 ... "ab",
221 ... "be",
222 ... "bf",
223 ... "bc",
224 ... "cg",
225 ... "cd",
226 ... "dc",
227 ... "dh",
228 ... "ea",
229 ... "ef",
230 ... "fg",
231 ... "gf",
232 ... "hd",
233 ... "hf",
234 ... ]
235 >>> G.add_edges_from(tuple(x) for x in edges)
236 >>> components = list(nx.strongly_connected_components(G))
237 >>> sorted(sorted(component) for component in components)
238 [['a', 'b', 'e'], ['c', 'd', 'h'], ['f', 'g']]
239 >>>
240 >>> C = nx.condensation(G, components)
241 >>> component_of = C.graph["mapping"]
242 >>> same_component = lambda u, v: component_of[u] == component_of[v]
243 >>> Q = nx.quotient_graph(G, same_component)
244 >>> nx.is_isomorphic(C, Q)
245 True
247 Node identification can be represented as the quotient of a graph under the
248 equivalence relation that places the two nodes in one block and each other
249 node in its own singleton block.
251 >>> K24 = nx.complete_bipartite_graph(2, 4)
252 >>> K34 = nx.complete_bipartite_graph(3, 4)
253 >>> C = nx.contracted_nodes(K34, 1, 2)
254 >>> nodes = {1, 2}
255 >>> is_contracted = lambda u, v: u in nodes and v in nodes
256 >>> Q = nx.quotient_graph(K34, is_contracted)
257 >>> nx.is_isomorphic(Q, C)
258 True
259 >>> nx.is_isomorphic(Q, K24)
260 True
262 The blockmodeling technique described in [1]_ can be implemented as a
263 quotient graph.
265 >>> G = nx.path_graph(6)
266 >>> partition = [{0, 1}, {2, 3}, {4, 5}]
267 >>> M = nx.quotient_graph(G, partition, relabel=True)
268 >>> list(M.edges())
269 [(0, 1), (1, 2)]
271 Here is the sample example but using partition as a dict of block sets.
273 >>> G = nx.path_graph(6)
274 >>> partition = {0: {0, 1}, 2: {2, 3}, 4: {4, 5}}
275 >>> M = nx.quotient_graph(G, partition, relabel=True)
276 >>> list(M.edges())
277 [(0, 1), (1, 2)]
279 Partitions can be represented in various ways:
281 0. a list/tuple/set of block lists/tuples/sets
282 1. a dict with block labels as keys and blocks lists/tuples/sets as values
283 2. a dict with block lists/tuples/sets as keys and block labels as values
284 3. a function from nodes in the original iterable to block labels
285 4. an equivalence relation function on the target iterable
287 As `quotient_graph` is designed to accept partitions represented as (0), (1) or
288 (4) only, the `equivalence_classes` function can be used to get the partitions
289 in the right form, in order to call `quotient_graph`.
291 .. _Strongly connected component: https://en.wikipedia.org/wiki/Strongly_connected_component
293 References
294 ----------
295 .. [1] Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj.
296 *Generalized Blockmodeling*.
297 Cambridge University Press, 2004.
299 """
300 # If the user provided an equivalence relation as a function to compute
301 # the blocks of the partition on the nodes of G induced by the
302 # equivalence relation.
303 if callable(partition):
304 # equivalence_classes always return partition of whole G.
305 partition = equivalence_classes(G, partition)
306 if not nx.community.is_partition(G, partition):
307 raise nx.NetworkXException(
308 "Input `partition` is not an equivalence relation for nodes of G"
309 )
310 return _quotient_graph(
311 G,
312 partition,
313 edge_relation,
314 node_data,
315 edge_data,
316 weight,
317 relabel,
318 create_using,
319 )
321 # If the partition is a dict, it is assumed to be one where the keys are
322 # user-defined block labels, and values are block lists, tuples or sets.
323 if isinstance(partition, dict):
324 partition = list(partition.values())
326 # If the user provided partition as a collection of sets. Then we
327 # need to check if partition covers all of G nodes. If the answer
328 # is 'No' then we need to prepare suitable subgraph view.
329 partition_nodes = set().union(*partition)
330 if len(partition_nodes) != len(G):
331 G = G.subgraph(partition_nodes)
332 # Each node in the graph/subgraph must be in exactly one block.
333 if not nx.community.is_partition(G, partition):
334 raise NetworkXException("each node must be in exactly one part of `partition`")
335 return _quotient_graph(
336 G,
337 partition,
338 edge_relation,
339 node_data,
340 edge_data,
341 weight,
342 relabel,
343 create_using,
344 )
347def _quotient_graph(
348 G, partition, edge_relation, node_data, edge_data, weight, relabel, create_using
349):
350 """Construct the quotient graph assuming input has been checked"""
351 if create_using is None:
352 H = G.__class__()
353 else:
354 H = nx.empty_graph(0, create_using)
355 # By default set some basic information about the subgraph that each block
356 # represents on the nodes in the quotient graph.
357 if node_data is None:
359 def node_data(b):
360 S = G.subgraph(b)
361 return {
362 "graph": S,
363 "nnodes": len(S),
364 "nedges": S.number_of_edges(),
365 "density": density(S),
366 }
368 # Each block of the partition becomes a node in the quotient graph.
369 partition = [frozenset(b) for b in partition]
370 H.add_nodes_from((b, node_data(b)) for b in partition)
371 # By default, the edge relation is the relation defined as follows. B is
372 # adjacent to C if a node in B is adjacent to a node in C, according to the
373 # edge set of G.
374 #
375 # This is not a particularly efficient implementation of this relation:
376 # there are O(n^2) pairs to check and each check may require O(log n) time
377 # (to check set membership). This can certainly be parallelized.
378 if edge_relation is None:
380 def edge_relation(b, c):
381 return any(v in G[u] for u, v in product(b, c))
383 # By default, sum the weights of the edges joining pairs of nodes across
384 # blocks to get the weight of the edge joining those two blocks.
385 if edge_data is None:
387 def edge_data(b, c):
388 edgedata = (
389 d
390 for u, v, d in G.edges(b | c, data=True)
391 if (u in b and v in c) or (u in c and v in b)
392 )
393 return {"weight": sum(d.get(weight, 1) for d in edgedata)}
395 block_pairs = permutations(H, 2) if H.is_directed() else combinations(H, 2)
396 # In a multigraph, add one edge in the quotient graph for each edge
397 # in the original graph.
398 if H.is_multigraph():
399 edges = chaini(
400 (
401 (b, c, G.get_edge_data(u, v, default={}))
402 for u, v in product(b, c)
403 if v in G[u]
404 )
405 for b, c in block_pairs
406 if edge_relation(b, c)
407 )
408 # In a simple graph, apply the edge data function to each pair of
409 # blocks to determine the edge data attributes to apply to each edge
410 # in the quotient graph.
411 else:
412 edges = (
413 (b, c, edge_data(b, c)) for (b, c) in block_pairs if edge_relation(b, c)
414 )
415 H.add_edges_from(edges)
416 # If requested by the user, relabel the nodes to be integers,
417 # numbered in increasing order from zero in the same order as the
418 # iteration order of `partition`.
419 if relabel:
420 # Can't use nx.convert_node_labels_to_integers() here since we
421 # want the order of iteration to be the same for backward
422 # compatibility with the nx.blockmodel() function.
423 labels = {b: i for i, b in enumerate(partition)}
424 H = nx.relabel_nodes(H, labels)
425 return H
428@nx._dispatchable(
429 preserve_all_attrs=True, mutates_input={"not copy": 4}, returns_graph=True
430)
431def contracted_nodes(
432 G, u, v, self_loops=True, copy=True, *, store_contraction_as="contraction"
433):
434 """Returns the graph that results from contracting `u` and `v`.
436 Node contraction identifies the two nodes as a single node incident to any
437 edge that was incident to the original two nodes.
438 Information about the contracted nodes and any modified edges are stored on
439 the output graph in a ``"contraction"`` attribute - see Examples for details.
441 Parameters
442 ----------
443 G : NetworkX graph
444 The graph whose nodes will be contracted.
446 u, v : nodes
447 Must be nodes in `G`.
449 self_loops : Boolean
450 If this is True, any edges joining `u` and `v` in `G` become
451 self-loops on the new node in the returned graph.
453 copy : Boolean
454 If this is True (the default), make a copy of
455 `G` and return that instead of directly changing `G`.
457 store_contraction_as : str or None, default="contraction"
458 Name of the node/edge attribute where information about the contraction
459 should be stored. By default information about the contracted node and
460 any contracted edges is stored in a ``"contraction"`` attribute on the
461 resulting node and edge. If `None`, information about the contracted
462 nodes/edges and their data are not stored.
464 Returns
465 -------
466 Networkx graph
467 If `copy` is True,
468 A new graph object of the same type as `G` (leaving `G` unmodified)
469 with `u` and `v` identified in a single node. The right node `v`
470 will be merged into the node `u`, so only `u` will appear in the
471 returned graph.
472 If `copy` is False,
473 Modifies `G` with `u` and `v` identified in a single node.
474 The right node `v` will be merged into the node `u`, so
475 only `u` will appear in the returned graph.
477 Notes
478 -----
479 For multigraphs, the edge keys for the realigned edges may
480 not be the same as the edge keys for the old edges. This is
481 natural because edge keys are unique only within each pair of nodes.
483 This function is also available as `identified_nodes`.
485 Examples
486 --------
487 Contracting two nonadjacent nodes of the cycle graph on four nodes `C_4`
488 yields the path graph (ignoring parallel edges):
490 >>> G = nx.cycle_graph(4)
491 >>> M = nx.contracted_nodes(G, 1, 3)
492 >>> P3 = nx.path_graph(3)
493 >>> nx.is_isomorphic(M, P3)
494 True
496 Information about the contracted nodes is stored on the resulting graph in
497 a ``"contraction"`` attribute. For instance, the contracted node is stored
498 as an attribute on ``u``:
500 >>> H = nx.contracted_nodes(P3, 0, 2)
501 >>> H.nodes(data=True)
502 NodeDataView({0: {'contraction': {2: {}}}, 1: {}})
504 Any node attributes on the contracted node are also preserved:
506 >>> nx.set_node_attributes(P3, dict(enumerate("rgb")), name="color")
507 >>> P3.nodes(data=True)
508 NodeDataView({0: {'color': 'r'}, 1: {'color': 'g'}, 2: {'color': 'b'}})
509 >>> H = nx.contracted_nodes(P3, 0, 2)
510 >>> H.nodes[0]
511 {'color': 'r', 'contraction': {2: {'color': 'b'}}}
513 Edges are handled similarly: when ``u`` and ``v`` are adjacent to a third node
514 ``w``, the edge ``(v, w)`` will be contracted into the edge ``(u, w)`` with
515 its attributes stored into a ``"contraction"`` attribute on edge ``(u, w)``:
517 >>> nx.set_edge_attributes(P3, {(0, 1): 10, (1, 2): 100}, name="weight")
518 >>> P3.edges(data=True)
519 EdgeDataView([(0, 1, {'weight': 10}), (1, 2, {'weight': 100})])
520 >>> H = nx.contracted_nodes(P3, 0, 2)
521 >>> H.edges(data=True)
522 EdgeDataView([(0, 1, {'weight': 10, 'contraction': {(2, 1): {'weight': 100}}})])
524 Attributes from contracted nodes/edges can be combined with those of the
525 nodes/edges onto which they were contracted:
527 >>> # Concatenate colors of contracted nodes
528 >>> for u, cdict in H.nodes(data="contraction"):
529 ... if cdict is not None:
530 ... H.nodes[u]["color"] += "".join(n["color"] for n in cdict.values())
531 ... del H.nodes[u]["contraction"] # Remove contraction attr (optional)
532 >>> H.nodes(data=True)
533 NodeDataView({0: {'color': 'rb'}, 1: {'color': 'g'}})
534 >>> # Sum contracted edge weights
535 >>> for u, v, cdict in H.edges(data="contraction"):
536 ... if cdict is not None:
537 ... H[u][v]["weight"] += sum(n["weight"] for n in cdict.values())
538 ... del H.edges[(u, v)]["contraction"] # Remove contraction attr (optional)
539 >>> H.edges(data=True)
540 EdgeDataView([(0, 1, {'weight': 110})])
542 If `G` is a multigraph, then a new edge is added instead. Any edge attributes
543 are still preserved:
545 >>> MG = nx.MultiGraph(P3)
546 >>> MH = nx.contracted_nodes(MG, 0, 2)
547 >>> MH.edges(keys=True, data=True)
548 MultiEdgeDataView([(0, 1, 0, {'weight': 10}), (0, 1, 1, {'weight': 100})])
550 If ``selfloops=True`` (the default), any edges adjoining `u` and `v` become
551 self-loops on ``u`` in the resulting graph:
553 >>> G = nx.Graph([(1, 2)])
554 >>> H = nx.contracted_nodes(G, 1, 2)
555 >>> H.nodes, H.edges
556 (NodeView((1,)), EdgeView([(1, 1)]))
557 >>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)
558 >>> H.nodes, H.edges
559 (NodeView((1,)), EdgeView([]))
561 Note however that any self loops in the original graph `G` are preserved:
563 >>> G = nx.Graph([(1, 2), (2, 2)])
564 >>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)
565 >>> H.nodes, H.edges
566 (NodeView((1,)), EdgeView([(1, 1)]))
568 The same reasoning applies to MultiGraphs:
570 >>> MG = nx.MultiGraph([(1, 2), (2, 2)])
571 >>> # Edge (1, 1, 0) in MH corresponds to edge (2, 2) in MG
572 >>> MH = nx.contracted_nodes(MG, 1, 2, self_loops=False)
573 >>> MH.edges(keys=True)
574 MultiEdgeView([(1, 1, 0)])
575 >>> # MH has two (1, 1) edges - one from edge (2, 2) in MG, and one
576 >>> # resulting from the contraction of 2->1
577 >>> MH = nx.contracted_nodes(MG, 1, 2, self_loops=True)
578 >>> MH.edges(keys=True)
579 MultiEdgeView([(1, 1, 0), (1, 1, 1)])
582 In a ``MultiDiGraph`` with a self loop, the in and out edges will
583 be treated separately as edges, so while contracting a node which
584 has a self loop the contraction will add multiple edges:
586 >>> G = nx.MultiDiGraph([(1, 2), (2, 2)])
587 >>> H = nx.contracted_nodes(G, 1, 2)
588 >>> list(H.edges()) # edge 1->2, 2->2, 2<-2 from the original Graph G
589 [(1, 1), (1, 1), (1, 1)]
590 >>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)
591 >>> list(H.edges()) # edge 2->2, 2<-2 from the original Graph G
592 [(1, 1), (1, 1)]
594 See Also
595 --------
596 contracted_edge
597 quotient_graph
599 """
600 # Copying has significant overhead and can be disabled if needed
601 H = G.copy() if copy else G
603 # edge code uses G.edges(v) instead of G.adj[v] to handle multiedges
604 if H.is_directed():
605 edges_to_remap = chain(G.in_edges(v, data=True), G.out_edges(v, data=True))
606 else:
607 edges_to_remap = G.edges(v, data=True)
609 # If the H=G, the generators change as H changes
610 # This makes the edges_to_remap independent of H
611 if not copy:
612 edges_to_remap = list(edges_to_remap)
614 v_data = H.nodes[v]
615 H.remove_node(v)
617 # A bit of input munging to extract whether contraction info should be
618 # stored, and if so bind to a shorter name
619 if _store_contraction := (store_contraction_as is not None):
620 contraction = store_contraction_as
622 for prev_w, prev_x, d in edges_to_remap:
623 w = prev_w if prev_w != v else u
624 x = prev_x if prev_x != v else u
626 if ({prev_w, prev_x} == {u, v}) and not self_loops:
627 continue
629 if not H.has_edge(w, x) or G.is_multigraph():
630 H.add_edge(w, x, **d)
631 continue
633 # Store information about the contracted edge iff `store_contraction` is not None
634 if _store_contraction:
635 if contraction in H.edges[(w, x)]:
636 H.edges[(w, x)][contraction][(prev_w, prev_x)] = d
637 else:
638 H.edges[(w, x)][contraction] = {(prev_w, prev_x): d}
640 # Store information about the contracted node iff `store_contraction`
641 if _store_contraction:
642 if contraction in H.nodes[u]:
643 H.nodes[u][contraction][v] = v_data
644 else:
645 H.nodes[u][contraction] = {v: v_data}
647 return H
650identified_nodes = contracted_nodes
653@nx._dispatchable(
654 preserve_all_attrs=True, mutates_input={"not copy": 3}, returns_graph=True
655)
656def contracted_edge(
657 G, edge, self_loops=True, copy=True, *, store_contraction_as="contraction"
658):
659 """Returns the graph that results from contracting the specified edge.
661 Edge contraction identifies the two endpoints of the edge as a single node
662 incident to any edge that was incident to the original two nodes. A graph
663 that results from edge contraction is called a *minor* of the original
664 graph.
666 Parameters
667 ----------
668 G : NetworkX graph
669 The graph whose edge will be contracted.
671 edge : tuple
672 Must be a pair of nodes in `G`.
674 self_loops : Boolean
675 If this is True, any edges (including `edge`) joining the
676 endpoints of `edge` in `G` become self-loops on the new node in the
677 returned graph.
679 copy : Boolean (default True)
680 If this is True, a the contraction will be performed on a copy of `G`,
681 otherwise the contraction will happen in place.
683 store_contraction_as : str or None, default="contraction"
684 Name of the node/edge attribute where information about the contraction
685 should be stored. By default information about the contracted node and
686 any contracted edges is stored in a ``"contraction"`` attribute on the
687 resulting node and edge. If `None`, information about the contracted
688 nodes/edges and their data are not stored.
690 Returns
691 -------
692 Networkx graph
693 A new graph object of the same type as `G` (leaving `G` unmodified)
694 with endpoints of `edge` identified in a single node. The right node
695 of `edge` will be merged into the left one, so only the left one will
696 appear in the returned graph.
698 Raises
699 ------
700 ValueError
701 If `edge` is not an edge in `G`.
703 Examples
704 --------
705 Attempting to contract two nonadjacent nodes yields an error:
707 >>> G = nx.cycle_graph(4)
708 >>> nx.contracted_edge(G, (1, 3))
709 Traceback (most recent call last):
710 ...
711 ValueError: Edge (1, 3) does not exist in graph G; cannot contract it
713 Contracting two adjacent nodes in the cycle graph on *n* nodes yields the
714 cycle graph on *n - 1* nodes:
716 >>> C5 = nx.cycle_graph(5)
717 >>> C4 = nx.cycle_graph(4)
718 >>> M = nx.contracted_edge(C5, (0, 1), self_loops=False)
719 >>> nx.is_isomorphic(M, C4)
720 True
722 See also
723 --------
724 contracted_nodes
725 quotient_graph
727 """
728 u, v = edge[:2]
729 if not G.has_edge(u, v):
730 raise ValueError(f"Edge {edge} does not exist in graph G; cannot contract it")
731 return contracted_nodes(
732 G,
733 u,
734 v,
735 self_loops=self_loops,
736 copy=copy,
737 store_contraction_as=store_contraction_as,
738 )