Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/operators/all.py: 13%
82 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Operations on many graphs.
2"""
3from itertools import chain, repeat
5import networkx as nx
7__all__ = ["union_all", "compose_all", "disjoint_union_all", "intersection_all"]
10@nx._dispatch(graphs="[graphs]", preserve_all_attrs=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.",
96 "Use appropriate rename"
97 "=(G1prefix,G2prefix,...,GNprefix)"
98 "or use disjoint_union(G1,G2,...,GN).",
99 )
101 seen_nodes |= G_nodes_set
102 R.graph.update(G.graph)
103 R.add_nodes_from(G.nodes(data=True))
104 R.add_edges_from(
105 G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
106 )
108 if R is None:
109 raise ValueError("cannot apply union_all to an empty list")
111 return R
114@nx._dispatch(graphs="[graphs]", preserve_all_attrs=True)
115def disjoint_union_all(graphs):
116 """Returns the disjoint union of all graphs.
118 This operation forces distinct integer node labels starting with 0
119 for the first graph in the list and numbering consecutively.
121 Parameters
122 ----------
123 graphs : iterable
124 Iterable of NetworkX graphs
126 Returns
127 -------
128 U : A graph with the same type as the first graph in list
130 Raises
131 ------
132 ValueError
133 If `graphs` is an empty list.
135 NetworkXError
136 In case of mixed type graphs, like MultiGraph and Graph, or directed and undirected graphs.
138 Examples
139 --------
140 >>> G1 = nx.Graph([(1, 2), (2, 3)])
141 >>> G2 = nx.Graph([(4, 5), (5, 6)])
142 >>> U = nx.disjoint_union_all([G1, G2])
143 >>> list(U.nodes())
144 [0, 1, 2, 3, 4, 5]
145 >>> list(U.edges())
146 [(0, 1), (1, 2), (3, 4), (4, 5)]
148 Notes
149 -----
150 For operating on mixed type graphs, they should be converted to the same type.
152 Graph, edge, and node attributes are propagated to the union graph.
153 If a graph attribute is present in multiple graphs, then the value
154 from the last graph in the list with that attribute is used.
155 """
157 def yield_relabeled(graphs):
158 first_label = 0
159 for G in graphs:
160 yield nx.convert_node_labels_to_integers(G, first_label=first_label)
161 first_label += len(G)
163 R = union_all(yield_relabeled(graphs))
165 return R
168@nx._dispatch(graphs="[graphs]", preserve_all_attrs=True)
169def compose_all(graphs):
170 """Returns the composition of all graphs.
172 Composition is the simple union of the node sets and edge sets.
173 The node sets of the supplied graphs need not be disjoint.
175 Parameters
176 ----------
177 graphs : iterable
178 Iterable of NetworkX graphs
180 Returns
181 -------
182 C : A graph with the same type as the first graph in list
184 Raises
185 ------
186 ValueError
187 If `graphs` is an empty list.
189 NetworkXError
190 In case of mixed type graphs, like MultiGraph and Graph, or directed and undirected graphs.
192 Examples
193 --------
194 >>> G1 = nx.Graph([(1, 2), (2, 3)])
195 >>> G2 = nx.Graph([(3, 4), (5, 6)])
196 >>> C = nx.compose_all([G1, G2])
197 >>> list(C.nodes())
198 [1, 2, 3, 4, 5, 6]
199 >>> list(C.edges())
200 [(1, 2), (2, 3), (3, 4), (5, 6)]
202 Notes
203 -----
204 For operating on mixed type graphs, they should be converted to the same type.
206 Graph, edge, and node attributes are propagated to the union graph.
207 If a graph attribute is present in multiple graphs, then the value
208 from the last graph in the list with that attribute is used.
209 """
210 R = None
212 # add graph attributes, H attributes take precedent over G attributes
213 for i, G in enumerate(graphs):
214 if i == 0:
215 # create new graph
216 R = G.__class__()
217 elif G.is_directed() != R.is_directed():
218 raise nx.NetworkXError("All graphs must be directed or undirected.")
219 elif G.is_multigraph() != R.is_multigraph():
220 raise nx.NetworkXError("All graphs must be graphs or multigraphs.")
222 R.graph.update(G.graph)
223 R.add_nodes_from(G.nodes(data=True))
224 R.add_edges_from(
225 G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
226 )
228 if R is None:
229 raise ValueError("cannot apply compose_all to an empty list")
231 return R
234@nx._dispatch(graphs="[graphs]")
235def intersection_all(graphs):
236 """Returns a new graph that contains only the nodes and the edges that exist in
237 all graphs.
239 Parameters
240 ----------
241 graphs : iterable
242 Iterable of NetworkX graphs
244 Returns
245 -------
246 R : A new graph with the same type as the first graph in list
248 Raises
249 ------
250 ValueError
251 If `graphs` is an empty list.
253 NetworkXError
254 In case of mixed type graphs, like MultiGraph and Graph, or directed and undirected graphs.
256 Notes
257 -----
258 For operating on mixed type graphs, they should be converted to the same type.
260 Attributes from the graph, nodes, and edges are not copied to the new
261 graph.
263 The resulting graph can be updated with attributes if desired. For example, code which adds the minimum attribute for each node across all graphs could work.
264 >>> g = nx.Graph()
265 >>> g.add_node(0, capacity=4)
266 >>> g.add_node(1, capacity=3)
267 >>> g.add_edge(0, 1)
269 >>> h = g.copy()
270 >>> h.nodes[0]["capacity"] = 2
272 >>> gh = nx.intersection_all([g, h])
274 >>> new_node_attr = {n: min(*(anyG.nodes[n].get('capacity', float('inf')) for anyG in [g, h])) for n in gh}
275 >>> nx.set_node_attributes(gh, new_node_attr, 'new_capacity')
276 >>> gh.nodes(data=True)
277 NodeDataView({0: {'new_capacity': 2}, 1: {'new_capacity': 3}})
279 Examples
280 --------
281 >>> G1 = nx.Graph([(1, 2), (2, 3)])
282 >>> G2 = nx.Graph([(2, 3), (3, 4)])
283 >>> R = nx.intersection_all([G1, G2])
284 >>> list(R.nodes())
285 [2, 3]
286 >>> list(R.edges())
287 [(2, 3)]
289 """
290 R = None
292 for i, G in enumerate(graphs):
293 G_nodes_set = set(G.nodes)
294 G_edges_set = set(G.edges)
295 if not G.is_directed():
296 if G.is_multigraph():
297 G_edges_set.update((v, u, k) for u, v, k in list(G_edges_set))
298 else:
299 G_edges_set.update((v, u) for u, v in list(G_edges_set))
300 if i == 0:
301 # create new graph
302 R = G.__class__()
303 node_intersection = G_nodes_set
304 edge_intersection = G_edges_set
305 elif G.is_directed() != R.is_directed():
306 raise nx.NetworkXError("All graphs must be directed or undirected.")
307 elif G.is_multigraph() != R.is_multigraph():
308 raise nx.NetworkXError("All graphs must be graphs or multigraphs.")
309 else:
310 node_intersection &= G_nodes_set
311 edge_intersection &= G_edges_set
313 if R is None:
314 raise ValueError("cannot apply intersection_all to an empty list")
316 R.add_nodes_from(node_intersection)
317 R.add_edges_from(edge_intersection)
319 return R