"""
图的积运算。
"""
from itertools import product
import networkx as nx
from networkx.utils import not_implemented_for
__all__ = [
"tensor_product",
"cartesian_product",
"lexicographic_product",
"strong_product",
"power",
"rooted_product",
"corona_product",
"modular_product",
]
_G_H = {"G": 0, "H": 1}
def _dict_product(d1, d2):
return {k: (d1.get(k), d2.get(k)) for k in set(d1) | set(d2)}
# Generators for producing graph products
def _node_product(G, H):
for u, v in product(G, H):
yield ((u, v), _dict_product(G.nodes[u], H.nodes[v]))
def _directed_edges_cross_edges(G, H):
if not G.is_multigraph() and not H.is_multigraph():
for u, v, c in G.edges(data=True):
for x, y, d in H.edges(data=True):
yield (u, x), (v, y), _dict_product(c, d)
if not G.is_multigraph() and H.is_multigraph():
for u, v, c in G.edges(data=True):
for x, y, k, d in H.edges(data=True, keys=True):
yield (u, x), (v, y), k, _dict_product(c, d)
if G.is_multigraph() and not H.is_multigraph():
for u, v, k, c in G.edges(data=True, keys=True):
for x, y, d in H.edges(data=True):
yield (u, x), (v, y), k, _dict_product(c, d)
if G.is_multigraph() and H.is_multigraph():
for u, v, j, c in G.edges(data=True, keys=True):
for x, y, k, d in H.edges(data=True, keys=True):
yield (u, x), (v, y), (j, k), _dict_product(c, d)
def _undirected_edges_cross_edges(G, H):
if not G.is_multigraph() and not H.is_multigraph():
for u, v, c in G.edges(data=True):
for x, y, d in H.edges(data=True):
yield (v, x), (u, y), _dict_product(c, d)
if not G.is_multigraph() and H.is_multigraph():
for u, v, c in G.edges(data=True):
for x, y, k, d in H.edges(data=True, keys=True):
yield (v, x), (u, y), k, _dict_product(c, d)
if G.is_multigraph() and not H.is_multigraph():
for u, v, k, c in G.edges(data=True, keys=True):
for x, y, d in H.edges(data=True):
yield (v, x), (u, y), k, _dict_product(c, d)
if G.is_multigraph() and H.is_multigraph():
for u, v, j, c in G.edges(data=True, keys=True):
for x, y, k, d in H.edges(data=True, keys=True):
yield (v, x), (u, y), (j, k), _dict_product(c, d)
def _edges_cross_nodes(G, H):
if G.is_multigraph():
for u, v, k, d in G.edges(data=True, keys=True):
for x in H:
yield (u, x), (v, x), k, d
else:
for u, v, d in G.edges(data=True):
for x in H:
if H.is_multigraph():
yield (u, x), (v, x), None, d
else:
yield (u, x), (v, x), d
def _nodes_cross_edges(G, H):
if H.is_multigraph():
for x in G:
for u, v, k, d in H.edges(data=True, keys=True):
yield (x, u), (x, v), k, d
else:
for x in G:
for u, v, d in H.edges(data=True):
if G.is_multigraph():
yield (x, u), (x, v), None, d
else:
yield (x, u), (x, v), d
def _edges_cross_nodes_and_nodes(G, H):
if G.is_multigraph():
for u, v, k, d in G.edges(data=True, keys=True):
for x in H:
for y in H:
yield (u, x), (v, y), k, d
else:
for u, v, d in G.edges(data=True):
for x in H:
for y in H:
if H.is_multigraph():
yield (u, x), (v, y), None, d
else:
yield (u, x), (v, y), d
def _init_product_graph(G, H):
if G.is_directed() != H.is_directed():
msg = "G and H must be both directed or both undirected"
raise nx.NetworkXError(msg)
if G.is_multigraph() or H.is_multigraph():
GH = nx.MultiGraph()
else:
GH = nx.Graph()
if G.is_directed():
GH = GH.to_directed()
return GH
[docs]
@nx._dispatchable(graphs=_G_H, preserve_node_attrs=True, returns_graph=True)
def tensor_product(G, H):
r"""返回 G 和 H 的张量积。
图 $G$ 和 $H$ 的张量积 $P$ 的节点集是节点集的笛卡尔积，即 $V(P)=V(G) \times V(H)$。$P$ 具有边 $((u,v), (x,y))$ 当且仅当 $(u,x)$ 是 $G$ 中的边且 $(v,y)$ 是 $H$ 中的边。
张量积有时也被称为范畴积、直积、基数积或合取。
Parameters
----------
G, H: 图
Networkx 图。
Returns
-------
P: NetworkX 图
G 和 H 的张量积。如果 G 或 H 是多重图，则 P 将是多重图；如果 G 和 H 是有向图，则 P 将是有向图；如果 G 和 H 是无向图，则 P 将是无向图。
Raises
------
NetworkXError
如果 G 和 H 不都是有向图或都是无向图。
Notes
-----
P 中的节点属性是 G 和 H 节点属性的二元组。缺失的属性被赋值为 None。
Examples
--------
>>> G = nx.Graph()
>>> H = nx.Graph()
>>> G.add_node(0, a1=True)
>>> H.add_node("a", a2="Spam")
>>> P = nx.tensor_product(G, H)
>>> list(P)
[(0, 'a')]
边属性和边键（对于多重图）也会被复制到新的积图中。
"""
GH = _init_product_graph(G, H)
GH.add_nodes_from(_node_product(G, H))
GH.add_edges_from(_directed_edges_cross_edges(G, H))
if not GH.is_directed():
GH.add_edges_from(_undirected_edges_cross_edges(G, H))
return GH
[docs]
@nx._dispatchable(graphs=_G_H, preserve_node_attrs=True, returns_graph=True)
def cartesian_product(G, H):
r"""返回 G 和 H 的笛卡尔积。
图 G 和 H 的笛卡尔积 $P$ 的节点集是节点集的笛卡尔积，$V(P)=V(G) \times V(H)$。
$P$ 具有边 $((u,v),(x,y))$ 当且仅当 $u$ 等于 $x$ 且 $v$ 和 $y$ 在 $H$ 中相邻，或者 $v$ 等于 $y$ 且 $u$ 和 $x$ 在 $G$ 中相邻。
Parameters
----------
G, H: 图
Networkx 图。
Returns
-------
P: NetworkX 图
G 和 H 的笛卡尔积。如果 G 或 H 是多图，则 P 将是多图。如果 G 和 H 是有向的，则 P 将是有向的，如果 G 和 H 是无向的，则 P 将是无向的。
Raises
------
NetworkXError
如果 G 和 H 不都是有向的或都是无向的。
Notes
-----
P 中的节点属性是 G 和 H 节点属性的二元组。
缺失的属性被赋值为 None。
Examples
--------
>>> G = nx.Graph()
>>> H = nx.Graph()
>>> G.add_node(0, a1=True)
>>> H.add_node("a", a2="Spam")
>>> P = nx.cartesian_product(G, H)
>>> list(P)
[(0, 'a')]
边属性和边键（对于多图）也会被复制到新的积图。
"""
GH = _init_product_graph(G, H)
GH.add_nodes_from(_node_product(G, H))
GH.add_edges_from(_edges_cross_nodes(G, H))
GH.add_edges_from(_nodes_cross_edges(G, H))
return GH
[docs]
@nx._dispatchable(graphs=_G_H, preserve_node_attrs=True, returns_graph=True)
def lexicographic_product(G, H):
r"""返回 G 和 H 的字典序乘积。
图 $G$ 和 $H$ 的字典序乘积 $P$ 的节点集是节点集的笛卡尔积，即 $V(P)=V(G) \times V(H)$。$P$ 具有边 $((u,v), (x,y))$ 当且仅当 $(u,v)$ 是 $G$ 中的边，或者 $u==v$ 且 $(x,y)$ 是 $H$ 中的边。
Parameters
----------
G, H: 图
Networkx 图。
Returns
-------
P: NetworkX 图
G 和 H 的笛卡尔积。如果 G 或 H 是多重图，则 P 将是多重图。如果 G 和 H 是有向的，则 P 将是有向的；如果 G 和 H 是无向的，则 P 将是无向的。
Raises
------
NetworkXError
如果 G 和 H 不都是有向的或都是无向的。
Notes
-----
P 中的节点属性是 G 和 H 节点属性的二元组。缺失的属性被赋值为 None。
Examples
--------
>>> G = nx.Graph()
>>> H = nx.Graph()
>>> G.add_node(0, a1=True)
>>> H.add_node("a", a2="Spam")
>>> P = nx.lexicographic_product(G, H)
>>> list(P)
[(0, 'a')]
边属性和边键（对于多重图）也会被复制到新的乘积图中。
"""
GH = _init_product_graph(G, H)
GH.add_nodes_from(_node_product(G, H))
# Edges in G regardless of H designation
GH.add_edges_from(_edges_cross_nodes_and_nodes(G, H))
# For each x in G, only if there is an edge in H
GH.add_edges_from(_nodes_cross_edges(G, H))
return GH
[docs]
@nx._dispatchable(graphs=_G_H, preserve_node_attrs=True, returns_graph=True)
def strong_product(G, H):
r"""返回 G 和 H 的强积图。
图 G 和 H 的强积图 $P$ 的节点集是节点集的笛卡尔积，即 $V(P)=V(G) \times V(H)$。
$P$ 具有边 $((u,x), (v,y))$ 如果满足以下任一条件：
- $u=v$ 且 $(x,y)$ 是 H 中的边
- $x=y$ 且 $(u,v)$ 是 G 中的边
- $(u,v)$ 是 G 中的边且 $(x,y)$ 是 H 中的边
Parameters
----------
G, H: 图
Networkx 图。
Returns
-------
P: NetworkX 图
G 和 H 的笛卡尔积。如果 G 或 H 是多重图，则 P 将是多重图。如果 G 和 H 是有向的，则 P 将是有向的，如果 G 和 H 是无向的，则 P 将是无向的。
Raises
------
NetworkXError
如果 G 和 H 不都是有向的或都是无向的。
Notes
-----
P 中的节点属性是 G 和 H 节点属性的二元组。
缺失的属性被赋值为 None。
Examples
--------
>>> G = nx.Graph()
>>> H = nx.Graph()
>>> G.add_node(0, a1=True)
>>> H.add_node("a", a2="Spam")
>>> P = nx.strong_product(G, H)
>>> list(P)
[(0, 'a')]
边属性和边键（对于多重图）也会被复制到新的积图。
"""
GH = _init_product_graph(G, H)
GH.add_nodes_from(_node_product(G, H))
GH.add_edges_from(_nodes_cross_edges(G, H))
GH.add_edges_from(_edges_cross_nodes(G, H))
GH.add_edges_from(_directed_edges_cross_edges(G, H))
if not GH.is_directed():
GH.add_edges_from(_undirected_edges_cross_edges(G, H))
return GH
[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable(returns_graph=True)
def power(G, k):
"""返回指定幂次的图。
简单图 $G$ 的第 $k$ 次幂，记作 $G^k$，是一个具有相同节点集的图，其中两个不同的节点 $u$ 和 $v$ 在 $G^k$ 中相邻当且仅当 $G$ 中 $u$ 和 $v$ 之间的最短路径距离不超过 $k$。
Parameters
----------
G : 图
一个 NetworkX 简单图对象。
k : 正整数
要提升图 `G` 的幂次。
Returns
-------
NetworkX 简单图
`G` 的 `k` 次幂。
Raises
------
ValueError
如果指数 `k` 不是正数。
NetworkXNotImplemented
如果 `G` 不是简单图。
Examples
--------
当连续取幂时，边的数量永远不会减少：
>>> G = nx.path_graph(4)
>>> list(nx.power(G, 2).edges)
[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
>>> list(nx.power(G, 3).edges)
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
如果 `k` 至少为 ``n // 2`` ，则具有 *n* 个节点的循环图的第 `k` 次幂是完全图：
>>> G = nx.cycle_graph(5)
>>> H = nx.complete_graph(5)
>>> nx.is_isomorphic(nx.power(G, 2), H)
True
>>> G = nx.cycle_graph(8)
>>> H = nx.complete_graph(8)
>>> nx.is_isomorphic(nx.power(G, 4), H)
True
References
----------
.. [1] J. A. Bondy, U. S. R. Murty, *Graph Theory*. Springer, 2008.
Notes
-----
这个“幂图”的定义来自 Bondy 和 Murty 所著的《图论》中的练习 3.1.6 [1]。
"""
if k <= 0:
raise ValueError("k must be a positive integer")
H = nx.Graph()
H.add_nodes_from(G)
# update BFS code to ignore self loops.
for n in G:
seen = {} # level (number of hops) when seen in BFS
level = 1 # the current level
nextlevel = G[n]
while nextlevel:
thislevel = nextlevel # advance to next level
nextlevel = {} # and start a new list (fringe)
for v in thislevel:
if v == n: # avoid self loop
continue
if v not in seen:
seen[v] = level # set the level of vertex v
nextlevel.update(G[v]) # add neighbors of v
if k <= level:
break
level += 1
H.add_edges_from((n, nbr) for nbr in seen)
return H
[docs]
@not_implemented_for("multigraph")
@nx._dispatchable(graphs=_G_H, returns_graph=True)
def rooted_product(G, H, root):
"""返回以H中root为根的图G和H的根积。
构建一个新图，表示输入图G和H的根积，根在H中。根积将H复制为G中的每个节点，H的根对应G中的节点。节点被重命名为G和H的直接积。结果是笛卡尔积的子图。
Parameters
----------
G,H : 图
一个NetworkX图
root : 节点
H中的一个节点
Returns
-------
R : G和H的根积，指定根在H中
Notes
-----
R的节点是G和H节点的笛卡尔积。G和H的节点未重新标记。
"""
if root not in H:
raise nx.NetworkXError("root must be a vertex in H")
R = nx.Graph()
R.add_nodes_from(product(G, H))
R.add_edges_from(((e[0], root), (e[1], root)) for e in G.edges())
R.add_edges_from(((g, e[0]), (g, e[1])) for g in G for e in H.edges())
return R
[docs]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
@nx._dispatchable(graphs=_G_H, returns_graph=True)
def corona_product(G, H):
r"""返回 G 和 H 的 Corona 积。
G 和 H 的 Corona 积是通过以下方式得到的图 $C = G \circ H$：
取一个 G 的副本，称为中心图，以及 $|V(G)|$ 个 H 的副本，称为外图，
并将 G 的第 $i$ 个顶点与 H 的第 $i$ 个副本的每个顶点相邻，其中 $1 ≤ i ≤ |V(G)|$。
Parameters
----------
G, H: NetworkX 图
要进行 Corona 积运算的图。
`G` 是中心图， `H` 是外图。
Returns
-------
C: NetworkX 图
G 和 H 的 Corona 积。
Raises
------
NetworkXError
如果 G 和 H 不都是有向图或无向图。
Examples
--------
>>> G = nx.cycle_graph(4)
>>> H = nx.path_graph(2)
>>> C = nx.corona_product(G, H)
>>> list(C)
[0, 1, 2, 3, (0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)]
>>> print(C)
Graph with 12 nodes and 16 edges
References
----------
[1] M. Tavakoli, F. Rahbarnia, and A. R. Ashrafi,
"Studying the corona product of graphs under some graph invariants,"
Transactions on Combinatorics, vol. 3, no. 3, pp. 43–49, Sep. 2014,
doi: 10.22108/toc.2014.5542.
[2] A. Faraji, "Corona Product in Graph Theory," Ali Faraji, May 11, 2021.
https://blog.alifaraji.ir/math/graph-theory/corona-product.html (accessed Dec. 07, 2021).
"""
GH = _init_product_graph(G, H)
GH.add_nodes_from(G)
GH.add_edges_from(G.edges)
for G_node in G:
# copy nodes of H in GH, call it H_i
GH.add_nodes_from((G_node, v) for v in H)
# copy edges of H_i based on H
GH.add_edges_from(
((G_node, e0), (G_node, e1), d) for e0, e1, d in H.edges.data()
)
# creating new edges between H_i and a G's node
GH.add_edges_from((G_node, (G_node, H_node)) for H_node in H)
return GH
[docs]
@nx._dispatchable(
graphs=_G_H, preserve_edge_attrs=True, preserve_node_attrs=True, returns_graph=True
)
def modular_product(G, H):
r"""返回 `G` 和 `H` 的模积图。
`G` 和 `H` 的模积图是图 $M = G \nabla H$，由节点集 $V(M) = V(G) \times V(H)$ 组成，这是 `G` 和 `H` 节点集的笛卡尔积。进一步地，M 包含边 ((u, v), (x, y))：
- 如果 u 在 `G` 中与 x 相邻且 v 在 `H` 中与 y 相邻，或者
- 如果 u 在 `G` 中与 x 不相邻且 v 在 `H` 中与 y 不相邻。
更正式地：
E(M) = {((u, v), (x, y)) | ((u, x) in E(G) and (v, y) in E(H)) or
((u, x) not in E(G) and (v, y) not in E(H))}
Parameters
----------
G, H: NetworkX 图
要计算模积的图。
Returns
-------
M: NetworkX 图
`G` 和 `H` 的模积图。
Raises
------
NetworkXNotImplemented
如果 `G` 不是简单图。
Examples
--------
>>> G = nx.cycle_graph(4)
>>> H = nx.path_graph(2)
>>> M = nx.modular_product(G, H)
>>> list(M)
[(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)]
>>> print(M)
Graph with 8 nodes and 8 edges
Notes
-----
*模积* 在 [1]_ 中定义，最初作为 *弱模积* 引入。
模积将 `G` 和 `H` 中计数同构子图的问题简化为在 M 中计数团的问题。由 M 中团的节点诱导的 `G` 和 `H` 的子图是同构的 [2]_ [3]_。
References
----------
.. [1] R. Hammack, W. Imrich, 和 S. Klavžar,
"Handbook of Product Graphs", CRC Press, 2011.
.. [2] H. G. Barrow 和 R. M. Burstall,
"Subgraph isomorphism, matching relational structures and maximal
cliques", Information Processing Letters, vol. 4, issue 4, pp. 83-84,
1976, https://doi.org/10.1016/0020-0190(76)90049-1.
.. [3] V. G. Vizing, "Reduction of the problem of isomorphism and isomorphic
entrance to the task of finding the nondensity of a graph." Proc. Third
All-Union Conference on Problems of Theoretical Cybernetics. 1974.
"""
if G.is_directed() or H.is_directed():
raise nx.NetworkXNotImplemented(
"Modular product not implemented for directed graphs"
)
if G.is_multigraph() or H.is_multigraph():
raise nx.NetworkXNotImplemented(
"Modular product not implemented for multigraphs"
)
GH = _init_product_graph(G, H)
GH.add_nodes_from(_node_product(G, H))
for u, v, c in G.edges(data=True):
for x, y, d in H.edges(data=True):
GH.add_edge((u, x), (v, y), **_dict_product(c, d))
GH.add_edge((v, x), (u, y), **_dict_product(c, d))
G = nx.complement(G)
H = nx.complement(H)
for u, v, c in G.edges(data=True):
for x, y, d in H.edges(data=True):
GH.add_edge((u, x), (v, y), **_dict_product(c, d))
GH.add_edge((v, x), (u, y), **_dict_product(c, d))
return GH
