Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/minors.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Provides functions for computing minors of a graph.""" | |
2 from itertools import chain | |
3 from itertools import combinations | |
4 from itertools import permutations | |
5 from itertools import product | |
6 | |
7 import networkx as nx | |
8 from networkx import density | |
9 from networkx.exception import NetworkXException | |
10 from networkx.utils import arbitrary_element | |
11 | |
12 __all__ = ["contracted_edge", "contracted_nodes", "identified_nodes", "quotient_graph"] | |
13 | |
14 chaini = chain.from_iterable | |
15 | |
16 | |
17 def equivalence_classes(iterable, relation): | |
18 """Returns the set of equivalence classes of the given `iterable` under | |
19 the specified equivalence relation. | |
20 | |
21 `relation` must be a Boolean-valued function that takes two argument. It | |
22 must represent an equivalence relation (that is, the relation induced by | |
23 the function must be reflexive, symmetric, and transitive). | |
24 | |
25 The return value is a set of sets. It is a partition of the elements of | |
26 `iterable`; duplicate elements will be ignored so it makes the most sense | |
27 for `iterable` to be a :class:`set`. | |
28 | |
29 """ | |
30 # For simplicity of implementation, we initialize the return value as a | |
31 # list of lists, then convert it to a set of sets at the end of the | |
32 # function. | |
33 blocks = [] | |
34 # Determine the equivalence class for each element of the iterable. | |
35 for y in iterable: | |
36 # Each element y must be in *exactly one* equivalence class. | |
37 # | |
38 # Each block is guaranteed to be non-empty | |
39 for block in blocks: | |
40 x = arbitrary_element(block) | |
41 if relation(x, y): | |
42 block.append(y) | |
43 break | |
44 else: | |
45 # If the element y is not part of any known equivalence class, it | |
46 # must be in its own, so we create a new singleton equivalence | |
47 # class for it. | |
48 blocks.append([y]) | |
49 return {frozenset(block) for block in blocks} | |
50 | |
51 | |
52 def quotient_graph( | |
53 G, | |
54 partition, | |
55 edge_relation=None, | |
56 node_data=None, | |
57 edge_data=None, | |
58 relabel=False, | |
59 create_using=None, | |
60 ): | |
61 """Returns the quotient graph of `G` under the specified equivalence | |
62 relation on nodes. | |
63 | |
64 Parameters | |
65 ---------- | |
66 G : NetworkX graph | |
67 The graph for which to return the quotient graph with the | |
68 specified node relation. | |
69 | |
70 partition : function or list of sets | |
71 If a function, this function must represent an equivalence | |
72 relation on the nodes of `G`. It must take two arguments *u* | |
73 and *v* and return True exactly when *u* and *v* are in the | |
74 same equivalence class. The equivalence classes form the nodes | |
75 in the returned graph. | |
76 | |
77 If a list of sets, the list must form a valid partition of | |
78 the nodes of the graph. That is, each node must be in exactly | |
79 one block of the partition. | |
80 | |
81 edge_relation : Boolean function with two arguments | |
82 This function must represent an edge relation on the *blocks* of | |
83 `G` in the partition induced by `node_relation`. It must | |
84 take two arguments, *B* and *C*, each one a set of nodes, and | |
85 return True exactly when there should be an edge joining | |
86 block *B* to block *C* in the returned graph. | |
87 | |
88 If `edge_relation` is not specified, it is assumed to be the | |
89 following relation. Block *B* is related to block *C* if and | |
90 only if some node in *B* is adjacent to some node in *C*, | |
91 according to the edge set of `G`. | |
92 | |
93 edge_data : function | |
94 This function takes two arguments, *B* and *C*, each one a set | |
95 of nodes, and must return a dictionary representing the edge | |
96 data attributes to set on the edge joining *B* and *C*, should | |
97 there be an edge joining *B* and *C* in the quotient graph (if | |
98 no such edge occurs in the quotient graph as determined by | |
99 `edge_relation`, then the output of this function is ignored). | |
100 | |
101 If the quotient graph would be a multigraph, this function is | |
102 not applied, since the edge data from each edge in the graph | |
103 `G` appears in the edges of the quotient graph. | |
104 | |
105 node_data : function | |
106 This function takes one argument, *B*, a set of nodes in `G`, | |
107 and must return a dictionary representing the node data | |
108 attributes to set on the node representing *B* in the quotient graph. | |
109 If None, the following node attributes will be set: | |
110 | |
111 * 'graph', the subgraph of the graph `G` that this block | |
112 represents, | |
113 * 'nnodes', the number of nodes in this block, | |
114 * 'nedges', the number of edges within this block, | |
115 * 'density', the density of the subgraph of `G` that this | |
116 block represents. | |
117 | |
118 relabel : bool | |
119 If True, relabel the nodes of the quotient graph to be | |
120 nonnegative integers. Otherwise, the nodes are identified with | |
121 :class:`frozenset` instances representing the blocks given in | |
122 `partition`. | |
123 | |
124 create_using : NetworkX graph constructor, optional (default=nx.Graph) | |
125 Graph type to create. If graph instance, then cleared before populated. | |
126 | |
127 Returns | |
128 ------- | |
129 NetworkX graph | |
130 The quotient graph of `G` under the equivalence relation | |
131 specified by `partition`. If the partition were given as a | |
132 list of :class:`set` instances and `relabel` is False, | |
133 each node will be a :class:`frozenset` corresponding to the same | |
134 :class:`set`. | |
135 | |
136 Raises | |
137 ------ | |
138 NetworkXException | |
139 If the given partition is not a valid partition of the nodes of | |
140 `G`. | |
141 | |
142 Examples | |
143 -------- | |
144 The quotient graph of the complete bipartite graph under the "same | |
145 neighbors" equivalence relation is `K_2`. Under this relation, two nodes | |
146 are equivalent if they are not adjacent but have the same neighbor set:: | |
147 | |
148 >>> G = nx.complete_bipartite_graph(2, 3) | |
149 >>> same_neighbors = lambda u, v: ( | |
150 ... u not in G[v] and v not in G[u] and G[u] == G[v] | |
151 ... ) | |
152 >>> Q = nx.quotient_graph(G, same_neighbors) | |
153 >>> K2 = nx.complete_graph(2) | |
154 >>> nx.is_isomorphic(Q, K2) | |
155 True | |
156 | |
157 The quotient graph of a directed graph under the "same strongly connected | |
158 component" equivalence relation is the condensation of the graph (see | |
159 :func:`condensation`). This example comes from the Wikipedia article | |
160 *`Strongly connected component`_*:: | |
161 | |
162 >>> G = nx.DiGraph() | |
163 >>> edges = [ | |
164 ... "ab", | |
165 ... "be", | |
166 ... "bf", | |
167 ... "bc", | |
168 ... "cg", | |
169 ... "cd", | |
170 ... "dc", | |
171 ... "dh", | |
172 ... "ea", | |
173 ... "ef", | |
174 ... "fg", | |
175 ... "gf", | |
176 ... "hd", | |
177 ... "hf", | |
178 ... ] | |
179 >>> G.add_edges_from(tuple(x) for x in edges) | |
180 >>> components = list(nx.strongly_connected_components(G)) | |
181 >>> sorted(sorted(component) for component in components) | |
182 [['a', 'b', 'e'], ['c', 'd', 'h'], ['f', 'g']] | |
183 >>> | |
184 >>> C = nx.condensation(G, components) | |
185 >>> component_of = C.graph["mapping"] | |
186 >>> same_component = lambda u, v: component_of[u] == component_of[v] | |
187 >>> Q = nx.quotient_graph(G, same_component) | |
188 >>> nx.is_isomorphic(C, Q) | |
189 True | |
190 | |
191 Node identification can be represented as the quotient of a graph under the | |
192 equivalence relation that places the two nodes in one block and each other | |
193 node in its own singleton block:: | |
194 | |
195 >>> K24 = nx.complete_bipartite_graph(2, 4) | |
196 >>> K34 = nx.complete_bipartite_graph(3, 4) | |
197 >>> C = nx.contracted_nodes(K34, 1, 2) | |
198 >>> nodes = {1, 2} | |
199 >>> is_contracted = lambda u, v: u in nodes and v in nodes | |
200 >>> Q = nx.quotient_graph(K34, is_contracted) | |
201 >>> nx.is_isomorphic(Q, C) | |
202 True | |
203 >>> nx.is_isomorphic(Q, K24) | |
204 True | |
205 | |
206 The blockmodeling technique described in [1]_ can be implemented as a | |
207 quotient graph:: | |
208 | |
209 >>> G = nx.path_graph(6) | |
210 >>> partition = [{0, 1}, {2, 3}, {4, 5}] | |
211 >>> M = nx.quotient_graph(G, partition, relabel=True) | |
212 >>> list(M.edges()) | |
213 [(0, 1), (1, 2)] | |
214 | |
215 .. _Strongly connected component: https://en.wikipedia.org/wiki/Strongly_connected_component | |
216 | |
217 References | |
218 ---------- | |
219 .. [1] Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj. | |
220 *Generalized Blockmodeling*. | |
221 Cambridge University Press, 2004. | |
222 | |
223 """ | |
224 # If the user provided an equivalence relation as a function compute | |
225 # the blocks of the partition on the nodes of G induced by the | |
226 # equivalence relation. | |
227 if callable(partition): | |
228 # equivalence_classes always return partition of whole G. | |
229 partition = equivalence_classes(G, partition) | |
230 return _quotient_graph( | |
231 G, partition, edge_relation, node_data, edge_data, relabel, create_using | |
232 ) | |
233 | |
234 # If the user provided partition as a collection of sets. Then we | |
235 # need to check if partition covers all of G nodes. If the answer | |
236 # is 'No' then we need to prepare suitable subgraph view. | |
237 partition_nodes = set().union(*partition) | |
238 if len(partition_nodes) != len(G): | |
239 G = G.subgraph(partition_nodes) | |
240 return _quotient_graph( | |
241 G, partition, edge_relation, node_data, edge_data, relabel, create_using | |
242 ) | |
243 | |
244 | |
245 def _quotient_graph( | |
246 G, | |
247 partition, | |
248 edge_relation=None, | |
249 node_data=None, | |
250 edge_data=None, | |
251 relabel=False, | |
252 create_using=None, | |
253 ): | |
254 # Each node in the graph must be in exactly one block. | |
255 if any(sum(1 for b in partition if v in b) != 1 for v in G): | |
256 raise NetworkXException("each node must be in exactly one block") | |
257 if create_using is None: | |
258 H = G.__class__() | |
259 else: | |
260 H = nx.empty_graph(0, create_using) | |
261 # By default set some basic information about the subgraph that each block | |
262 # represents on the nodes in the quotient graph. | |
263 if node_data is None: | |
264 | |
265 def node_data(b): | |
266 S = G.subgraph(b) | |
267 return dict( | |
268 graph=S, nnodes=len(S), nedges=S.number_of_edges(), density=density(S) | |
269 ) | |
270 | |
271 # Each block of the partition becomes a node in the quotient graph. | |
272 partition = [frozenset(b) for b in partition] | |
273 H.add_nodes_from((b, node_data(b)) for b in partition) | |
274 # By default, the edge relation is the relation defined as follows. B is | |
275 # adjacent to C if a node in B is adjacent to a node in C, according to the | |
276 # edge set of G. | |
277 # | |
278 # This is not a particularly efficient implementation of this relation: | |
279 # there are O(n^2) pairs to check and each check may require O(log n) time | |
280 # (to check set membership). This can certainly be parallelized. | |
281 if edge_relation is None: | |
282 | |
283 def edge_relation(b, c): | |
284 return any(v in G[u] for u, v in product(b, c)) | |
285 | |
286 # By default, sum the weights of the edges joining pairs of nodes across | |
287 # blocks to get the weight of the edge joining those two blocks. | |
288 if edge_data is None: | |
289 | |
290 def edge_data(b, c): | |
291 edgedata = ( | |
292 d | |
293 for u, v, d in G.edges(b | c, data=True) | |
294 if (u in b and v in c) or (u in c and v in b) | |
295 ) | |
296 return {"weight": sum(d.get("weight", 1) for d in edgedata)} | |
297 | |
298 block_pairs = permutations(H, 2) if H.is_directed() else combinations(H, 2) | |
299 # In a multigraph, add one edge in the quotient graph for each edge | |
300 # in the original graph. | |
301 if H.is_multigraph(): | |
302 edges = chaini( | |
303 ( | |
304 (b, c, G.get_edge_data(u, v, default={})) | |
305 for u, v in product(b, c) | |
306 if v in G[u] | |
307 ) | |
308 for b, c in block_pairs | |
309 if edge_relation(b, c) | |
310 ) | |
311 # In a simple graph, apply the edge data function to each pair of | |
312 # blocks to determine the edge data attributes to apply to each edge | |
313 # in the quotient graph. | |
314 else: | |
315 edges = ( | |
316 (b, c, edge_data(b, c)) for (b, c) in block_pairs if edge_relation(b, c) | |
317 ) | |
318 H.add_edges_from(edges) | |
319 # If requested by the user, relabel the nodes to be integers, | |
320 # numbered in increasing order from zero in the same order as the | |
321 # iteration order of `partition`. | |
322 if relabel: | |
323 # Can't use nx.convert_node_labels_to_integers() here since we | |
324 # want the order of iteration to be the same for backward | |
325 # compatibility with the nx.blockmodel() function. | |
326 labels = {b: i for i, b in enumerate(partition)} | |
327 H = nx.relabel_nodes(H, labels) | |
328 return H | |
329 | |
330 | |
331 def contracted_nodes(G, u, v, self_loops=True, copy=True): | |
332 """Returns the graph that results from contracting `u` and `v`. | |
333 | |
334 Node contraction identifies the two nodes as a single node incident to any | |
335 edge that was incident to the original two nodes. | |
336 | |
337 Parameters | |
338 ---------- | |
339 G : NetworkX graph | |
340 The graph whose nodes will be contracted. | |
341 | |
342 u, v : nodes | |
343 Must be nodes in `G`. | |
344 | |
345 self_loops : Boolean | |
346 If this is True, any edges joining `u` and `v` in `G` become | |
347 self-loops on the new node in the returned graph. | |
348 | |
349 copy : Boolean | |
350 If this is True (default True), make a copy of | |
351 `G` and return that instead of directly changing `G`. | |
352 | |
353 Returns | |
354 ------- | |
355 Networkx graph | |
356 If Copy is True: | |
357 A new graph object of the same type as `G` (leaving `G` unmodified) | |
358 with `u` and `v` identified in a single node. The right node `v` | |
359 will be merged into the node `u`, so only `u` will appear in the | |
360 returned graph. | |
361 if Copy is False: | |
362 Modifies `G` with `u` and `v` identified in a single node. | |
363 The right node `v` will be merged into the node `u`, so | |
364 only `u` will appear in the returned graph. | |
365 | |
366 Notes | |
367 ----- | |
368 For multigraphs, the edge keys for the realigned edges may | |
369 not be the same as the edge keys for the old edges. This is | |
370 natural because edge keys are unique only within each pair of nodes. | |
371 | |
372 Examples | |
373 -------- | |
374 Contracting two nonadjacent nodes of the cycle graph on four nodes `C_4` | |
375 yields the path graph (ignoring parallel edges):: | |
376 | |
377 >>> G = nx.cycle_graph(4) | |
378 >>> M = nx.contracted_nodes(G, 1, 3) | |
379 >>> P3 = nx.path_graph(3) | |
380 >>> nx.is_isomorphic(M, P3) | |
381 True | |
382 | |
383 >>> G = nx.MultiGraph(P3) | |
384 >>> M = nx.contracted_nodes(G, 0, 2) | |
385 >>> M.edges | |
386 MultiEdgeView([(0, 1, 0), (0, 1, 1)]) | |
387 | |
388 >>> G = nx.Graph([(1, 2), (2, 2)]) | |
389 >>> H = nx.contracted_nodes(G, 1, 2, self_loops=False) | |
390 >>> list(H.nodes()) | |
391 [1] | |
392 >>> list(H.edges()) | |
393 [(1, 1)] | |
394 | |
395 See also | |
396 -------- | |
397 contracted_edge | |
398 quotient_graph | |
399 | |
400 Notes | |
401 ----- | |
402 This function is also available as `identified_nodes`. | |
403 """ | |
404 # Copying has significant overhead and can be disabled if needed | |
405 if copy: | |
406 H = G.copy() | |
407 else: | |
408 H = G | |
409 | |
410 # edge code uses G.edges(v) instead of G.adj[v] to handle multiedges | |
411 if H.is_directed(): | |
412 in_edges = ( | |
413 (w if w != v else u, u, d) | |
414 for w, x, d in G.in_edges(v, data=True) | |
415 if self_loops or w != u | |
416 ) | |
417 out_edges = ( | |
418 (u, w if w != v else u, d) | |
419 for x, w, d in G.out_edges(v, data=True) | |
420 if self_loops or w != u | |
421 ) | |
422 new_edges = chain(in_edges, out_edges) | |
423 else: | |
424 new_edges = ( | |
425 (u, w if w != v else u, d) | |
426 for x, w, d in G.edges(v, data=True) | |
427 if self_loops or w != u | |
428 ) | |
429 | |
430 # If the H=G, the generators change as H changes | |
431 # This makes the new_edges independent of H | |
432 if not copy: | |
433 new_edges = list(new_edges) | |
434 | |
435 v_data = H.nodes[v] | |
436 H.remove_node(v) | |
437 H.add_edges_from(new_edges) | |
438 | |
439 if "contraction" in H.nodes[u]: | |
440 H.nodes[u]["contraction"][v] = v_data | |
441 else: | |
442 H.nodes[u]["contraction"] = {v: v_data} | |
443 return H | |
444 | |
445 | |
446 identified_nodes = contracted_nodes | |
447 | |
448 | |
449 def contracted_edge(G, edge, self_loops=True): | |
450 """Returns the graph that results from contracting the specified edge. | |
451 | |
452 Edge contraction identifies the two endpoints of the edge as a single node | |
453 incident to any edge that was incident to the original two nodes. A graph | |
454 that results from edge contraction is called a *minor* of the original | |
455 graph. | |
456 | |
457 Parameters | |
458 ---------- | |
459 G : NetworkX graph | |
460 The graph whose edge will be contracted. | |
461 | |
462 edge : tuple | |
463 Must be a pair of nodes in `G`. | |
464 | |
465 self_loops : Boolean | |
466 If this is True, any edges (including `edge`) joining the | |
467 endpoints of `edge` in `G` become self-loops on the new node in the | |
468 returned graph. | |
469 | |
470 Returns | |
471 ------- | |
472 Networkx graph | |
473 A new graph object of the same type as `G` (leaving `G` unmodified) | |
474 with endpoints of `edge` identified in a single node. The right node | |
475 of `edge` will be merged into the left one, so only the left one will | |
476 appear in the returned graph. | |
477 | |
478 Raises | |
479 ------ | |
480 ValueError | |
481 If `edge` is not an edge in `G`. | |
482 | |
483 Examples | |
484 -------- | |
485 Attempting to contract two nonadjacent nodes yields an error:: | |
486 | |
487 >>> G = nx.cycle_graph(4) | |
488 >>> nx.contracted_edge(G, (1, 3)) | |
489 Traceback (most recent call last): | |
490 ... | |
491 ValueError: Edge (1, 3) does not exist in graph G; cannot contract it | |
492 | |
493 Contracting two adjacent nodes in the cycle graph on *n* nodes yields the | |
494 cycle graph on *n - 1* nodes:: | |
495 | |
496 >>> C5 = nx.cycle_graph(5) | |
497 >>> C4 = nx.cycle_graph(4) | |
498 >>> M = nx.contracted_edge(C5, (0, 1), self_loops=False) | |
499 >>> nx.is_isomorphic(M, C4) | |
500 True | |
501 | |
502 See also | |
503 -------- | |
504 contracted_nodes | |
505 quotient_graph | |
506 | |
507 """ | |
508 if not G.has_edge(*edge): | |
509 raise ValueError(f"Edge {edge} does not exist in graph G; cannot contract it") | |
510 return contracted_nodes(G, *edge, self_loops=self_loops) |