Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/minors/contraction.py: 18%
91 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Provides functions for computing minors of a graph."""
2from itertools import chain, combinations, permutations, product
4import networkx as nx
5from networkx import density
6from networkx.exception import NetworkXException
7from networkx.utils import arbitrary_element
9__all__ = [
10 "contracted_edge",
11 "contracted_nodes",
12 "equivalence_classes",
13 "identified_nodes",
14 "quotient_graph",
15]
17chaini = chain.from_iterable
20def equivalence_classes(iterable, relation):
21 """Returns equivalence classes of `relation` when applied to `iterable`.
23 The equivalence classes, or blocks, consist of objects from `iterable`
24 which are all equivalent. They are defined to be equivalent if the
25 `relation` function returns `True` when passed any two objects from that
26 class, and `False` otherwise. To define an equivalence relation the
27 function must be reflexive, symmetric and transitive.
29 Parameters
30 ----------
31 iterable : list, tuple, or set
32 An iterable of elements/nodes.
34 relation : function
35 A Boolean-valued function that implements an equivalence relation
36 (reflexive, symmetric, transitive binary relation) on the elements
37 of `iterable` - it must take two elements and return `True` if
38 they are related, or `False` if not.
40 Returns
41 -------
42 set of frozensets
43 A set of frozensets representing the partition induced by the equivalence
44 relation function `relation` on the elements of `iterable`. Each
45 member set in the return set represents an equivalence class, or
46 block, of the partition.
48 Duplicate elements will be ignored so it makes the most sense for
49 `iterable` to be a :class:`set`.
51 Notes
52 -----
53 This function does not check that `relation` represents an equivalence
54 relation. You can check that your equivalence classes provide a partition
55 using `is_partition`.
57 Examples
58 --------
59 Let `X` be the set of integers from `0` to `9`, and consider an equivalence
60 relation `R` on `X` of congruence modulo `3`: this means that two integers
61 `x` and `y` in `X` are equivalent under `R` if they leave the same
62 remainder when divided by `3`, i.e. `(x - y) mod 3 = 0`.
64 The equivalence classes of this relation are `{0, 3, 6, 9}`, `{1, 4, 7}`,
65 `{2, 5, 8}`: `0`, `3`, `6`, `9` are all divisible by `3` and leave zero
66 remainder; `1`, `4`, `7` leave remainder `1`; while `2`, `5` and `8` leave
67 remainder `2`. We can see this by calling `equivalence_classes` with
68 `X` and a function implementation of `R`.
70 >>> X = set(range(10))
71 >>> def mod3(x, y): return (x - y) % 3 == 0
72 >>> equivalence_classes(X, mod3) # doctest: +SKIP
73 {frozenset({1, 4, 7}), frozenset({8, 2, 5}), frozenset({0, 9, 3, 6})}
74 """
75 # For simplicity of implementation, we initialize the return value as a
76 # list of lists, then convert it to a set of sets at the end of the
77 # function.
78 blocks = []
79 # Determine the equivalence class for each element of the iterable.
80 for y in iterable:
81 # Each element y must be in *exactly one* equivalence class.
82 #
83 # Each block is guaranteed to be non-empty
84 for block in blocks:
85 x = arbitrary_element(block)
86 if relation(x, y):
87 block.append(y)
88 break
89 else:
90 # If the element y is not part of any known equivalence class, it
91 # must be in its own, so we create a new singleton equivalence
92 # class for it.
93 blocks.append([y])
94 return {frozenset(block) for block in blocks}
97@nx._dispatch(edge_attrs="weight")
98def quotient_graph(
99 G,
100 partition,
101 edge_relation=None,
102 node_data=None,
103 edge_data=None,
104 weight="weight",
105 relabel=False,
106 create_using=None,
107):
108 """Returns the quotient graph of `G` under the specified equivalence
109 relation on nodes.
111 Parameters
112 ----------
113 G : NetworkX graph
114 The graph for which to return the quotient graph with the
115 specified node relation.
117 partition : function, or dict or list of lists, tuples or sets
118 If a function, this function must represent an equivalence
119 relation on the nodes of `G`. It must take two arguments *u*
120 and *v* and return True exactly when *u* and *v* are in the
121 same equivalence class. The equivalence classes form the nodes
122 in the returned graph.
124 If a dict of lists/tuples/sets, the keys can be any meaningful
125 block labels, but the values must be the block lists/tuples/sets
126 (one list/tuple/set per block), and the blocks must form a valid
127 partition of the nodes of the graph. That is, each node must be
128 in exactly one block of the partition.
130 If a list of sets, the list must form a valid partition of
131 the nodes of the graph. That is, each node must be in exactly
132 one block of the partition.
134 edge_relation : Boolean function with two arguments
135 This function must represent an edge relation on the *blocks* of
136 the `partition` of `G`. It must take two arguments, *B* and *C*,
137 each one a set of nodes, and return True exactly when there should be
138 an edge joining block *B* to block *C* in the returned graph.
140 If `edge_relation` is not specified, it is assumed to be the
141 following relation. Block *B* is related to block *C* if and
142 only if some node in *B* is adjacent to some node in *C*,
143 according to the edge set of `G`.
145 node_data : function
146 This function takes one argument, *B*, a set of nodes in `G`,
147 and must return a dictionary representing the node data
148 attributes to set on the node representing *B* in the quotient graph.
149 If None, the following node attributes will be set:
151 * 'graph', the subgraph of the graph `G` that this block
152 represents,
153 * 'nnodes', the number of nodes in this block,
154 * 'nedges', the number of edges within this block,
155 * 'density', the density of the subgraph of `G` that this
156 block represents.
158 edge_data : function
159 This function takes two arguments, *B* and *C*, each one a set
160 of nodes, and must return a dictionary representing the edge
161 data attributes to set on the edge joining *B* and *C*, should
162 there be an edge joining *B* and *C* in the quotient graph (if
163 no such edge occurs in the quotient graph as determined by
164 `edge_relation`, then the output of this function is ignored).
166 If the quotient graph would be a multigraph, this function is
167 not applied, since the edge data from each edge in the graph
168 `G` appears in the edges of the quotient graph.
170 weight : string or None, optional (default="weight")
171 The name of an edge attribute that holds the numerical value
172 used as a weight. If None then each edge has weight 1.
174 relabel : bool
175 If True, relabel the nodes of the quotient graph to be
176 nonnegative integers. Otherwise, the nodes are identified with
177 :class:`frozenset` instances representing the blocks given in
178 `partition`.
180 create_using : NetworkX graph constructor, optional (default=nx.Graph)
181 Graph type to create. If graph instance, then cleared before populated.
183 Returns
184 -------
185 NetworkX graph
186 The quotient graph of `G` under the equivalence relation
187 specified by `partition`. If the partition were given as a
188 list of :class:`set` instances and `relabel` is False,
189 each node will be a :class:`frozenset` corresponding to the same
190 :class:`set`.
192 Raises
193 ------
194 NetworkXException
195 If the given partition is not a valid partition of the nodes of
196 `G`.
198 Examples
199 --------
200 The quotient graph of the complete bipartite graph under the "same
201 neighbors" equivalence relation is `K_2`. Under this relation, two nodes
202 are equivalent if they are not adjacent but have the same neighbor set.
204 >>> G = nx.complete_bipartite_graph(2, 3)
205 >>> same_neighbors = lambda u, v: (
206 ... u not in G[v] and v not in G[u] and G[u] == G[v]
207 ... )
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._dispatch(preserve_all_attrs=True)
429def contracted_nodes(G, u, v, self_loops=True, copy=True):
430 """Returns the graph that results from contracting `u` and `v`.
432 Node contraction identifies the two nodes as a single node incident to any
433 edge that was incident to the original two nodes.
435 Parameters
436 ----------
437 G : NetworkX graph
438 The graph whose nodes will be contracted.
440 u, v : nodes
441 Must be nodes in `G`.
443 self_loops : Boolean
444 If this is True, any edges joining `u` and `v` in `G` become
445 self-loops on the new node in the returned graph.
447 copy : Boolean
448 If this is True (default True), make a copy of
449 `G` and return that instead of directly changing `G`.
452 Returns
453 -------
454 Networkx graph
455 If Copy is True,
456 A new graph object of the same type as `G` (leaving `G` unmodified)
457 with `u` and `v` identified in a single node. The right node `v`
458 will be merged into the node `u`, so only `u` will appear in the
459 returned graph.
460 If copy is False,
461 Modifies `G` with `u` and `v` identified in a single node.
462 The right node `v` will be merged into the node `u`, so
463 only `u` will appear in the returned graph.
465 Notes
466 -----
467 For multigraphs, the edge keys for the realigned edges may
468 not be the same as the edge keys for the old edges. This is
469 natural because edge keys are unique only within each pair of nodes.
471 For non-multigraphs where `u` and `v` are adjacent to a third node
472 `w`, the edge (`v`, `w`) will be contracted into the edge (`u`,
473 `w`) with its attributes stored into a "contraction" attribute.
475 This function is also available as `identified_nodes`.
477 Examples
478 --------
479 Contracting two nonadjacent nodes of the cycle graph on four nodes `C_4`
480 yields the path graph (ignoring parallel edges):
482 >>> G = nx.cycle_graph(4)
483 >>> M = nx.contracted_nodes(G, 1, 3)
484 >>> P3 = nx.path_graph(3)
485 >>> nx.is_isomorphic(M, P3)
486 True
488 >>> G = nx.MultiGraph(P3)
489 >>> M = nx.contracted_nodes(G, 0, 2)
490 >>> M.edges
491 MultiEdgeView([(0, 1, 0), (0, 1, 1)])
493 >>> G = nx.Graph([(1, 2), (2, 2)])
494 >>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)
495 >>> list(H.nodes())
496 [1]
497 >>> list(H.edges())
498 [(1, 1)]
500 In a ``MultiDiGraph`` with a self loop, the in and out edges will
501 be treated separately as edges, so while contracting a node which
502 has a self loop the contraction will add multiple edges:
504 >>> G = nx.MultiDiGraph([(1, 2), (2, 2)])
505 >>> H = nx.contracted_nodes(G, 1, 2)
506 >>> list(H.edges()) # edge 1->2, 2->2, 2<-2 from the original Graph G
507 [(1, 1), (1, 1), (1, 1)]
508 >>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)
509 >>> list(H.edges()) # edge 2->2, 2<-2 from the original Graph G
510 [(1, 1), (1, 1)]
512 See Also
513 --------
514 contracted_edge
515 quotient_graph
517 """
518 # Copying has significant overhead and can be disabled if needed
519 if copy:
520 H = G.copy()
521 else:
522 H = G
524 # edge code uses G.edges(v) instead of G.adj[v] to handle multiedges
525 if H.is_directed():
526 edges_to_remap = chain(G.in_edges(v, data=True), G.out_edges(v, data=True))
527 else:
528 edges_to_remap = G.edges(v, data=True)
530 # If the H=G, the generators change as H changes
531 # This makes the edges_to_remap independent of H
532 if not copy:
533 edges_to_remap = list(edges_to_remap)
535 v_data = H.nodes[v]
536 H.remove_node(v)
538 for prev_w, prev_x, d in edges_to_remap:
539 w = prev_w if prev_w != v else u
540 x = prev_x if prev_x != v else u
542 if ({prev_w, prev_x} == {u, v}) and not self_loops:
543 continue
545 if not H.has_edge(w, x) or G.is_multigraph():
546 H.add_edge(w, x, **d)
547 else:
548 if "contraction" in H.edges[(w, x)]:
549 H.edges[(w, x)]["contraction"][(prev_w, prev_x)] = d
550 else:
551 H.edges[(w, x)]["contraction"] = {(prev_w, prev_x): d}
553 if "contraction" in H.nodes[u]:
554 H.nodes[u]["contraction"][v] = v_data
555 else:
556 H.nodes[u]["contraction"] = {v: v_data}
557 return H
560identified_nodes = contracted_nodes
563@nx._dispatch(preserve_edge_attrs=True)
564def contracted_edge(G, edge, self_loops=True, copy=True):
565 """Returns the graph that results from contracting the specified edge.
567 Edge contraction identifies the two endpoints of the edge as a single node
568 incident to any edge that was incident to the original two nodes. A graph
569 that results from edge contraction is called a *minor* of the original
570 graph.
572 Parameters
573 ----------
574 G : NetworkX graph
575 The graph whose edge will be contracted.
577 edge : tuple
578 Must be a pair of nodes in `G`.
580 self_loops : Boolean
581 If this is True, any edges (including `edge`) joining the
582 endpoints of `edge` in `G` become self-loops on the new node in the
583 returned graph.
585 copy : Boolean (default True)
586 If this is True, a the contraction will be performed on a copy of `G`,
587 otherwise the contraction will happen in place.
589 Returns
590 -------
591 Networkx graph
592 A new graph object of the same type as `G` (leaving `G` unmodified)
593 with endpoints of `edge` identified in a single node. The right node
594 of `edge` will be merged into the left one, so only the left one will
595 appear in the returned graph.
597 Raises
598 ------
599 ValueError
600 If `edge` is not an edge in `G`.
602 Examples
603 --------
604 Attempting to contract two nonadjacent nodes yields an error:
606 >>> G = nx.cycle_graph(4)
607 >>> nx.contracted_edge(G, (1, 3))
608 Traceback (most recent call last):
609 ...
610 ValueError: Edge (1, 3) does not exist in graph G; cannot contract it
612 Contracting two adjacent nodes in the cycle graph on *n* nodes yields the
613 cycle graph on *n - 1* nodes:
615 >>> C5 = nx.cycle_graph(5)
616 >>> C4 = nx.cycle_graph(4)
617 >>> M = nx.contracted_edge(C5, (0, 1), self_loops=False)
618 >>> nx.is_isomorphic(M, C4)
619 True
621 See also
622 --------
623 contracted_nodes
624 quotient_graph
626 """
627 u, v = edge[:2]
628 if not G.has_edge(u, v):
629 raise ValueError(f"Edge {edge} does not exist in graph G; cannot contract it")
630 return contracted_nodes(G, u, v, self_loops=self_loops, copy=copy)