1"""
2Graph products.
3"""
4from itertools import product
5
6import networkx as nx
7from networkx.utils import not_implemented_for
8
9__all__ = [
10    "tensor_product",
11    "cartesian_product",
12    "lexicographic_product",
13    "strong_product",
14    "power",
15    "rooted_product",
16]
17
18
19def _dict_product(d1, d2):
20    return {k: (d1.get(k), d2.get(k)) for k in set(d1) | set(d2)}
21
22
23# Generators for producting graph products
24def _node_product(G, H):
25    for u, v in product(G, H):
26        yield ((u, v), _dict_product(G.nodes[u], H.nodes[v]))
27
28
29def _directed_edges_cross_edges(G, H):
30    if not G.is_multigraph() and not H.is_multigraph():
31        for u, v, c in G.edges(data=True):
32            for x, y, d in H.edges(data=True):
33                yield (u, x), (v, y), _dict_product(c, d)
34    if not G.is_multigraph() and H.is_multigraph():
35        for u, v, c in G.edges(data=True):
36            for x, y, k, d in H.edges(data=True, keys=True):
37                yield (u, x), (v, y), k, _dict_product(c, d)
38    if G.is_multigraph() and not H.is_multigraph():
39        for u, v, k, c in G.edges(data=True, keys=True):
40            for x, y, d in H.edges(data=True):
41                yield (u, x), (v, y), k, _dict_product(c, d)
42    if G.is_multigraph() and H.is_multigraph():
43        for u, v, j, c in G.edges(data=True, keys=True):
44            for x, y, k, d in H.edges(data=True, keys=True):
45                yield (u, x), (v, y), (j, k), _dict_product(c, d)
46
47
48def _undirected_edges_cross_edges(G, H):
49    if not G.is_multigraph() and not H.is_multigraph():
50        for u, v, c in G.edges(data=True):
51            for x, y, d in H.edges(data=True):
52                yield (v, x), (u, y), _dict_product(c, d)
53    if not G.is_multigraph() and H.is_multigraph():
54        for u, v, c in G.edges(data=True):
55            for x, y, k, d in H.edges(data=True, keys=True):
56                yield (v, x), (u, y), k, _dict_product(c, d)
57    if G.is_multigraph() and not H.is_multigraph():
58        for u, v, k, c in G.edges(data=True, keys=True):
59            for x, y, d in H.edges(data=True):
60                yield (v, x), (u, y), k, _dict_product(c, d)
61    if G.is_multigraph() and H.is_multigraph():
62        for u, v, j, c in G.edges(data=True, keys=True):
63            for x, y, k, d in H.edges(data=True, keys=True):
64                yield (v, x), (u, y), (j, k), _dict_product(c, d)
65
66
67def _edges_cross_nodes(G, H):
68    if G.is_multigraph():
69        for u, v, k, d in G.edges(data=True, keys=True):
70            for x in H:
71                yield (u, x), (v, x), k, d
72    else:
73        for u, v, d in G.edges(data=True):
74            for x in H:
75                if H.is_multigraph():
76                    yield (u, x), (v, x), None, d
77                else:
78                    yield (u, x), (v, x), d
79
80
81def _nodes_cross_edges(G, H):
82    if H.is_multigraph():
83        for x in G:
84            for u, v, k, d in H.edges(data=True, keys=True):
85                yield (x, u), (x, v), k, d
86    else:
87        for x in G:
88            for u, v, d in H.edges(data=True):
89                if G.is_multigraph():
90                    yield (x, u), (x, v), None, d
91                else:
92                    yield (x, u), (x, v), d
93
94
95def _edges_cross_nodes_and_nodes(G, H):
96    if G.is_multigraph():
97        for u, v, k, d in G.edges(data=True, keys=True):
98            for x in H:
99                for y in H:
100                    yield (u, x), (v, y), k, d
101    else:
102        for u, v, d in G.edges(data=True):
103            for x in H:
104                for y in H:
105                    if H.is_multigraph():
106                        yield (u, x), (v, y), None, d
107                    else:
108                        yield (u, x), (v, y), d
109
110
111def _init_product_graph(G, H):
112    if not G.is_directed() == H.is_directed():
113        msg = "G and H must be both directed or both undirected"
114        raise nx.NetworkXError(msg)
115    if G.is_multigraph() or H.is_multigraph():
116        GH = nx.MultiGraph()
117    else:
118        GH = nx.Graph()
119    if G.is_directed():
120        GH = GH.to_directed()
121    return GH
122
123
124def tensor_product(G, H):
125    r"""Returns the tensor product of G and H.
126
127    The tensor product $P$ of the graphs $G$ and $H$ has a node set that
128    is the tensor product of the node sets, $V(P)=V(G) \times V(H)$.
129    $P$ has an edge $((u,v), (x,y))$ if and only if $(u,x)$ is an edge in $G$
130    and $(v,y)$ is an edge in $H$.
131
132    Tensor product is sometimes also referred to as the categorical product,
133    direct product, cardinal product or conjunction.
134
135
136    Parameters
137    ----------
138    G, H: graphs
139     Networkx graphs.
140
141    Returns
142    -------
143    P: NetworkX graph
144     The tensor product of G and H. P will be a multi-graph if either G
145     or H is a multi-graph, will be a directed if G and H are directed,
146     and undirected if G and H are undirected.
147
148    Raises
149    ------
150    NetworkXError
151     If G and H are not both directed or both undirected.
152
153    Notes
154    -----
155    Node attributes in P are two-tuple of the G and H node attributes.
156    Missing attributes are assigned None.
157
158    Examples
159    --------
160    >>> G = nx.Graph()
161    >>> H = nx.Graph()
162    >>> G.add_node(0, a1=True)
163    >>> H.add_node("a", a2="Spam")
164    >>> P = nx.tensor_product(G, H)
165    >>> list(P)
166    [(0, 'a')]
167
168    Edge attributes and edge keys (for multigraphs) are also copied to the
169    new product graph
170    """
171    GH = _init_product_graph(G, H)
172    GH.add_nodes_from(_node_product(G, H))
173    GH.add_edges_from(_directed_edges_cross_edges(G, H))
174    if not GH.is_directed():
175        GH.add_edges_from(_undirected_edges_cross_edges(G, H))
176    return GH
177
178
179def cartesian_product(G, H):
180    r"""Returns the Cartesian product of G and H.
181
182    The Cartesian product $P$ of the graphs $G$ and $H$ has a node set that
183    is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.
184    $P$ has an edge $((u,v),(x,y))$ if and only if either $u$ is equal to $x$
185    and both $v$ and $y$ are adjacent in $H$ or if $v$ is equal to $y$ and
186    both $u$ and $x$ are adjacent in $G$.
187
188    Parameters
189    ----------
190    G, H: graphs
191     Networkx graphs.
192
193    Returns
194    -------
195    P: NetworkX graph
196     The Cartesian product of G and H. P will be a multi-graph if either G
197     or H is a multi-graph. Will be a directed if G and H are directed,
198     and undirected if G and H are undirected.
199
200    Raises
201    ------
202    NetworkXError
203     If G and H are not both directed or both undirected.
204
205    Notes
206    -----
207    Node attributes in P are two-tuple of the G and H node attributes.
208    Missing attributes are assigned None.
209
210    Examples
211    --------
212    >>> G = nx.Graph()
213    >>> H = nx.Graph()
214    >>> G.add_node(0, a1=True)
215    >>> H.add_node("a", a2="Spam")
216    >>> P = nx.cartesian_product(G, H)
217    >>> list(P)
218    [(0, 'a')]
219
220    Edge attributes and edge keys (for multigraphs) are also copied to the
221    new product graph
222    """
223    GH = _init_product_graph(G, H)
224    GH.add_nodes_from(_node_product(G, H))
225    GH.add_edges_from(_edges_cross_nodes(G, H))
226    GH.add_edges_from(_nodes_cross_edges(G, H))
227    return GH
228
229
230def lexicographic_product(G, H):
231    r"""Returns the lexicographic product of G and H.
232
233    The lexicographical product $P$ of the graphs $G$ and $H$ has a node set
234    that is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.
235    $P$ has an edge $((u,v), (x,y))$ if and only if $(u,v)$ is an edge in $G$
236    or $u==v$ and $(x,y)$ is an edge in $H$.
237
238    Parameters
239    ----------
240    G, H: graphs
241     Networkx graphs.
242
243    Returns
244    -------
245    P: NetworkX graph
246     The Cartesian product of G and H. P will be a multi-graph if either G
247     or H is a multi-graph. Will be a directed if G and H are directed,
248     and undirected if G and H are undirected.
249
250    Raises
251    ------
252    NetworkXError
253     If G and H are not both directed or both undirected.
254
255    Notes
256    -----
257    Node attributes in P are two-tuple of the G and H node attributes.
258    Missing attributes are assigned None.
259
260    Examples
261    --------
262    >>> G = nx.Graph()
263    >>> H = nx.Graph()
264    >>> G.add_node(0, a1=True)
265    >>> H.add_node("a", a2="Spam")
266    >>> P = nx.lexicographic_product(G, H)
267    >>> list(P)
268    [(0, 'a')]
269
270    Edge attributes and edge keys (for multigraphs) are also copied to the
271    new product graph
272    """
273    GH = _init_product_graph(G, H)
274    GH.add_nodes_from(_node_product(G, H))
275    # Edges in G regardless of H designation
276    GH.add_edges_from(_edges_cross_nodes_and_nodes(G, H))
277    # For each x in G, only if there is an edge in H
278    GH.add_edges_from(_nodes_cross_edges(G, H))
279    return GH
280
281
282def strong_product(G, H):
283    r"""Returns the strong product of G and H.
284
285    The strong product $P$ of the graphs $G$ and $H$ has a node set that
286    is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$.
287    $P$ has an edge $((u,v), (x,y))$ if and only if
288    $u==v$ and $(x,y)$ is an edge in $H$, or
289    $x==y$ and $(u,v)$ is an edge in $G$, or
290    $(u,v)$ is an edge in $G$ and $(x,y)$ is an edge in $H$.
291
292    Parameters
293    ----------
294    G, H: graphs
295     Networkx graphs.
296
297    Returns
298    -------
299    P: NetworkX graph
300     The Cartesian product of G and H. P will be a multi-graph if either G
301     or H is a multi-graph. Will be a directed if G and H are directed,
302     and undirected if G and H are undirected.
303
304    Raises
305    ------
306    NetworkXError
307     If G and H are not both directed or both undirected.
308
309    Notes
310    -----
311    Node attributes in P are two-tuple of the G and H node attributes.
312    Missing attributes are assigned None.
313
314    Examples
315    --------
316    >>> G = nx.Graph()
317    >>> H = nx.Graph()
318    >>> G.add_node(0, a1=True)
319    >>> H.add_node("a", a2="Spam")
320    >>> P = nx.strong_product(G, H)
321    >>> list(P)
322    [(0, 'a')]
323
324    Edge attributes and edge keys (for multigraphs) are also copied to the
325    new product graph
326    """
327    GH = _init_product_graph(G, H)
328    GH.add_nodes_from(_node_product(G, H))
329    GH.add_edges_from(_nodes_cross_edges(G, H))
330    GH.add_edges_from(_edges_cross_nodes(G, H))
331    GH.add_edges_from(_directed_edges_cross_edges(G, H))
332    if not GH.is_directed():
333        GH.add_edges_from(_undirected_edges_cross_edges(G, H))
334    return GH
335
336
337@not_implemented_for("directed")
338@not_implemented_for("multigraph")
339def power(G, k):
340    """Returns the specified power of a graph.
341
342    The $k$th power of a simple graph $G$, denoted $G^k$, is a
343    graph on the same set of nodes in which two distinct nodes $u$ and
344    $v$ are adjacent in $G^k$ if and only if the shortest path
345    distance between $u$ and $v$ in $G$ is at most $k$.
346
347    Parameters
348    ----------
349    G : graph
350        A NetworkX simple graph object.
351
352    k : positive integer
353        The power to which to raise the graph `G`.
354
355    Returns
356    -------
357    NetworkX simple graph
358        `G` to the power `k`.
359
360    Raises
361    ------
362    ValueError
363        If the exponent `k` is not positive.
364
365    NetworkXNotImplemented
366        If `G` is not a simple graph.
367
368    Examples
369    --------
370    The number of edges will never decrease when taking successive
371    powers:
372
373    >>> G = nx.path_graph(4)
374    >>> list(nx.power(G, 2).edges)
375    [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
376    >>> list(nx.power(G, 3).edges)
377    [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
378
379    The `k`th power of a cycle graph on *n* nodes is the complete graph
380    on *n* nodes, if `k` is at least ``n // 2``:
381
382    >>> G = nx.cycle_graph(5)
383    >>> H = nx.complete_graph(5)
384    >>> nx.is_isomorphic(nx.power(G, 2), H)
385    True
386    >>> G = nx.cycle_graph(8)
387    >>> H = nx.complete_graph(8)
388    >>> nx.is_isomorphic(nx.power(G, 4), H)
389    True
390
391    References
392    ----------
393    .. [1] J. A. Bondy, U. S. R. Murty, *Graph Theory*. Springer, 2008.
394
395    Notes
396    -----
397    This definition of "power graph" comes from Exercise 3.1.6 of
398    *Graph Theory* by Bondy and Murty [1]_.
399
400    """
401    if k <= 0:
402        raise ValueError("k must be a positive integer")
403    H = nx.Graph()
404    H.add_nodes_from(G)
405    # update BFS code to ignore self loops.
406    for n in G:
407        seen = {}  # level (number of hops) when seen in BFS
408        level = 1  # the current level
409        nextlevel = G[n]
410        while nextlevel:
411            thislevel = nextlevel  # advance to next level
412            nextlevel = {}  # and start a new list (fringe)
413            for v in thislevel:
414                if v == n:  # avoid self loop
415                    continue
416                if v not in seen:
417                    seen[v] = level  # set the level of vertex v
418                    nextlevel.update(G[v])  # add neighbors of v
419            if k <= level:
420                break
421            level += 1
422        H.add_edges_from((n, nbr) for nbr in seen)
423    return H
424
425
426@not_implemented_for("multigraph")
427def rooted_product(G, H, root):
428    """Return the rooted product of graphs G and H rooted at root in H.
429
430    A new graph is constructed representing the rooted product of
431    the inputted graphs, G and H, with a root in H.
432    A rooted product duplicates H for each nodes in G with the root
433    of H corresponding to the node in G. Nodes are renamed as the direct
434    product of G and H. The result is a subgraph of the cartesian product.
435
436    Parameters
437    ----------
438    G,H : graph
439       A NetworkX graph
440    root : node
441       A node in H
442
443    Returns
444    -------
445    R : The rooted product of G and H with a specified root in H
446
447    Notes
448    -----
449    The nodes of R are the Cartesian Product of the nodes of G and H.
450    The nodes of G and H are not relabeled.
451    """
452    if root not in H:
453        raise nx.NetworkXError("root must be a vertex in H")
454
455    R = nx.Graph()
456    R.add_nodes_from(product(G, H))
457
458    R.add_edges_from(((e[0], root), (e[1], root)) for e in G.edges())
459    R.add_edges_from(((g, e[0]), (g, e[1])) for g in G for e in H.edges())
460
461    return R
462