Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/operators/binary.py: 24%
72 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Operations on graphs including union, intersection, difference.
3"""
4import networkx as nx
6__all__ = [
7 "union",
8 "compose",
9 "disjoint_union",
10 "intersection",
11 "difference",
12 "symmetric_difference",
13 "full_join",
14]
15_G_H = {"G": 0, "H": 1}
18@nx._dispatch(graphs=_G_H, preserve_all_attrs=True)
19def union(G, H, rename=()):
20 """Combine graphs G and H. The names of nodes must be unique.
22 A name collision between the graphs will raise an exception.
24 A renaming facility is provided to avoid name collisions.
27 Parameters
28 ----------
29 G, H : graph
30 A NetworkX graph
32 rename : iterable , optional
33 Node names of G and H can be changed by specifying the tuple
34 rename=('G-','H-') (for example). Node "u" in G is then renamed
35 "G-u" and "v" in H is renamed "H-v".
37 Returns
38 -------
39 U : A union graph with the same type as G.
41 See Also
42 --------
43 compose
44 :func:`~networkx.Graph.update`
45 disjoint_union
47 Notes
48 -----
49 To combine graphs that have common nodes, consider compose(G, H)
50 or the method, Graph.update().
52 disjoint_union() is similar to union() except that it avoids name clashes
53 by relabeling the nodes with sequential integers.
55 Edge and node attributes are propagated from G and H to the union graph.
56 Graph attributes are also propagated, but if they are present in both G and H,
57 then the value from H is used.
59 Examples
60 --------
61 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
62 >>> H = nx.Graph([(0, 1), (0, 3), (1, 3), (1, 2)])
63 >>> U = nx.union(G, H, rename=("G", "H"))
64 >>> U.nodes
65 NodeView(('G0', 'G1', 'G2', 'H0', 'H1', 'H3', 'H2'))
66 >>> U.edges
67 EdgeView([('G0', 'G1'), ('G0', 'G2'), ('G1', 'G2'), ('H0', 'H1'), ('H0', 'H3'), ('H1', 'H3'), ('H1', 'H2')])
70 """
71 return nx.union_all([G, H], rename)
74@nx._dispatch(graphs=_G_H, preserve_all_attrs=True)
75def disjoint_union(G, H):
76 """Combine graphs G and H. The nodes are assumed to be unique (disjoint).
78 This algorithm automatically relabels nodes to avoid name collisions.
80 Parameters
81 ----------
82 G,H : graph
83 A NetworkX graph
85 Returns
86 -------
87 U : A union graph with the same type as G.
89 See Also
90 --------
91 union
92 compose
93 :func:`~networkx.Graph.update`
95 Notes
96 -----
97 A new graph is created, of the same class as G. It is recommended
98 that G and H be either both directed or both undirected.
100 The nodes of G are relabeled 0 to len(G)-1, and the nodes of H are
101 relabeled len(G) to len(G)+len(H)-1.
103 Renumbering forces G and H to be disjoint, so no exception is ever raised for a name collision.
104 To preserve the check for common nodes, use union().
106 Edge and node attributes are propagated from G and H to the union graph.
107 Graph attributes are also propagated, but if they are present in both G and H,
108 then the value from H is used.
110 To combine graphs that have common nodes, consider compose(G, H)
111 or the method, Graph.update().
113 Examples
114 --------
115 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
116 >>> H = nx.Graph([(0, 3), (1, 2), (2, 3)])
117 >>> G.nodes[0]["key1"] = 5
118 >>> H.nodes[0]["key2"] = 10
119 >>> U = nx.disjoint_union(G, H)
120 >>> U.nodes(data=True)
121 NodeDataView({0: {'key1': 5}, 1: {}, 2: {}, 3: {'key2': 10}, 4: {}, 5: {}, 6: {}})
122 >>> U.edges
123 EdgeView([(0, 1), (0, 2), (1, 2), (3, 4), (4, 6), (5, 6)])
124 """
125 return nx.disjoint_union_all([G, H])
128@nx._dispatch(graphs=_G_H)
129def intersection(G, H):
130 """Returns a new graph that contains only the nodes and the edges that exist in
131 both G and H.
133 Parameters
134 ----------
135 G,H : graph
136 A NetworkX graph. G and H can have different node sets but must be both graphs or both multigraphs.
138 Raises
139 ------
140 NetworkXError
141 If one is a MultiGraph and the other one is a graph.
143 Returns
144 -------
145 GH : A new graph with the same type as G.
147 Notes
148 -----
149 Attributes from the graph, nodes, and edges are not copied to the new
150 graph. If you want a new graph of the intersection of G and H
151 with the attributes (including edge data) from G use remove_nodes_from()
152 as follows
154 >>> G = nx.path_graph(3)
155 >>> H = nx.path_graph(5)
156 >>> R = G.copy()
157 >>> R.remove_nodes_from(n for n in G if n not in H)
158 >>> R.remove_edges_from(e for e in G.edges if e not in H.edges)
160 Examples
161 --------
162 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
163 >>> H = nx.Graph([(0, 3), (1, 2), (2, 3)])
164 >>> R = nx.intersection(G, H)
165 >>> R.nodes
166 NodeView((0, 1, 2))
167 >>> R.edges
168 EdgeView([(1, 2)])
169 """
170 return nx.intersection_all([G, H])
173@nx._dispatch(graphs=_G_H)
174def difference(G, H):
175 """Returns a new graph that contains the edges that exist in G but not in H.
177 The node sets of H and G must be the same.
179 Parameters
180 ----------
181 G,H : graph
182 A NetworkX graph. G and H must have the same node sets.
184 Returns
185 -------
186 D : A new graph with the same type as G.
188 Notes
189 -----
190 Attributes from the graph, nodes, and edges are not copied to the new
191 graph. If you want a new graph of the difference of G and H with
192 the attributes (including edge data) from G use remove_nodes_from()
193 as follows:
195 >>> G = nx.path_graph(3)
196 >>> H = nx.path_graph(5)
197 >>> R = G.copy()
198 >>> R.remove_nodes_from(n for n in G if n in H)
200 Examples
201 --------
202 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3)])
203 >>> H = nx.Graph([(0, 1), (1, 2), (0, 3)])
204 >>> R = nx.difference(G, H)
205 >>> R.nodes
206 NodeView((0, 1, 2, 3))
207 >>> R.edges
208 EdgeView([(0, 2), (1, 3)])
209 """
210 # create new graph
211 if not G.is_multigraph() == H.is_multigraph():
212 raise nx.NetworkXError("G and H must both be graphs or multigraphs.")
213 R = nx.create_empty_copy(G)
215 if set(G) != set(H):
216 raise nx.NetworkXError("Node sets of graphs not equal")
218 if G.is_multigraph():
219 edges = G.edges(keys=True)
220 else:
221 edges = G.edges()
222 for e in edges:
223 if not H.has_edge(*e):
224 R.add_edge(*e)
225 return R
228@nx._dispatch(graphs=_G_H)
229def symmetric_difference(G, H):
230 """Returns new graph with edges that exist in either G or H but not both.
232 The node sets of H and G must be the same.
234 Parameters
235 ----------
236 G,H : graph
237 A NetworkX graph. G and H must have the same node sets.
239 Returns
240 -------
241 D : A new graph with the same type as G.
243 Notes
244 -----
245 Attributes from the graph, nodes, and edges are not copied to the new
246 graph.
248 Examples
249 --------
250 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3)])
251 >>> H = nx.Graph([(0, 1), (1, 2), (0, 3)])
252 >>> R = nx.symmetric_difference(G, H)
253 >>> R.nodes
254 NodeView((0, 1, 2, 3))
255 >>> R.edges
256 EdgeView([(0, 2), (0, 3), (1, 3)])
257 """
258 # create new graph
259 if not G.is_multigraph() == H.is_multigraph():
260 raise nx.NetworkXError("G and H must both be graphs or multigraphs.")
261 R = nx.create_empty_copy(G)
263 if set(G) != set(H):
264 raise nx.NetworkXError("Node sets of graphs not equal")
266 gnodes = set(G) # set of nodes in G
267 hnodes = set(H) # set of nodes in H
268 nodes = gnodes.symmetric_difference(hnodes)
269 R.add_nodes_from(nodes)
271 if G.is_multigraph():
272 edges = G.edges(keys=True)
273 else:
274 edges = G.edges()
275 # we could copy the data here but then this function doesn't
276 # match intersection and difference
277 for e in edges:
278 if not H.has_edge(*e):
279 R.add_edge(*e)
281 if H.is_multigraph():
282 edges = H.edges(keys=True)
283 else:
284 edges = H.edges()
285 for e in edges:
286 if not G.has_edge(*e):
287 R.add_edge(*e)
288 return R
291@nx._dispatch(graphs=_G_H, preserve_all_attrs=True)
292def compose(G, H):
293 """Compose graph G with H by combining nodes and edges into a single graph.
295 The node sets and edges sets do not need to be disjoint.
297 Composing preserves the attributes of nodes and edges.
298 Attribute values from H take precedent over attribute values from G.
300 Parameters
301 ----------
302 G, H : graph
303 A NetworkX graph
305 Returns
306 -------
307 C: A new graph with the same type as G
309 See Also
310 --------
311 :func:`~networkx.Graph.update`
312 union
313 disjoint_union
315 Notes
316 -----
317 It is recommended that G and H be either both directed or both undirected.
319 For MultiGraphs, the edges are identified by incident nodes AND edge-key.
320 This can cause surprises (i.e., edge `(1, 2)` may or may not be the same
321 in two graphs) if you use MultiGraph without keeping track of edge keys.
323 If combining the attributes of common nodes is not desired, consider union(),
324 which raises an exception for name collisions.
326 Examples
327 --------
328 >>> G = nx.Graph([(0, 1), (0, 2)])
329 >>> H = nx.Graph([(0, 1), (1, 2)])
330 >>> R = nx.compose(G, H)
331 >>> R.nodes
332 NodeView((0, 1, 2))
333 >>> R.edges
334 EdgeView([(0, 1), (0, 2), (1, 2)])
336 By default, the attributes from `H` take precedent over attributes from `G`.
337 If you prefer another way of combining attributes, you can update them after the compose operation:
339 >>> G = nx.Graph([(0, 1, {'weight': 2.0}), (3, 0, {'weight': 100.0})])
340 >>> H = nx.Graph([(0, 1, {'weight': 10.0}), (1, 2, {'weight': -1.0})])
341 >>> nx.set_node_attributes(G, {0: 'dark', 1: 'light', 3: 'black'}, name='color')
342 >>> nx.set_node_attributes(H, {0: 'green', 1: 'orange', 2: 'yellow'}, name='color')
343 >>> GcomposeH = nx.compose(G, H)
345 Normally, color attribute values of nodes of GcomposeH come from H. We can workaround this as follows:
347 >>> node_data = {n: G.nodes[n]['color'] + " " + H.nodes[n]['color'] for n in G.nodes & H.nodes}
348 >>> nx.set_node_attributes(GcomposeH, node_data, 'color')
349 >>> print(GcomposeH.nodes[0]['color'])
350 dark green
352 >>> print(GcomposeH.nodes[3]['color'])
353 black
355 Similarly, we can update edge attributes after the compose operation in a way we prefer:
357 >>> edge_data = {e: G.edges[e]['weight'] * H.edges[e]['weight'] for e in G.edges & H.edges}
358 >>> nx.set_edge_attributes(GcomposeH, edge_data, 'weight')
359 >>> print(GcomposeH.edges[(0, 1)]['weight'])
360 20.0
362 >>> print(GcomposeH.edges[(3, 0)]['weight'])
363 100.0
364 """
365 return nx.compose_all([G, H])
368@nx._dispatch(graphs=_G_H, preserve_all_attrs=True)
369def full_join(G, H, rename=(None, None)):
370 """Returns the full join of graphs G and H.
372 Full join is the union of G and H in which all edges between
373 G and H are added.
374 The node sets of G and H must be disjoint,
375 otherwise an exception is raised.
377 Parameters
378 ----------
379 G, H : graph
380 A NetworkX graph
382 rename : tuple , default=(None, None)
383 Node names of G and H can be changed by specifying the tuple
384 rename=('G-','H-') (for example). Node "u" in G is then renamed
385 "G-u" and "v" in H is renamed "H-v".
387 Returns
388 -------
389 U : The full join graph with the same type as G.
391 Notes
392 -----
393 It is recommended that G and H be either both directed or both undirected.
395 If G is directed, then edges from G to H are added as well as from H to G.
397 Note that full_join() does not produce parallel edges for MultiGraphs.
399 The full join operation of graphs G and H is the same as getting
400 their complement, performing a disjoint union, and finally getting
401 the complement of the resulting graph.
403 Graph, edge, and node attributes are propagated from G and H
404 to the union graph. If a graph attribute is present in both
405 G and H the value from H is used.
407 Examples
408 --------
409 >>> G = nx.Graph([(0, 1), (0, 2)])
410 >>> H = nx.Graph([(3, 4)])
411 >>> R = nx.full_join(G, H, rename=("G", "H"))
412 >>> R.nodes
413 NodeView(('G0', 'G1', 'G2', 'H3', 'H4'))
414 >>> R.edges
415 EdgeView([('G0', 'G1'), ('G0', 'G2'), ('G0', 'H3'), ('G0', 'H4'), ('G1', 'H3'), ('G1', 'H4'), ('G2', 'H3'), ('G2', 'H4'), ('H3', 'H4')])
417 See Also
418 --------
419 union
420 disjoint_union
421 """
422 R = union(G, H, rename)
424 def add_prefix(graph, prefix):
425 if prefix is None:
426 return graph
428 def label(x):
429 return f"{prefix}{x}"
431 return nx.relabel_nodes(graph, label)
433 G = add_prefix(G, rename[0])
434 H = add_prefix(H, rename[1])
436 for i in G:
437 for j in H:
438 R.add_edge(i, j)
439 if R.is_directed():
440 for i in H:
441 for j in G:
442 R.add_edge(i, j)
444 return R