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"""
2Graph products.
3"""
5from itertools import product
7import networkx as nx
8from networkx.utils import not_implemented_for
10__all__ = [
11 "tensor_product",
12 "cartesian_product",
13 "lexicographic_product",
14 "strong_product",
15 "power",
16 "rooted_product",
17 "corona_product",
18 "modular_product",
19]
20_G_H = {"G": 0, "H": 1}
23def _dict_product(d1, d2):
24 return {k: (d1.get(k), d2.get(k)) for k in set(d1) | set(d2)}
27# Generators for producing graph products
28def _node_product(G, H):
29 for u, v in product(G, H):
30 yield ((u, v), _dict_product(G.nodes[u], H.nodes[v]))
33def _directed_edges_cross_edges(G, H):
34 if not G.is_multigraph() and not H.is_multigraph():
35 for u, v, c in G.edges(data=True):
36 for x, y, d in H.edges(data=True):
37 yield (u, x), (v, y), _dict_product(c, d)
38 if not G.is_multigraph() and H.is_multigraph():
39 for u, v, c in G.edges(data=True):
40 for x, y, k, d in H.edges(data=True, keys=True):
41 yield (u, x), (v, y), k, _dict_product(c, d)
42 if G.is_multigraph() and not H.is_multigraph():
43 for u, v, k, c in G.edges(data=True, keys=True):
44 for x, y, d in H.edges(data=True):
45 yield (u, x), (v, y), k, _dict_product(c, d)
46 if G.is_multigraph() and H.is_multigraph():
47 for u, v, j, c in G.edges(data=True, keys=True):
48 for x, y, k, d in H.edges(data=True, keys=True):
49 yield (u, x), (v, y), (j, k), _dict_product(c, d)
52def _undirected_edges_cross_edges(G, H):
53 if not G.is_multigraph() and not H.is_multigraph():
54 for u, v, c in G.edges(data=True):
55 for x, y, d in H.edges(data=True):
56 yield (v, x), (u, y), _dict_product(c, d)
57 if not G.is_multigraph() and H.is_multigraph():
58 for u, v, c in G.edges(data=True):
59 for x, y, k, d in H.edges(data=True, keys=True):
60 yield (v, x), (u, y), k, _dict_product(c, d)
61 if G.is_multigraph() and not H.is_multigraph():
62 for u, v, k, c in G.edges(data=True, keys=True):
63 for x, y, d in H.edges(data=True):
64 yield (v, x), (u, y), k, _dict_product(c, d)
65 if G.is_multigraph() and H.is_multigraph():
66 for u, v, j, c in G.edges(data=True, keys=True):
67 for x, y, k, d in H.edges(data=True, keys=True):
68 yield (v, x), (u, y), (j, k), _dict_product(c, d)
71def _edges_cross_nodes(G, H):
72 if G.is_multigraph():
73 for u, v, k, d in G.edges(data=True, keys=True):
74 for x in H:
75 yield (u, x), (v, x), k, d
76 else:
77 for u, v, d in G.edges(data=True):
78 for x in H:
79 if H.is_multigraph():
80 yield (u, x), (v, x), None, d
81 else:
82 yield (u, x), (v, x), d
85def _nodes_cross_edges(G, H):
86 if H.is_multigraph():
87 for x in G:
88 for u, v, k, d in H.edges(data=True, keys=True):
89 yield (x, u), (x, v), k, d
90 else:
91 for x in G:
92 for u, v, d in H.edges(data=True):
93 if G.is_multigraph():
94 yield (x, u), (x, v), None, d
95 else:
96 yield (x, u), (x, v), d
99def _edges_cross_nodes_and_nodes(G, H):
100 if G.is_multigraph():
101 for u, v, k, d in G.edges(data=True, keys=True):
102 for x in H:
103 for y in H:
104 yield (u, x), (v, y), k, d
105 else:
106 for u, v, d in G.edges(data=True):
107 for x in H:
108 for y in H:
109 if H.is_multigraph():
110 yield (u, x), (v, y), None, d
111 else:
112 yield (u, x), (v, y), d
115def _init_product_graph(G, H):
116 if G.is_directed() != H.is_directed():
117 msg = "G and H must be both directed or both undirected"
118 raise nx.NetworkXError(msg)
119 if G.is_multigraph() or H.is_multigraph():
120 GH = nx.MultiGraph()
121 else:
122 GH = nx.Graph()
123 if G.is_directed():
124 GH = GH.to_directed()
125 return GH
128@nx._dispatchable(graphs=_G_H, preserve_node_attrs=True, returns_graph=True)
129def tensor_product(G, H):
130 r"""Returns the tensor product of G and H.
132 The tensor product $P$ of the graphs $G$ and $H$ has a node set that
133 is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.
134 $P$ has an edge $((u,v), (x,y))$ if and only if $(u,x)$ is an edge in $G$
135 and $(v,y)$ is an edge in $H$.
137 Tensor product is sometimes also referred to as the categorical product,
138 direct product, cardinal product or conjunction.
141 Parameters
142 ----------
143 G, H: graphs
144 Networkx graphs.
146 Returns
147 -------
148 P: NetworkX graph
149 The tensor product of G and H. P will be a multi-graph if either G
150 or H is a multi-graph, will be a directed if G and H are directed,
151 and undirected if G and H are undirected.
153 Raises
154 ------
155 NetworkXError
156 If G and H are not both directed or both undirected.
158 Notes
159 -----
160 Node attributes in P are two-tuple of the G and H node attributes.
161 Missing attributes are assigned None.
163 Examples
164 --------
165 >>> G = nx.Graph()
166 >>> H = nx.Graph()
167 >>> G.add_node(0, a1=True)
168 >>> H.add_node("a", a2="Spam")
169 >>> P = nx.tensor_product(G, H)
170 >>> list(P)
171 [(0, 'a')]
173 Edge attributes and edge keys (for multigraphs) are also copied to the
174 new product graph
175 """
176 GH = _init_product_graph(G, H)
177 GH.add_nodes_from(_node_product(G, H))
178 GH.add_edges_from(_directed_edges_cross_edges(G, H))
179 if not GH.is_directed():
180 GH.add_edges_from(_undirected_edges_cross_edges(G, H))
181 return GH
184@nx._dispatchable(graphs=_G_H, preserve_node_attrs=True, returns_graph=True)
185def cartesian_product(G, H):
186 r"""Returns the Cartesian product of G and H.
188 The Cartesian product $P$ of the graphs $G$ and $H$ has a node set that
189 is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.
190 $P$ has an edge $((u,v),(x,y))$ if and only if either $u$ is equal to $x$
191 and both $v$ and $y$ are adjacent in $H$ or if $v$ is equal to $y$ and
192 both $u$ and $x$ are adjacent in $G$.
194 Parameters
195 ----------
196 G, H: graphs
197 Networkx graphs.
199 Returns
200 -------
201 P: NetworkX graph
202 The Cartesian product of G and H. P will be a multi-graph if either G
203 or H is a multi-graph. Will be a directed if G and H are directed,
204 and undirected if G and H are undirected.
206 Raises
207 ------
208 NetworkXError
209 If G and H are not both directed or both undirected.
211 Notes
212 -----
213 Node attributes in P are two-tuple of the G and H node attributes.
214 Missing attributes are assigned None.
216 Examples
217 --------
218 >>> G = nx.Graph()
219 >>> H = nx.Graph()
220 >>> G.add_node(0, a1=True)
221 >>> H.add_node("a", a2="Spam")
222 >>> P = nx.cartesian_product(G, H)
223 >>> list(P)
224 [(0, 'a')]
226 Edge attributes and edge keys (for multigraphs) are also copied to the
227 new product graph
228 """
229 GH = _init_product_graph(G, H)
230 GH.add_nodes_from(_node_product(G, H))
231 GH.add_edges_from(_edges_cross_nodes(G, H))
232 GH.add_edges_from(_nodes_cross_edges(G, H))
233 return GH
236@nx._dispatchable(graphs=_G_H, preserve_node_attrs=True, returns_graph=True)
237def lexicographic_product(G, H):
238 r"""Returns the lexicographic product of G and H.
240 The lexicographical product $P$ of the graphs $G$ and $H$ has a node set
241 that is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.
242 $P$ has an edge $((u,v), (x,y))$ if and only if $(u,v)$ is an edge in $G$
243 or $u==v$ and $(x,y)$ is an edge in $H$.
245 Parameters
246 ----------
247 G, H: graphs
248 Networkx graphs.
250 Returns
251 -------
252 P: NetworkX graph
253 The Cartesian product of G and H. P will be a multi-graph if either G
254 or H is a multi-graph. Will be a directed if G and H are directed,
255 and undirected if G and H are undirected.
257 Raises
258 ------
259 NetworkXError
260 If G and H are not both directed or both undirected.
262 Notes
263 -----
264 Node attributes in P are two-tuple of the G and H node attributes.
265 Missing attributes are assigned None.
267 Examples
268 --------
269 >>> G = nx.Graph()
270 >>> H = nx.Graph()
271 >>> G.add_node(0, a1=True)
272 >>> H.add_node("a", a2="Spam")
273 >>> P = nx.lexicographic_product(G, H)
274 >>> list(P)
275 [(0, 'a')]
277 Edge attributes and edge keys (for multigraphs) are also copied to the
278 new product graph
279 """
280 GH = _init_product_graph(G, H)
281 GH.add_nodes_from(_node_product(G, H))
282 # Edges in G regardless of H designation
283 GH.add_edges_from(_edges_cross_nodes_and_nodes(G, H))
284 # For each x in G, only if there is an edge in H
285 GH.add_edges_from(_nodes_cross_edges(G, H))
286 return GH
289@nx._dispatchable(graphs=_G_H, preserve_node_attrs=True, returns_graph=True)
290def strong_product(G, H):
291 r"""Returns the strong product of G and H.
293 The strong product $P$ of the graphs $G$ and $H$ has a node set that
294 is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.
295 $P$ has an edge $((u,x), (v,y))$ if any of the following conditions
296 are met:
298 - $u=v$ and $(x,y)$ is an edge in $H$
299 - $x=y$ and $(u,v)$ is an edge in $G$
300 - $(u,v)$ is an edge in $G$ and $(x,y)$ is an edge in $H$
302 Parameters
303 ----------
304 G, H: graphs
305 Networkx graphs.
307 Returns
308 -------
309 P: NetworkX graph
310 The Cartesian product of G and H. P will be a multi-graph if either G
311 or H is a multi-graph. Will be a directed if G and H are directed,
312 and undirected if G and H are undirected.
314 Raises
315 ------
316 NetworkXError
317 If G and H are not both directed or both undirected.
319 Notes
320 -----
321 Node attributes in P are two-tuple of the G and H node attributes.
322 Missing attributes are assigned None.
324 Examples
325 --------
326 >>> G = nx.Graph()
327 >>> H = nx.Graph()
328 >>> G.add_node(0, a1=True)
329 >>> H.add_node("a", a2="Spam")
330 >>> P = nx.strong_product(G, H)
331 >>> list(P)
332 [(0, 'a')]
334 Edge attributes and edge keys (for multigraphs) are also copied to the
335 new product graph
336 """
337 GH = _init_product_graph(G, H)
338 GH.add_nodes_from(_node_product(G, H))
339 GH.add_edges_from(_nodes_cross_edges(G, H))
340 GH.add_edges_from(_edges_cross_nodes(G, H))
341 GH.add_edges_from(_directed_edges_cross_edges(G, H))
342 if not GH.is_directed():
343 GH.add_edges_from(_undirected_edges_cross_edges(G, H))
344 return GH
347@not_implemented_for("directed")
348@not_implemented_for("multigraph")
349@nx._dispatchable(returns_graph=True)
350def power(G, k):
351 """Returns the specified power of a graph.
353 The $k$th power of a simple graph $G$, denoted $G^k$, is a
354 graph on the same set of nodes in which two distinct nodes $u$ and
355 $v$ are adjacent in $G^k$ if and only if the shortest path
356 distance between $u$ and $v$ in $G$ is at most $k$.
358 Parameters
359 ----------
360 G : graph
361 A NetworkX simple graph object.
363 k : positive integer
364 The power to which to raise the graph `G`.
366 Returns
367 -------
368 NetworkX simple graph
369 `G` to the power `k`.
371 Raises
372 ------
373 ValueError
374 If the exponent `k` is not positive.
376 NetworkXNotImplemented
377 If `G` is not a simple graph.
379 Examples
380 --------
381 The number of edges will never decrease when taking successive
382 powers:
384 >>> G = nx.path_graph(4)
385 >>> list(nx.power(G, 2).edges)
386 [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
387 >>> list(nx.power(G, 3).edges)
388 [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
390 The `k` th power of a cycle graph on *n* nodes is the complete graph
391 on *n* nodes, if `k` is at least ``n // 2``:
393 >>> G = nx.cycle_graph(5)
394 >>> H = nx.complete_graph(5)
395 >>> nx.is_isomorphic(nx.power(G, 2), H)
396 True
397 >>> G = nx.cycle_graph(8)
398 >>> H = nx.complete_graph(8)
399 >>> nx.is_isomorphic(nx.power(G, 4), H)
400 True
402 References
403 ----------
404 .. [1] J. A. Bondy, U. S. R. Murty, *Graph Theory*. Springer, 2008.
406 Notes
407 -----
408 This definition of "power graph" comes from Exercise 3.1.6 of
409 *Graph Theory* by Bondy and Murty [1]_.
411 """
412 if k <= 0:
413 raise ValueError("k must be a positive integer")
414 H = nx.Graph()
415 H.add_nodes_from(G)
416 # update BFS code to ignore self loops.
417 for n in G:
418 seen = {} # level (number of hops) when seen in BFS
419 level = 1 # the current level
420 nextlevel = G[n]
421 while nextlevel:
422 thislevel = nextlevel # advance to next level
423 nextlevel = {} # and start a new list (fringe)
424 for v in thislevel:
425 if v == n: # avoid self loop
426 continue
427 if v not in seen:
428 seen[v] = level # set the level of vertex v
429 nextlevel.update(G[v]) # add neighbors of v
430 if k <= level:
431 break
432 level += 1
433 H.add_edges_from((n, nbr) for nbr in seen)
434 return H
437@not_implemented_for("multigraph")
438@nx._dispatchable(graphs=_G_H, returns_graph=True)
439def rooted_product(G, H, root):
440 """Return the rooted product of graphs G and H rooted at root in H.
442 A new graph is constructed representing the rooted product of
443 the inputted graphs, G and H, with a root in H.
444 A rooted product duplicates H for each nodes in G with the root
445 of H corresponding to the node in G. Nodes are renamed as the direct
446 product of G and H. The result is a subgraph of the cartesian product.
448 Parameters
449 ----------
450 G,H : graph
451 A NetworkX graph
452 root : node
453 A node in H
455 Returns
456 -------
457 R : The rooted product of G and H with a specified root in H
459 Notes
460 -----
461 The nodes of R are the Cartesian Product of the nodes of G and H.
462 The nodes of G and H are not relabeled.
463 """
464 if root not in H:
465 raise nx.NodeNotFound("root must be a vertex in H")
467 R = nx.Graph()
468 R.add_nodes_from(product(G, H))
470 R.add_edges_from(((e[0], root), (e[1], root)) for e in G.edges())
471 R.add_edges_from(((g, e[0]), (g, e[1])) for g in G for e in H.edges())
473 return R
476@not_implemented_for("directed")
477@not_implemented_for("multigraph")
478@nx._dispatchable(graphs=_G_H, returns_graph=True)
479def corona_product(G, H):
480 r"""Returns the Corona product of G and H.
482 The corona product of $G$ and $H$ is the graph $C = G \circ H$ obtained by
483 taking one copy of $G$, called the center graph, $|V(G)|$ copies of $H$,
484 called the outer graph, and making the $i$-th vertex of $G$ adjacent to
485 every vertex of the $i$-th copy of $H$, where $1 ≤ i ≤ |V(G)|$.
487 Parameters
488 ----------
489 G, H: NetworkX graphs
490 The graphs to take the carona product of.
491 `G` is the center graph and `H` is the outer graph
493 Returns
494 -------
495 C: NetworkX graph
496 The Corona product of G and H.
498 Raises
499 ------
500 NetworkXError
501 If G and H are not both directed or both undirected.
503 Examples
504 --------
505 >>> G = nx.cycle_graph(4)
506 >>> H = nx.path_graph(2)
507 >>> C = nx.corona_product(G, H)
508 >>> list(C)
509 [0, 1, 2, 3, (0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)]
510 >>> print(C)
511 Graph with 12 nodes and 16 edges
513 References
514 ----------
515 [1] M. Tavakoli, F. Rahbarnia, and A. R. Ashrafi,
516 "Studying the corona product of graphs under some graph invariants,"
517 Transactions on Combinatorics, vol. 3, no. 3, pp. 43–49, Sep. 2014,
518 doi: 10.22108/toc.2014.5542.
519 [2] A. Faraji, "Corona Product in Graph Theory," Ali Faraji, May 11, 2021.
520 https://blog.alifaraji.ir/math/graph-theory/corona-product.html (accessed Dec. 07, 2021).
521 """
522 GH = _init_product_graph(G, H)
523 GH.add_nodes_from(G)
524 GH.add_edges_from(G.edges)
526 for G_node in G:
527 # copy nodes of H in GH, call it H_i
528 GH.add_nodes_from((G_node, v) for v in H)
530 # copy edges of H_i based on H
531 GH.add_edges_from(
532 ((G_node, e0), (G_node, e1), d) for e0, e1, d in H.edges.data()
533 )
535 # creating new edges between H_i and a G's node
536 GH.add_edges_from((G_node, (G_node, H_node)) for H_node in H)
538 return GH
541@nx._dispatchable(
542 graphs=_G_H, preserve_edge_attrs=True, preserve_node_attrs=True, returns_graph=True
543)
544def modular_product(G, H):
545 r"""Returns the Modular product of G and H.
547 The modular product of `G` and `H` is the graph $M = G \nabla H$,
548 consisting of the node set $V(M) = V(G) \times V(H)$ that is the Cartesian
549 product of the node sets of `G` and `H`. Further, M contains an edge ((u, v), (x, y)):
551 - if u is adjacent to x in `G` and v is adjacent to y in `H`, or
552 - if u is not adjacent to x in `G` and v is not adjacent to y in `H`.
554 More formally::
556 E(M) = {((u, v), (x, y)) | ((u, x) in E(G) and (v, y) in E(H)) or
557 ((u, x) not in E(G) and (v, y) not in E(H))}
559 Parameters
560 ----------
561 G, H: NetworkX graphs
562 The graphs to take the modular product of.
564 Returns
565 -------
566 M: NetworkX graph
567 The Modular product of `G` and `H`.
569 Raises
570 ------
571 NetworkXNotImplemented
572 If `G` is not a simple graph.
574 Examples
575 --------
576 >>> G = nx.cycle_graph(4)
577 >>> H = nx.path_graph(2)
578 >>> M = nx.modular_product(G, H)
579 >>> list(M)
580 [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)]
581 >>> print(M)
582 Graph with 8 nodes and 8 edges
584 Notes
585 -----
586 The *modular product* is defined in [1]_ and was first
587 introduced as the *weak modular product*.
589 The modular product reduces the problem of counting isomorphic subgraphs
590 in `G` and `H` to the problem of counting cliques in M. The subgraphs of
591 `G` and `H` that are induced by the nodes of a clique in M are
592 isomorphic [2]_ [3]_.
594 References
595 ----------
596 .. [1] R. Hammack, W. Imrich, and S. Klavžar,
597 "Handbook of Product Graphs", CRC Press, 2011.
599 .. [2] H. G. Barrow and R. M. Burstall,
600 "Subgraph isomorphism, matching relational structures and maximal
601 cliques", Information Processing Letters, vol. 4, issue 4, pp. 83-84,
602 1976, https://doi.org/10.1016/0020-0190(76)90049-1.
604 .. [3] V. G. Vizing, "Reduction of the problem of isomorphism and isomorphic
605 entrance to the task of finding the nondensity of a graph." Proc. Third
606 All-Union Conference on Problems of Theoretical Cybernetics. 1974.
607 """
608 if G.is_directed() or H.is_directed():
609 raise nx.NetworkXNotImplemented(
610 "Modular product not implemented for directed graphs"
611 )
612 if G.is_multigraph() or H.is_multigraph():
613 raise nx.NetworkXNotImplemented(
614 "Modular product not implemented for multigraphs"
615 )
617 GH = _init_product_graph(G, H)
618 GH.add_nodes_from(_node_product(G, H))
620 for u, v, c in G.edges(data=True):
621 for x, y, d in H.edges(data=True):
622 GH.add_edge((u, x), (v, y), **_dict_product(c, d))
623 GH.add_edge((v, x), (u, y), **_dict_product(c, d))
625 G = nx.complement(G)
626 H = nx.complement(H)
628 for u, v, c in G.edges(data=True):
629 for x, y, d in H.edges(data=True):
630 GH.add_edge((u, x), (v, y), **_dict_product(c, d))
631 GH.add_edge((v, x), (u, y), **_dict_product(c, d))
633 return GH