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"""Operations on many graphs."""
3from itertools import chain, repeat
5import networkx as nx
7__all__ = ["union_all", "compose_all", "disjoint_union_all", "intersection_all"]
10@nx._dispatchable(graphs="[graphs]", preserve_all_attrs=True, returns_graph=True)
11def union_all(graphs, rename=()):
12 """Returns the union of all graphs.
14 The graphs must be disjoint, otherwise an exception is raised.
16 Parameters
17 ----------
18 graphs : iterable
19 Iterable of NetworkX graphs
21 rename : iterable , optional
22 Node names of graphs can be changed by specifying the tuple
23 rename=('G-','H-') (for example). Node "u" in G is then renamed
24 "G-u" and "v" in H is renamed "H-v". Infinite generators (like itertools.count)
25 are also supported.
27 Returns
28 -------
29 U : a graph with the same type as the first graph in list
31 Raises
32 ------
33 ValueError
34 If `graphs` is an empty list.
36 NetworkXError
37 In case of mixed type graphs, like MultiGraph and Graph, or directed and undirected graphs.
39 Notes
40 -----
41 For operating on mixed type graphs, they should be converted to the same type.
42 >>> G = nx.Graph()
43 >>> H = nx.DiGraph()
44 >>> GH = union_all([nx.DiGraph(G), H])
46 To force a disjoint union with node relabeling, use
47 disjoint_union_all(G,H) or convert_node_labels_to integers().
49 Graph, edge, and node attributes are propagated to the union graph.
50 If a graph attribute is present in multiple graphs, then the value
51 from the last graph in the list with that attribute is used.
53 Examples
54 --------
55 >>> G1 = nx.Graph([(1, 2), (2, 3)])
56 >>> G2 = nx.Graph([(4, 5), (5, 6)])
57 >>> result_graph = nx.union_all([G1, G2])
58 >>> result_graph.nodes()
59 NodeView((1, 2, 3, 4, 5, 6))
60 >>> result_graph.edges()
61 EdgeView([(1, 2), (2, 3), (4, 5), (5, 6)])
63 See Also
64 --------
65 union
66 disjoint_union_all
67 """
68 R = None
69 seen_nodes = set()
71 # rename graph to obtain disjoint node labels
72 def add_prefix(graph, prefix):
73 if prefix is None:
74 return graph
76 def label(x):
77 return f"{prefix}{x}"
79 return nx.relabel_nodes(graph, label)
81 rename = chain(rename, repeat(None))
82 graphs = (add_prefix(G, name) for G, name in zip(graphs, rename))
84 for i, G in enumerate(graphs):
85 G_nodes_set = set(G.nodes)
86 if i == 0:
87 # Union is the same type as first graph
88 R = G.__class__()
89 elif G.is_directed() != R.is_directed():
90 raise nx.NetworkXError("All graphs must be directed or undirected.")
91 elif G.is_multigraph() != R.is_multigraph():
92 raise nx.NetworkXError("All graphs must be graphs or multigraphs.")
93 elif not seen_nodes.isdisjoint(G_nodes_set):
94 raise nx.NetworkXError(
95 "The node sets of the graphs are not disjoint.\n"
96 "Use `rename` to specify prefixes for the graphs or use\n"
97 "disjoint_union(G1, G2, ..., GN)."
98 )
100 seen_nodes |= G_nodes_set
101 R.graph.update(G.graph)
102 R.add_nodes_from(G.nodes(data=True))
103 R.add_edges_from(
104 G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
105 )
107 if R is None:
108 raise ValueError("cannot apply union_all to an empty list")
110 return R
113@nx._dispatchable(graphs="[graphs]", preserve_all_attrs=True, returns_graph=True)
114def disjoint_union_all(graphs):
115 """Returns the disjoint union of all graphs.
117 This operation forces distinct integer node labels starting with 0
118 for the first graph in the list and numbering consecutively.
120 Parameters
121 ----------
122 graphs : iterable
123 Iterable of NetworkX graphs
125 Returns
126 -------
127 U : A graph with the same type as the first graph in list
129 Raises
130 ------
131 ValueError
132 If `graphs` is an empty list.
134 NetworkXError
135 In case of mixed type graphs, like MultiGraph and Graph, or directed and undirected graphs.
137 Examples
138 --------
139 >>> G1 = nx.Graph([(1, 2), (2, 3)])
140 >>> G2 = nx.Graph([(4, 5), (5, 6)])
141 >>> U = nx.disjoint_union_all([G1, G2])
142 >>> list(U.nodes())
143 [0, 1, 2, 3, 4, 5]
144 >>> list(U.edges())
145 [(0, 1), (1, 2), (3, 4), (4, 5)]
147 Notes
148 -----
149 For operating on mixed type graphs, they should be converted to the same type.
151 Graph, edge, and node attributes are propagated to the union graph.
152 If a graph attribute is present in multiple graphs, then the value
153 from the last graph in the list with that attribute is used.
154 """
156 def yield_relabeled(graphs):
157 first_label = 0
158 for G in graphs:
159 yield nx.convert_node_labels_to_integers(G, first_label=first_label)
160 first_label += len(G)
162 R = union_all(yield_relabeled(graphs))
164 return R
167@nx._dispatchable(graphs="[graphs]", preserve_all_attrs=True, returns_graph=True)
168def compose_all(graphs):
169 """Returns the composition of all graphs.
171 Composition is the simple union of the node sets and edge sets.
172 The node sets of the supplied graphs need not be disjoint.
174 Parameters
175 ----------
176 graphs : iterable
177 Iterable of NetworkX graphs
179 Returns
180 -------
181 C : A graph with the same type as the first graph in list
183 Raises
184 ------
185 ValueError
186 If `graphs` is an empty list.
188 NetworkXError
189 In case of mixed type graphs, like MultiGraph and Graph, or directed and undirected graphs.
191 Examples
192 --------
193 >>> G1 = nx.Graph([(1, 2), (2, 3)])
194 >>> G2 = nx.Graph([(3, 4), (5, 6)])
195 >>> C = nx.compose_all([G1, G2])
196 >>> list(C.nodes())
197 [1, 2, 3, 4, 5, 6]
198 >>> list(C.edges())
199 [(1, 2), (2, 3), (3, 4), (5, 6)]
201 Notes
202 -----
203 For operating on mixed type graphs, they should be converted to the same type.
205 Graph, edge, and node attributes are propagated to the union graph.
206 If a graph attribute is present in multiple graphs, then the value
207 from the last graph in the list with that attribute is used.
208 """
209 R = None
211 # add graph attributes, H attributes take precedent over G attributes
212 for i, G in enumerate(graphs):
213 if i == 0:
214 # create new graph
215 R = G.__class__()
216 elif G.is_directed() != R.is_directed():
217 raise nx.NetworkXError("All graphs must be directed or undirected.")
218 elif G.is_multigraph() != R.is_multigraph():
219 raise nx.NetworkXError("All graphs must be graphs or multigraphs.")
221 R.graph.update(G.graph)
222 R.add_nodes_from(G.nodes(data=True))
223 R.add_edges_from(
224 G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
225 )
227 if R is None:
228 raise ValueError("cannot apply compose_all to an empty list")
230 return R
233@nx._dispatchable(graphs="[graphs]", returns_graph=True)
234def intersection_all(graphs):
235 """Returns a new graph that contains only the nodes and the edges that exist in
236 all graphs.
238 Parameters
239 ----------
240 graphs : iterable
241 Iterable of NetworkX graphs
243 Returns
244 -------
245 R : A new graph with the same type as the first graph in list
247 Raises
248 ------
249 ValueError
250 If `graphs` is an empty list.
252 NetworkXError
253 In case of mixed type graphs, like MultiGraph and Graph, or directed and undirected graphs.
255 Notes
256 -----
257 For operating on mixed type graphs, they should be converted to the same type.
259 Attributes from the graph, nodes, and edges are not copied to the new
260 graph.
262 The resulting graph can be updated with attributes if desired.
263 For example, code which adds the minimum attribute for each node across all
264 graphs could work::
266 >>> g = nx.Graph()
267 >>> g.add_node(0, capacity=4)
268 >>> g.add_node(1, capacity=3)
269 >>> g.add_edge(0, 1)
271 >>> h = g.copy()
272 >>> h.nodes[0]["capacity"] = 2
274 >>> gh = nx.intersection_all([g, h])
276 >>> new_node_attr = {
277 ... n: min(*(anyG.nodes[n].get("capacity", float("inf")) for anyG in [g, h]))
278 ... for n in gh
279 ... }
280 >>> nx.set_node_attributes(gh, new_node_attr, "new_capacity")
281 >>> gh.nodes(data=True)
282 NodeDataView({0: {'new_capacity': 2}, 1: {'new_capacity': 3}})
284 Examples
285 --------
286 >>> G1 = nx.Graph([(1, 2), (2, 3)])
287 >>> G2 = nx.Graph([(2, 3), (3, 4)])
288 >>> R = nx.intersection_all([G1, G2])
289 >>> list(R.nodes())
290 [2, 3]
291 >>> list(R.edges())
292 [(2, 3)]
294 """
295 R = None
297 for i, G in enumerate(graphs):
298 G_nodes_set = set(G.nodes)
299 G_edges_set = set(G.edges)
300 if not G.is_directed():
301 if G.is_multigraph():
302 G_edges_set.update((v, u, k) for u, v, k in list(G_edges_set))
303 else:
304 G_edges_set.update((v, u) for u, v in list(G_edges_set))
305 if i == 0:
306 # create new graph
307 R = G.__class__()
308 node_intersection = G_nodes_set
309 edge_intersection = G_edges_set
310 elif G.is_directed() != R.is_directed():
311 raise nx.NetworkXError("All graphs must be directed or undirected.")
312 elif G.is_multigraph() != R.is_multigraph():
313 raise nx.NetworkXError("All graphs must be graphs or multigraphs.")
314 else:
315 node_intersection &= G_nodes_set
316 edge_intersection &= G_edges_set
318 if R is None:
319 raise ValueError("cannot apply intersection_all to an empty list")
321 R.add_nodes_from(node_intersection)
322 R.add_edges_from(edge_intersection)
324 return R