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"""
2Operations on graphs including union, intersection, difference.
3"""
5import networkx as nx
7__all__ = [
8 "union",
9 "compose",
10 "disjoint_union",
11 "intersection",
12 "difference",
13 "symmetric_difference",
14 "full_join",
15]
16_G_H = {"G": 0, "H": 1}
19@nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True)
20def union(G, H, rename=()):
21 """Combine graphs G and H. The names of nodes must be unique.
23 A name collision between the graphs will raise an exception.
25 A renaming facility is provided to avoid name collisions.
28 Parameters
29 ----------
30 G, H : graph
31 A NetworkX graph
33 rename : iterable , optional
34 Node names of G and H can be changed by specifying the tuple
35 rename=('G-','H-') (for example). Node "u" in G is then renamed
36 "G-u" and "v" in H is renamed "H-v".
38 Returns
39 -------
40 U : A union graph with the same type as G.
42 See Also
43 --------
44 compose
45 :func:`~networkx.Graph.update`
46 disjoint_union
48 Notes
49 -----
50 To combine graphs that have common nodes, consider compose(G, H)
51 or the method, Graph.update().
53 disjoint_union() is similar to union() except that it avoids name clashes
54 by relabeling the nodes with sequential integers.
56 Edge and node attributes are propagated from G and H to the union graph.
57 Graph attributes are also propagated, but if they are present in both G and H,
58 then the value from H is used.
60 Examples
61 --------
62 >>> from pprint import pprint
63 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
64 >>> H = nx.Graph([(0, 1), (0, 3), (1, 3), (1, 2)])
65 >>> U = nx.union(G, H, rename=("G", "H"))
66 >>> U.nodes
67 NodeView(('G0', 'G1', 'G2', 'H0', 'H1', 'H3', 'H2'))
68 >>> edgelist = list(U.edges)
69 >>> pprint(edgelist)
70 [('G0', 'G1'),
71 ('G0', 'G2'),
72 ('G1', 'G2'),
73 ('H0', 'H1'),
74 ('H0', 'H3'),
75 ('H1', 'H3'),
76 ('H1', 'H2')]
79 """
80 return nx.union_all([G, H], rename)
83@nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True)
84def disjoint_union(G, H):
85 """Combine graphs G and H. The nodes are assumed to be unique (disjoint).
87 This algorithm automatically relabels nodes to avoid name collisions.
89 Parameters
90 ----------
91 G,H : graph
92 A NetworkX graph
94 Returns
95 -------
96 U : A union graph with the same type as G.
98 See Also
99 --------
100 union
101 compose
102 :func:`~networkx.Graph.update`
104 Notes
105 -----
106 A new graph is created, of the same class as G. It is recommended
107 that G and H be either both directed or both undirected.
109 The nodes of G are relabeled 0 to len(G)-1, and the nodes of H are
110 relabeled len(G) to len(G)+len(H)-1.
112 Renumbering forces G and H to be disjoint, so no exception is ever raised for a name collision.
113 To preserve the check for common nodes, use union().
115 Edge and node attributes are propagated from G and H to the union graph.
116 Graph attributes are also propagated, but if they are present in both G and H,
117 then the value from H is used.
119 To combine graphs that have common nodes, consider compose(G, H)
120 or the method, Graph.update().
122 Examples
123 --------
124 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
125 >>> H = nx.Graph([(0, 3), (1, 2), (2, 3)])
126 >>> G.nodes[0]["key1"] = 5
127 >>> H.nodes[0]["key2"] = 10
128 >>> U = nx.disjoint_union(G, H)
129 >>> U.nodes(data=True)
130 NodeDataView({0: {'key1': 5}, 1: {}, 2: {}, 3: {'key2': 10}, 4: {}, 5: {}, 6: {}})
131 >>> U.edges
132 EdgeView([(0, 1), (0, 2), (1, 2), (3, 4), (4, 6), (5, 6)])
133 """
134 return nx.disjoint_union_all([G, H])
137@nx._dispatchable(graphs=_G_H, returns_graph=True)
138def intersection(G, H):
139 """Returns a new graph that contains only the nodes and the edges that exist in
140 both G and H.
142 Parameters
143 ----------
144 G,H : graph
145 A NetworkX graph. G and H can have different node sets but must be both graphs or both multigraphs.
147 Raises
148 ------
149 NetworkXError
150 If one is a MultiGraph and the other one is a graph.
152 Returns
153 -------
154 GH : A new graph with the same type as G.
156 Notes
157 -----
158 Attributes from the graph, nodes, and edges are not copied to the new
159 graph. If you want a new graph of the intersection of G and H
160 with the attributes (including edge data) from G use remove_nodes_from()
161 as follows
163 >>> G = nx.path_graph(3)
164 >>> H = nx.path_graph(5)
165 >>> R = G.copy()
166 >>> R.remove_nodes_from(n for n in G if n not in H)
167 >>> R.remove_edges_from(e for e in G.edges if e not in H.edges)
169 Examples
170 --------
171 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
172 >>> H = nx.Graph([(0, 3), (1, 2), (2, 3)])
173 >>> R = nx.intersection(G, H)
174 >>> R.nodes
175 NodeView((0, 1, 2))
176 >>> R.edges
177 EdgeView([(1, 2)])
178 """
179 return nx.intersection_all([G, H])
182@nx._dispatchable(graphs=_G_H, returns_graph=True)
183def difference(G, H):
184 """Returns a new graph that contains the edges that exist in G but not in H.
186 The node sets of H and G must be the same.
188 Parameters
189 ----------
190 G,H : graph
191 A NetworkX graph. G and H must have the same node sets.
193 Returns
194 -------
195 D : A new graph with the same type as G.
197 Notes
198 -----
199 Attributes from the graph, nodes, and edges are not copied to the new
200 graph. If you want a new graph of the difference of G and H with
201 the attributes (including edge data) from G use remove_nodes_from()
202 as follows:
204 >>> G = nx.path_graph(3)
205 >>> H = nx.path_graph(5)
206 >>> R = G.copy()
207 >>> R.remove_nodes_from(n for n in G if n in H)
209 Examples
210 --------
211 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3)])
212 >>> H = nx.Graph([(0, 1), (1, 2), (0, 3)])
213 >>> R = nx.difference(G, H)
214 >>> R.nodes
215 NodeView((0, 1, 2, 3))
216 >>> R.edges
217 EdgeView([(0, 2), (1, 3)])
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, with_data=False)
224 if set(G) != set(H):
225 raise nx.NetworkXError("Node sets of graphs not equal")
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
237@nx._dispatchable(graphs=_G_H, returns_graph=True)
238def symmetric_difference(G, H):
239 """Returns new graph with edges that exist in either G or H but not both.
241 The node sets of H and G must be the same.
243 Parameters
244 ----------
245 G,H : graph
246 A NetworkX graph. G and H must have the same node sets.
248 Returns
249 -------
250 D : A new graph with the same type as G.
252 Notes
253 -----
254 Attributes from the graph, nodes, and edges are not copied to the new
255 graph.
257 Examples
258 --------
259 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3)])
260 >>> H = nx.Graph([(0, 1), (1, 2), (0, 3)])
261 >>> R = nx.symmetric_difference(G, H)
262 >>> R.nodes
263 NodeView((0, 1, 2, 3))
264 >>> R.edges
265 EdgeView([(0, 2), (0, 3), (1, 3)])
266 """
267 # create new graph
268 if not G.is_multigraph() == H.is_multigraph():
269 raise nx.NetworkXError("G and H must both be graphs or multigraphs.")
270 R = nx.create_empty_copy(G, with_data=False)
272 if set(G) != set(H):
273 raise nx.NetworkXError("Node sets of graphs not equal")
275 gnodes = set(G) # set of nodes in G
276 hnodes = set(H) # set of nodes in H
277 nodes = gnodes.symmetric_difference(hnodes)
278 R.add_nodes_from(nodes)
280 if G.is_multigraph():
281 edges = G.edges(keys=True)
282 else:
283 edges = G.edges()
284 # we could copy the data here but then this function doesn't
285 # match intersection and difference
286 for e in edges:
287 if not H.has_edge(*e):
288 R.add_edge(*e)
290 if H.is_multigraph():
291 edges = H.edges(keys=True)
292 else:
293 edges = H.edges()
294 for e in edges:
295 if not G.has_edge(*e):
296 R.add_edge(*e)
297 return R
300@nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True)
301def compose(G, H):
302 """Compose graph G with H by combining nodes and edges into a single graph.
304 The node sets and edges sets do not need to be disjoint.
306 Composing preserves the attributes of nodes and edges.
307 Attribute values from H take precedent over attribute values from G.
309 Parameters
310 ----------
311 G, H : graph
312 A NetworkX graph
314 Returns
315 -------
316 C: A new graph with the same type as G
318 See Also
319 --------
320 :func:`~networkx.Graph.update`
321 union
322 disjoint_union
324 Notes
325 -----
326 It is recommended that G and H be either both directed or both undirected.
328 For MultiGraphs, the edges are identified by incident nodes AND edge-key.
329 This can cause surprises (i.e., edge `(1, 2)` may or may not be the same
330 in two graphs) if you use MultiGraph without keeping track of edge keys.
332 If combining the attributes of common nodes is not desired, consider union(),
333 which raises an exception for name collisions.
335 Examples
336 --------
337 >>> G = nx.Graph([(0, 1), (0, 2)])
338 >>> H = nx.Graph([(0, 1), (1, 2)])
339 >>> R = nx.compose(G, H)
340 >>> R.nodes
341 NodeView((0, 1, 2))
342 >>> R.edges
343 EdgeView([(0, 1), (0, 2), (1, 2)])
345 By default, the attributes from `H` take precedent over attributes from `G`.
346 If you prefer another way of combining attributes, you can update them after the compose operation:
348 >>> G = nx.Graph([(0, 1, {"weight": 2.0}), (3, 0, {"weight": 100.0})])
349 >>> H = nx.Graph([(0, 1, {"weight": 10.0}), (1, 2, {"weight": -1.0})])
350 >>> nx.set_node_attributes(G, {0: "dark", 1: "light", 3: "black"}, name="color")
351 >>> nx.set_node_attributes(H, {0: "green", 1: "orange", 2: "yellow"}, name="color")
352 >>> GcomposeH = nx.compose(G, H)
354 Normally, color attribute values of nodes of GcomposeH come from H. We can workaround this as follows:
356 >>> node_data = {
357 ... n: G.nodes[n]["color"] + " " + H.nodes[n]["color"]
358 ... for n in G.nodes & H.nodes
359 ... }
360 >>> nx.set_node_attributes(GcomposeH, node_data, "color")
361 >>> print(GcomposeH.nodes[0]["color"])
362 dark green
364 >>> print(GcomposeH.nodes[3]["color"])
365 black
367 Similarly, we can update edge attributes after the compose operation in a way we prefer:
369 >>> edge_data = {
370 ... e: G.edges[e]["weight"] * H.edges[e]["weight"] for e in G.edges & H.edges
371 ... }
372 >>> nx.set_edge_attributes(GcomposeH, edge_data, "weight")
373 >>> print(GcomposeH.edges[(0, 1)]["weight"])
374 20.0
376 >>> print(GcomposeH.edges[(3, 0)]["weight"])
377 100.0
378 """
379 return nx.compose_all([G, H])
382@nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True)
383def full_join(G, H, rename=(None, None)):
384 """Returns the full join of graphs G and H.
386 Full join is the union of G and H in which all edges between
387 G and H are added.
388 The node sets of G and H must be disjoint,
389 otherwise an exception is raised.
391 Parameters
392 ----------
393 G, H : graph
394 A NetworkX graph
396 rename : tuple , default=(None, None)
397 Node names of G and H can be changed by specifying the tuple
398 rename=('G-','H-') (for example). Node "u" in G is then renamed
399 "G-u" and "v" in H is renamed "H-v".
401 Returns
402 -------
403 U : The full join graph with the same type as G.
405 Notes
406 -----
407 It is recommended that G and H be either both directed or both undirected.
409 If G is directed, then edges from G to H are added as well as from H to G.
411 Note that full_join() does not produce parallel edges for MultiGraphs.
413 The full join operation of graphs G and H is the same as getting
414 their complement, performing a disjoint union, and finally getting
415 the complement of the resulting graph.
417 Graph, edge, and node attributes are propagated from G and H
418 to the union graph. If a graph attribute is present in both
419 G and H the value from H is used.
421 Examples
422 --------
423 >>> from pprint import pprint
424 >>> G = nx.Graph([(0, 1), (0, 2)])
425 >>> H = nx.Graph([(3, 4)])
426 >>> R = nx.full_join(G, H, rename=("G", "H"))
427 >>> R.nodes
428 NodeView(('G0', 'G1', 'G2', 'H3', 'H4'))
429 >>> edgelist = list(R.edges)
430 >>> pprint(edgelist)
431 [('G0', 'G1'),
432 ('G0', 'G2'),
433 ('G0', 'H3'),
434 ('G0', 'H4'),
435 ('G1', 'H3'),
436 ('G1', 'H4'),
437 ('G2', 'H3'),
438 ('G2', 'H4'),
439 ('H3', 'H4')]
441 See Also
442 --------
443 union
444 disjoint_union
445 """
446 R = union(G, H, rename)
448 def add_prefix(graph, prefix):
449 if prefix is None:
450 return graph
452 def label(x):
453 return f"{prefix}{x}"
455 return nx.relabel_nodes(graph, label)
457 G = add_prefix(G, rename[0])
458 H = add_prefix(H, rename[1])
460 for i in G:
461 for j in H:
462 R.add_edge(i, j)
463 if R.is_directed():
464 for i in H:
465 for j in G:
466 R.add_edge(i, j)
468 return R