Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/operators/product.py: 19%
166 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Graph products.
3"""
4from itertools import product
6import networkx as nx
7from networkx.utils import not_implemented_for
9__all__ = [
10 "tensor_product",
11 "cartesian_product",
12 "lexicographic_product",
13 "strong_product",
14 "power",
15 "rooted_product",
16 "corona_product",
17]
18_G_H = {"G": 0, "H": 1}
21def _dict_product(d1, d2):
22 return {k: (d1.get(k), d2.get(k)) for k in set(d1) | set(d2)}
25# Generators for producing graph products
26def _node_product(G, H):
27 for u, v in product(G, H):
28 yield ((u, v), _dict_product(G.nodes[u], H.nodes[v]))
31def _directed_edges_cross_edges(G, H):
32 if not G.is_multigraph() and not H.is_multigraph():
33 for u, v, c in G.edges(data=True):
34 for x, y, d in H.edges(data=True):
35 yield (u, x), (v, y), _dict_product(c, d)
36 if not G.is_multigraph() and H.is_multigraph():
37 for u, v, c in G.edges(data=True):
38 for x, y, k, d in H.edges(data=True, keys=True):
39 yield (u, x), (v, y), k, _dict_product(c, d)
40 if G.is_multigraph() and not H.is_multigraph():
41 for u, v, k, c in G.edges(data=True, keys=True):
42 for x, y, d in H.edges(data=True):
43 yield (u, x), (v, y), k, _dict_product(c, d)
44 if G.is_multigraph() and H.is_multigraph():
45 for u, v, j, c in G.edges(data=True, keys=True):
46 for x, y, k, d in H.edges(data=True, keys=True):
47 yield (u, x), (v, y), (j, k), _dict_product(c, d)
50def _undirected_edges_cross_edges(G, H):
51 if not G.is_multigraph() and not H.is_multigraph():
52 for u, v, c in G.edges(data=True):
53 for x, y, d in H.edges(data=True):
54 yield (v, x), (u, y), _dict_product(c, d)
55 if not G.is_multigraph() and H.is_multigraph():
56 for u, v, c in G.edges(data=True):
57 for x, y, k, d in H.edges(data=True, keys=True):
58 yield (v, x), (u, y), k, _dict_product(c, d)
59 if G.is_multigraph() and not H.is_multigraph():
60 for u, v, k, c in G.edges(data=True, keys=True):
61 for x, y, d in H.edges(data=True):
62 yield (v, x), (u, y), k, _dict_product(c, d)
63 if G.is_multigraph() and H.is_multigraph():
64 for u, v, j, c in G.edges(data=True, keys=True):
65 for x, y, k, d in H.edges(data=True, keys=True):
66 yield (v, x), (u, y), (j, k), _dict_product(c, d)
69def _edges_cross_nodes(G, H):
70 if G.is_multigraph():
71 for u, v, k, d in G.edges(data=True, keys=True):
72 for x in H:
73 yield (u, x), (v, x), k, d
74 else:
75 for u, v, d in G.edges(data=True):
76 for x in H:
77 if H.is_multigraph():
78 yield (u, x), (v, x), None, d
79 else:
80 yield (u, x), (v, x), d
83def _nodes_cross_edges(G, H):
84 if H.is_multigraph():
85 for x in G:
86 for u, v, k, d in H.edges(data=True, keys=True):
87 yield (x, u), (x, v), k, d
88 else:
89 for x in G:
90 for u, v, d in H.edges(data=True):
91 if G.is_multigraph():
92 yield (x, u), (x, v), None, d
93 else:
94 yield (x, u), (x, v), d
97def _edges_cross_nodes_and_nodes(G, H):
98 if G.is_multigraph():
99 for u, v, k, d in G.edges(data=True, keys=True):
100 for x in H:
101 for y in H:
102 yield (u, x), (v, y), k, d
103 else:
104 for u, v, d in G.edges(data=True):
105 for x in H:
106 for y in H:
107 if H.is_multigraph():
108 yield (u, x), (v, y), None, d
109 else:
110 yield (u, x), (v, y), d
113def _init_product_graph(G, H):
114 if G.is_directed() != H.is_directed():
115 msg = "G and H must be both directed or both undirected"
116 raise nx.NetworkXError(msg)
117 if G.is_multigraph() or H.is_multigraph():
118 GH = nx.MultiGraph()
119 else:
120 GH = nx.Graph()
121 if G.is_directed():
122 GH = GH.to_directed()
123 return GH
126@nx._dispatch(graphs=_G_H)
127def tensor_product(G, H):
128 r"""Returns the tensor product of G and H.
130 The tensor product $P$ of the graphs $G$ and $H$ has a node set that
131 is the tensor product of the node sets, $V(P)=V(G) \times V(H)$.
132 $P$ has an edge $((u,v), (x,y))$ if and only if $(u,x)$ is an edge in $G$
133 and $(v,y)$ is an edge in $H$.
135 Tensor product is sometimes also referred to as the categorical product,
136 direct product, cardinal product or conjunction.
139 Parameters
140 ----------
141 G, H: graphs
142 Networkx graphs.
144 Returns
145 -------
146 P: NetworkX graph
147 The tensor product of G and H. P will be a multi-graph if either G
148 or H is a multi-graph, will be a directed if G and H are directed,
149 and undirected if G and H are undirected.
151 Raises
152 ------
153 NetworkXError
154 If G and H are not both directed or both undirected.
156 Notes
157 -----
158 Node attributes in P are two-tuple of the G and H node attributes.
159 Missing attributes are assigned None.
161 Examples
162 --------
163 >>> G = nx.Graph()
164 >>> H = nx.Graph()
165 >>> G.add_node(0, a1=True)
166 >>> H.add_node("a", a2="Spam")
167 >>> P = nx.tensor_product(G, H)
168 >>> list(P)
169 [(0, 'a')]
171 Edge attributes and edge keys (for multigraphs) are also copied to the
172 new product graph
173 """
174 GH = _init_product_graph(G, H)
175 GH.add_nodes_from(_node_product(G, H))
176 GH.add_edges_from(_directed_edges_cross_edges(G, H))
177 if not GH.is_directed():
178 GH.add_edges_from(_undirected_edges_cross_edges(G, H))
179 return GH
182@nx._dispatch(graphs=_G_H)
183def cartesian_product(G, H):
184 r"""Returns the Cartesian product of G and H.
186 The Cartesian product $P$ of the graphs $G$ and $H$ has a node set that
187 is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.
188 $P$ has an edge $((u,v),(x,y))$ if and only if either $u$ is equal to $x$
189 and both $v$ and $y$ are adjacent in $H$ or if $v$ is equal to $y$ and
190 both $u$ and $x$ are adjacent in $G$.
192 Parameters
193 ----------
194 G, H: graphs
195 Networkx graphs.
197 Returns
198 -------
199 P: NetworkX graph
200 The Cartesian product of G and H. P will be a multi-graph if either G
201 or H is a multi-graph. Will be a directed if G and H are directed,
202 and undirected if G and H are undirected.
204 Raises
205 ------
206 NetworkXError
207 If G and H are not both directed or both undirected.
209 Notes
210 -----
211 Node attributes in P are two-tuple of the G and H node attributes.
212 Missing attributes are assigned None.
214 Examples
215 --------
216 >>> G = nx.Graph()
217 >>> H = nx.Graph()
218 >>> G.add_node(0, a1=True)
219 >>> H.add_node("a", a2="Spam")
220 >>> P = nx.cartesian_product(G, H)
221 >>> list(P)
222 [(0, 'a')]
224 Edge attributes and edge keys (for multigraphs) are also copied to the
225 new product graph
226 """
227 GH = _init_product_graph(G, H)
228 GH.add_nodes_from(_node_product(G, H))
229 GH.add_edges_from(_edges_cross_nodes(G, H))
230 GH.add_edges_from(_nodes_cross_edges(G, H))
231 return GH
234@nx._dispatch(graphs=_G_H)
235def lexicographic_product(G, H):
236 r"""Returns the lexicographic product of G and H.
238 The lexicographical product $P$ of the graphs $G$ and $H$ has a node set
239 that is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.
240 $P$ has an edge $((u,v), (x,y))$ if and only if $(u,v)$ is an edge in $G$
241 or $u==v$ and $(x,y)$ is an edge in $H$.
243 Parameters
244 ----------
245 G, H: graphs
246 Networkx graphs.
248 Returns
249 -------
250 P: NetworkX graph
251 The Cartesian product of G and H. P will be a multi-graph if either G
252 or H is a multi-graph. Will be a directed if G and H are directed,
253 and undirected if G and H are undirected.
255 Raises
256 ------
257 NetworkXError
258 If G and H are not both directed or both undirected.
260 Notes
261 -----
262 Node attributes in P are two-tuple of the G and H node attributes.
263 Missing attributes are assigned None.
265 Examples
266 --------
267 >>> G = nx.Graph()
268 >>> H = nx.Graph()
269 >>> G.add_node(0, a1=True)
270 >>> H.add_node("a", a2="Spam")
271 >>> P = nx.lexicographic_product(G, H)
272 >>> list(P)
273 [(0, 'a')]
275 Edge attributes and edge keys (for multigraphs) are also copied to the
276 new product graph
277 """
278 GH = _init_product_graph(G, H)
279 GH.add_nodes_from(_node_product(G, H))
280 # Edges in G regardless of H designation
281 GH.add_edges_from(_edges_cross_nodes_and_nodes(G, H))
282 # For each x in G, only if there is an edge in H
283 GH.add_edges_from(_nodes_cross_edges(G, H))
284 return GH
287@nx._dispatch(graphs=_G_H)
288def strong_product(G, H):
289 r"""Returns the strong product of G and H.
291 The strong product $P$ of the graphs $G$ and $H$ has a node set that
292 is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.
293 $P$ has an edge $((u,v), (x,y))$ if and only if
294 $u==v$ and $(x,y)$ is an edge in $H$, or
295 $x==y$ and $(u,v)$ is an edge in $G$, or
296 $(u,v)$ is an edge in $G$ and $(x,y)$ is an edge in $H$.
298 Parameters
299 ----------
300 G, H: graphs
301 Networkx graphs.
303 Returns
304 -------
305 P: NetworkX graph
306 The Cartesian product of G and H. P will be a multi-graph if either G
307 or H is a multi-graph. Will be a directed if G and H are directed,
308 and undirected if G and H are undirected.
310 Raises
311 ------
312 NetworkXError
313 If G and H are not both directed or both undirected.
315 Notes
316 -----
317 Node attributes in P are two-tuple of the G and H node attributes.
318 Missing attributes are assigned None.
320 Examples
321 --------
322 >>> G = nx.Graph()
323 >>> H = nx.Graph()
324 >>> G.add_node(0, a1=True)
325 >>> H.add_node("a", a2="Spam")
326 >>> P = nx.strong_product(G, H)
327 >>> list(P)
328 [(0, 'a')]
330 Edge attributes and edge keys (for multigraphs) are also copied to the
331 new product graph
332 """
333 GH = _init_product_graph(G, H)
334 GH.add_nodes_from(_node_product(G, H))
335 GH.add_edges_from(_nodes_cross_edges(G, H))
336 GH.add_edges_from(_edges_cross_nodes(G, H))
337 GH.add_edges_from(_directed_edges_cross_edges(G, H))
338 if not GH.is_directed():
339 GH.add_edges_from(_undirected_edges_cross_edges(G, H))
340 return GH
343@not_implemented_for("directed")
344@not_implemented_for("multigraph")
345@nx._dispatch
346def power(G, k):
347 """Returns the specified power of a graph.
349 The $k$th power of a simple graph $G$, denoted $G^k$, is a
350 graph on the same set of nodes in which two distinct nodes $u$ and
351 $v$ are adjacent in $G^k$ if and only if the shortest path
352 distance between $u$ and $v$ in $G$ is at most $k$.
354 Parameters
355 ----------
356 G : graph
357 A NetworkX simple graph object.
359 k : positive integer
360 The power to which to raise the graph `G`.
362 Returns
363 -------
364 NetworkX simple graph
365 `G` to the power `k`.
367 Raises
368 ------
369 ValueError
370 If the exponent `k` is not positive.
372 NetworkXNotImplemented
373 If `G` is not a simple graph.
375 Examples
376 --------
377 The number of edges will never decrease when taking successive
378 powers:
380 >>> G = nx.path_graph(4)
381 >>> list(nx.power(G, 2).edges)
382 [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
383 >>> list(nx.power(G, 3).edges)
384 [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
386 The `k` th power of a cycle graph on *n* nodes is the complete graph
387 on *n* nodes, if `k` is at least ``n // 2``:
389 >>> G = nx.cycle_graph(5)
390 >>> H = nx.complete_graph(5)
391 >>> nx.is_isomorphic(nx.power(G, 2), H)
392 True
393 >>> G = nx.cycle_graph(8)
394 >>> H = nx.complete_graph(8)
395 >>> nx.is_isomorphic(nx.power(G, 4), H)
396 True
398 References
399 ----------
400 .. [1] J. A. Bondy, U. S. R. Murty, *Graph Theory*. Springer, 2008.
402 Notes
403 -----
404 This definition of "power graph" comes from Exercise 3.1.6 of
405 *Graph Theory* by Bondy and Murty [1]_.
407 """
408 if k <= 0:
409 raise ValueError("k must be a positive integer")
410 H = nx.Graph()
411 H.add_nodes_from(G)
412 # update BFS code to ignore self loops.
413 for n in G:
414 seen = {} # level (number of hops) when seen in BFS
415 level = 1 # the current level
416 nextlevel = G[n]
417 while nextlevel:
418 thislevel = nextlevel # advance to next level
419 nextlevel = {} # and start a new list (fringe)
420 for v in thislevel:
421 if v == n: # avoid self loop
422 continue
423 if v not in seen:
424 seen[v] = level # set the level of vertex v
425 nextlevel.update(G[v]) # add neighbors of v
426 if k <= level:
427 break
428 level += 1
429 H.add_edges_from((n, nbr) for nbr in seen)
430 return H
433@not_implemented_for("multigraph")
434@nx._dispatch(graphs=_G_H)
435def rooted_product(G, H, root):
436 """Return the rooted product of graphs G and H rooted at root in H.
438 A new graph is constructed representing the rooted product of
439 the inputted graphs, G and H, with a root in H.
440 A rooted product duplicates H for each nodes in G with the root
441 of H corresponding to the node in G. Nodes are renamed as the direct
442 product of G and H. The result is a subgraph of the cartesian product.
444 Parameters
445 ----------
446 G,H : graph
447 A NetworkX graph
448 root : node
449 A node in H
451 Returns
452 -------
453 R : The rooted product of G and H with a specified root in H
455 Notes
456 -----
457 The nodes of R are the Cartesian Product of the nodes of G and H.
458 The nodes of G and H are not relabeled.
459 """
460 if root not in H:
461 raise nx.NetworkXError("root must be a vertex in H")
463 R = nx.Graph()
464 R.add_nodes_from(product(G, H))
466 R.add_edges_from(((e[0], root), (e[1], root)) for e in G.edges())
467 R.add_edges_from(((g, e[0]), (g, e[1])) for g in G for e in H.edges())
469 return R
472@not_implemented_for("directed")
473@not_implemented_for("multigraph")
474@nx._dispatch(graphs=_G_H)
475def corona_product(G, H):
476 r"""Returns the Corona product of G and H.
478 The corona product of $G$ and $H$ is the graph $C = G \circ H$ obtained by
479 taking one copy of $G$, called the center graph, $|V(G)|$ copies of $H$,
480 called the outer graph, and making the $i$-th vertex of $G$ adjacent to
481 every vertex of the $i$-th copy of $H$, where $1 ≤ i ≤ |V(G)|$.
483 Parameters
484 ----------
485 G, H: NetworkX graphs
486 The graphs to take the carona product of.
487 `G` is the center graph and `H` is the outer graph
489 Returns
490 -------
491 C: NetworkX graph
492 The Corona product of G and H.
494 Raises
495 ------
496 NetworkXError
497 If G and H are not both directed or both undirected.
499 Examples
500 --------
501 >>> G = nx.cycle_graph(4)
502 >>> H = nx.path_graph(2)
503 >>> C = nx.corona_product(G, H)
504 >>> list(C)
505 [0, 1, 2, 3, (0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)]
506 >>> print(C)
507 Graph with 12 nodes and 16 edges
509 References
510 ----------
511 [1] M. Tavakoli, F. Rahbarnia, and A. R. Ashrafi,
512 "Studying the corona product of graphs under some graph invariants,"
513 Transactions on Combinatorics, vol. 3, no. 3, pp. 43–49, Sep. 2014,
514 doi: 10.22108/toc.2014.5542.
515 [2] A. Faraji, "Corona Product in Graph Theory," Ali Faraji, May 11, 2021.
516 https://blog.alifaraji.ir/math/graph-theory/corona-product.html (accessed Dec. 07, 2021).
517 """
518 GH = _init_product_graph(G, H)
519 GH.add_nodes_from(G)
520 GH.add_edges_from(G.edges)
522 for G_node in G:
523 # copy nodes of H in GH, call it H_i
524 GH.add_nodes_from((G_node, v) for v in H)
526 # copy edges of H_i based on H
527 GH.add_edges_from(
528 ((G_node, e0), (G_node, e1), d) for e0, e1, d in H.edges.data()
529 )
531 # creating new edges between H_i and a G's node
532 GH.add_edges_from((G_node, (G_node, H_node)) for H_node in H)
534 return GH