Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/operators/binary.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 """ | |
2 Operations on graphs including union, intersection, difference. | |
3 """ | |
4 import networkx as nx | |
5 | |
6 __all__ = [ | |
7 "union", | |
8 "compose", | |
9 "disjoint_union", | |
10 "intersection", | |
11 "difference", | |
12 "symmetric_difference", | |
13 "full_join", | |
14 ] | |
15 | |
16 | |
17 def union(G, H, rename=(None, None), name=None): | |
18 """ Return the union of graphs G and H. | |
19 | |
20 Graphs G and H must be disjoint, otherwise an exception is raised. | |
21 | |
22 Parameters | |
23 ---------- | |
24 G,H : graph | |
25 A NetworkX graph | |
26 | |
27 rename : bool , default=(None, None) | |
28 Node names of G and H can be changed by specifying the tuple | |
29 rename=('G-','H-') (for example). Node "u" in G is then renamed | |
30 "G-u" and "v" in H is renamed "H-v". | |
31 | |
32 name : string | |
33 Specify the name for the union graph | |
34 | |
35 Returns | |
36 ------- | |
37 U : A union graph with the same type as G. | |
38 | |
39 Notes | |
40 ----- | |
41 To force a disjoint union with node relabeling, use | |
42 disjoint_union(G,H) or convert_node_labels_to integers(). | |
43 | |
44 Graph, edge, and node attributes are propagated from G and H | |
45 to the union graph. If a graph attribute is present in both | |
46 G and H the value from H is used. | |
47 | |
48 See Also | |
49 -------- | |
50 disjoint_union | |
51 """ | |
52 if not G.is_multigraph() == H.is_multigraph(): | |
53 raise nx.NetworkXError("G and H must both be graphs or multigraphs.") | |
54 # Union is the same type as G | |
55 R = G.__class__() | |
56 # add graph attributes, H attributes take precedent over G attributes | |
57 R.graph.update(G.graph) | |
58 R.graph.update(H.graph) | |
59 | |
60 # rename graph to obtain disjoint node labels | |
61 def add_prefix(graph, prefix): | |
62 if prefix is None: | |
63 return graph | |
64 | |
65 def label(x): | |
66 if isinstance(x, str): | |
67 name = prefix + x | |
68 else: | |
69 name = prefix + repr(x) | |
70 return name | |
71 | |
72 return nx.relabel_nodes(graph, label) | |
73 | |
74 G = add_prefix(G, rename[0]) | |
75 H = add_prefix(H, rename[1]) | |
76 if set(G) & set(H): | |
77 raise nx.NetworkXError( | |
78 "The node sets of G and H are not disjoint.", | |
79 "Use appropriate rename=(Gprefix,Hprefix)" "or use disjoint_union(G,H).", | |
80 ) | |
81 if G.is_multigraph(): | |
82 G_edges = G.edges(keys=True, data=True) | |
83 else: | |
84 G_edges = G.edges(data=True) | |
85 if H.is_multigraph(): | |
86 H_edges = H.edges(keys=True, data=True) | |
87 else: | |
88 H_edges = H.edges(data=True) | |
89 | |
90 # add nodes | |
91 R.add_nodes_from(G) | |
92 R.add_nodes_from(H) | |
93 # add edges | |
94 R.add_edges_from(G_edges) | |
95 R.add_edges_from(H_edges) | |
96 # add node attributes | |
97 for n in G: | |
98 R.nodes[n].update(G.nodes[n]) | |
99 for n in H: | |
100 R.nodes[n].update(H.nodes[n]) | |
101 | |
102 return R | |
103 | |
104 | |
105 def disjoint_union(G, H): | |
106 """ Return the disjoint union of graphs G and H. | |
107 | |
108 This algorithm forces distinct integer node labels. | |
109 | |
110 Parameters | |
111 ---------- | |
112 G,H : graph | |
113 A NetworkX graph | |
114 | |
115 Returns | |
116 ------- | |
117 U : A union graph with the same type as G. | |
118 | |
119 Notes | |
120 ----- | |
121 A new graph is created, of the same class as G. It is recommended | |
122 that G and H be either both directed or both undirected. | |
123 | |
124 The nodes of G are relabeled 0 to len(G)-1, and the nodes of H are | |
125 relabeled len(G) to len(G)+len(H)-1. | |
126 | |
127 Graph, edge, and node attributes are propagated from G and H | |
128 to the union graph. If a graph attribute is present in both | |
129 G and H the value from H is used. | |
130 """ | |
131 R1 = nx.convert_node_labels_to_integers(G) | |
132 R2 = nx.convert_node_labels_to_integers(H, first_label=len(R1)) | |
133 R = union(R1, R2) | |
134 R.graph.update(G.graph) | |
135 R.graph.update(H.graph) | |
136 return R | |
137 | |
138 | |
139 def intersection(G, H): | |
140 """Returns a new graph that contains only the edges that exist in | |
141 both G and H. | |
142 | |
143 The node sets of H and G must be the same. | |
144 | |
145 Parameters | |
146 ---------- | |
147 G,H : graph | |
148 A NetworkX graph. G and H must have the same node sets. | |
149 | |
150 Returns | |
151 ------- | |
152 GH : A new graph with the same type as G. | |
153 | |
154 Notes | |
155 ----- | |
156 Attributes from the graph, nodes, and edges are not copied to the new | |
157 graph. If you want a new graph of the intersection of G and H | |
158 with the attributes (including edge data) from G use remove_nodes_from() | |
159 as follows | |
160 | |
161 >>> G = nx.path_graph(3) | |
162 >>> H = nx.path_graph(5) | |
163 >>> R = G.copy() | |
164 >>> R.remove_nodes_from(n for n in G if n not in H) | |
165 """ | |
166 # create new graph | |
167 R = nx.create_empty_copy(G) | |
168 | |
169 if not G.is_multigraph() == H.is_multigraph(): | |
170 raise nx.NetworkXError("G and H must both be graphs or multigraphs.") | |
171 if set(G) != set(H): | |
172 raise nx.NetworkXError("Node sets of graphs are not equal") | |
173 | |
174 if G.number_of_edges() <= H.number_of_edges(): | |
175 if G.is_multigraph(): | |
176 edges = G.edges(keys=True) | |
177 else: | |
178 edges = G.edges() | |
179 for e in edges: | |
180 if H.has_edge(*e): | |
181 R.add_edge(*e) | |
182 else: | |
183 if H.is_multigraph(): | |
184 edges = H.edges(keys=True) | |
185 else: | |
186 edges = H.edges() | |
187 for e in edges: | |
188 if G.has_edge(*e): | |
189 R.add_edge(*e) | |
190 return R | |
191 | |
192 | |
193 def difference(G, H): | |
194 """Returns a new graph that contains the edges that exist in G but not in H. | |
195 | |
196 The node sets of H and G must be the same. | |
197 | |
198 Parameters | |
199 ---------- | |
200 G,H : graph | |
201 A NetworkX graph. G and H must have the same node sets. | |
202 | |
203 Returns | |
204 ------- | |
205 D : A new graph with the same type as G. | |
206 | |
207 Notes | |
208 ----- | |
209 Attributes from the graph, nodes, and edges are not copied to the new | |
210 graph. If you want a new graph of the difference of G and H with | |
211 with the attributes (including edge data) from G use remove_nodes_from() | |
212 as follows: | |
213 | |
214 >>> G = nx.path_graph(3) | |
215 >>> H = nx.path_graph(5) | |
216 >>> R = G.copy() | |
217 >>> R.remove_nodes_from(n for n in G if n in H) | |
218 """ | |
219 # create new graph | |
220 if not G.is_multigraph() == H.is_multigraph(): | |
221 raise nx.NetworkXError("G and H must both be graphs or multigraphs.") | |
222 R = nx.create_empty_copy(G) | |
223 | |
224 if set(G) != set(H): | |
225 raise nx.NetworkXError("Node sets of graphs not equal") | |
226 | |
227 if G.is_multigraph(): | |
228 edges = G.edges(keys=True) | |
229 else: | |
230 edges = G.edges() | |
231 for e in edges: | |
232 if not H.has_edge(*e): | |
233 R.add_edge(*e) | |
234 return R | |
235 | |
236 | |
237 def symmetric_difference(G, H): | |
238 """Returns new graph with edges that exist in either G or H but not both. | |
239 | |
240 The node sets of H and G must be the same. | |
241 | |
242 Parameters | |
243 ---------- | |
244 G,H : graph | |
245 A NetworkX graph. G and H must have the same node sets. | |
246 | |
247 Returns | |
248 ------- | |
249 D : A new graph with the same type as G. | |
250 | |
251 Notes | |
252 ----- | |
253 Attributes from the graph, nodes, and edges are not copied to the new | |
254 graph. | |
255 """ | |
256 # create new graph | |
257 if not G.is_multigraph() == H.is_multigraph(): | |
258 raise nx.NetworkXError("G and H must both be graphs or multigraphs.") | |
259 R = nx.create_empty_copy(G) | |
260 | |
261 if set(G) != set(H): | |
262 raise nx.NetworkXError("Node sets of graphs not equal") | |
263 | |
264 gnodes = set(G) # set of nodes in G | |
265 hnodes = set(H) # set of nodes in H | |
266 nodes = gnodes.symmetric_difference(hnodes) | |
267 R.add_nodes_from(nodes) | |
268 | |
269 if G.is_multigraph(): | |
270 edges = G.edges(keys=True) | |
271 else: | |
272 edges = G.edges() | |
273 # we could copy the data here but then this function doesn't | |
274 # match intersection and difference | |
275 for e in edges: | |
276 if not H.has_edge(*e): | |
277 R.add_edge(*e) | |
278 | |
279 if H.is_multigraph(): | |
280 edges = H.edges(keys=True) | |
281 else: | |
282 edges = H.edges() | |
283 for e in edges: | |
284 if not G.has_edge(*e): | |
285 R.add_edge(*e) | |
286 return R | |
287 | |
288 | |
289 def compose(G, H): | |
290 """Returns a new graph of G composed with H. | |
291 | |
292 Composition is the simple union of the node sets and edge sets. | |
293 The node sets of G and H do not need to be disjoint. | |
294 | |
295 Parameters | |
296 ---------- | |
297 G, H : graph | |
298 A NetworkX graph | |
299 | |
300 Returns | |
301 ------- | |
302 C: A new graph with the same type as G | |
303 | |
304 Notes | |
305 ----- | |
306 It is recommended that G and H be either both directed or both undirected. | |
307 Attributes from H take precedent over attributes from G. | |
308 | |
309 For MultiGraphs, the edges are identified by incident nodes AND edge-key. | |
310 This can cause surprises (i.e., edge `(1, 2)` may or may not be the same | |
311 in two graphs) if you use MultiGraph without keeping track of edge keys. | |
312 """ | |
313 if not G.is_multigraph() == H.is_multigraph(): | |
314 raise nx.NetworkXError("G and H must both be graphs or multigraphs.") | |
315 | |
316 R = G.__class__() | |
317 # add graph attributes, H attributes take precedent over G attributes | |
318 R.graph.update(G.graph) | |
319 R.graph.update(H.graph) | |
320 | |
321 R.add_nodes_from(G.nodes(data=True)) | |
322 R.add_nodes_from(H.nodes(data=True)) | |
323 | |
324 if G.is_multigraph(): | |
325 R.add_edges_from(G.edges(keys=True, data=True)) | |
326 else: | |
327 R.add_edges_from(G.edges(data=True)) | |
328 if H.is_multigraph(): | |
329 R.add_edges_from(H.edges(keys=True, data=True)) | |
330 else: | |
331 R.add_edges_from(H.edges(data=True)) | |
332 return R | |
333 | |
334 | |
335 def full_join(G, H, rename=(None, None)): | |
336 """Returns the full join of graphs G and H. | |
337 | |
338 Full join is the union of G and H in which all edges between | |
339 G and H are added. | |
340 The node sets of G and H must be disjoint, | |
341 otherwise an exception is raised. | |
342 | |
343 Parameters | |
344 ---------- | |
345 G, H : graph | |
346 A NetworkX graph | |
347 | |
348 rename : bool , default=(None, None) | |
349 Node names of G and H can be changed by specifying the tuple | |
350 rename=('G-','H-') (for example). Node "u" in G is then renamed | |
351 "G-u" and "v" in H is renamed "H-v". | |
352 | |
353 Returns | |
354 ------- | |
355 U : The full join graph with the same type as G. | |
356 | |
357 Notes | |
358 ----- | |
359 It is recommended that G and H be either both directed or both undirected. | |
360 | |
361 If G is directed, then edges from G to H are added as well as from H to G. | |
362 | |
363 Note that full_join() does not produce parallel edges for MultiGraphs. | |
364 | |
365 The full join operation of graphs G and H is the same as getting | |
366 their complement, performing a disjoint union, and finally getting | |
367 the complement of the resulting graph. | |
368 | |
369 Graph, edge, and node attributes are propagated from G and H | |
370 to the union graph. If a graph attribute is present in both | |
371 G and H the value from H is used. | |
372 | |
373 See Also | |
374 -------- | |
375 union | |
376 disjoint_union | |
377 """ | |
378 R = union(G, H, rename) | |
379 | |
380 def add_prefix(graph, prefix): | |
381 if prefix is None: | |
382 return graph | |
383 | |
384 def label(x): | |
385 if isinstance(x, str): | |
386 name = prefix + x | |
387 else: | |
388 name = prefix + repr(x) | |
389 return name | |
390 | |
391 return nx.relabel_nodes(graph, label) | |
392 | |
393 G = add_prefix(G, rename[0]) | |
394 H = add_prefix(H, rename[1]) | |
395 | |
396 for i in G: | |
397 for j in H: | |
398 R.add_edge(i, j) | |
399 if R.is_directed(): | |
400 for i in H: | |
401 for j in G: | |
402 R.add_edge(i, j) | |
403 | |
404 return R |