"""提供支持计算图多项式的算法。
图多项式是编码了广泛结构信息的多项式值图不变量。例如包括Tutte多项式、色多项式、特征多项式和匹配多项式。在[1]中提供了广泛的论述。
作为一个简单的例子，可以使用 `~sympy.matrices.matrices.MatrixDeterminant.charpoly` 方法从图的邻接矩阵计算特征多项式。考虑完全图 ``K_4`` ：
>>> import sympy
>>> x = sympy.Symbol("x")
>>> G = nx.complete_graph(4)
>>> A = nx.to_numpy_array(G, dtype=int)
>>> M = sympy.SparseMatrix(A)
>>> M.charpoly(x).as_expr()
x**4 - 6*x**2 - 8*x - 3
.. [1] Y. Shi, M. Dehmer, X. Li, I. Gutman,
"Graph Polynomials"
"""
from collections import deque
import networkx as nx
from networkx.utils import not_implemented_for
__all__ = ["tutte_polynomial", "chromatic_polynomial"]
[docs]
@not_implemented_for("directed")
@nx._dispatchable
def tutte_polynomial(G):
r"""返回图 `G` 的 Tutte 多项式
此函数通过删除-收缩算法的迭代版本计算 Tutte 多项式。
Tutte 多项式 `T_G(x, y)` 是一个在两个变量中的基本图多项式不变量。它编码了与图的边连通性相关的广泛信息；“关于图的许多问题可以简化为在某些值上找到并评估 Tutte 多项式的问题” [1]_。事实上，图的每个可删除-收缩表达的特征都是 Tutte 多项式的一个特化 [2]_（参见注释中的示例）。
有几种等价的定义；以下是三种：
定义 1（秩-零度展开）：对于 `G` 是一个无向图， `n(G)` 是 `G` 的顶点数， `E` 是 `G` 的边集， `V` 是 `G` 的顶点集， `c(A)` 是具有顶点集 `V` 和边集 `A` 的图的连通分量数 [3]_：
.. math::
T_G(x, y) = \sum_{A \in E} (x-1)^{c(A) - c(E)} (y-1)^{c(A) + |A| - n(G)}
定义 2（生成树展开）：设 `G` 是一个无向图， `T` 是 `G` 的一个生成树， `E` 是 `G` 的边集。设 `E` 有一个任意的严格线性顺序 `L` 。设 `B_e` 是 $E \setminus T \cup {e}$ 的唯一最小非空边割。边 `e` 相对于 `T` 和 `L` 是内部活动的，如果 `e` 是根据线性顺序 `L` 在 `B_e` 中的最小边。 `T` 的内部活动（记为 `i(T)` ）是 $E \setminus T$ 中相对于 `T` 和 `L` 是内部活动的边的数量。设 `P_e` 是 $T \cup {e}$ 中源顶点和目标顶点相同的唯一路径。边 `e` 相对于 `T` 和 `L` 是外部活动的，如果 `e` 是根据线性顺序 `L` 在 `P_e` 中的最小边。 `T` 的外部活动（记为 `e(T)` ）是 $E \setminus T$ 中相对于 `T` 和 `L` 是外部活动的边的数量。然后 [4]_ [5]_：
.. math::
T_G(x, y) = \sum_{T \text{ 是 } G \text{ 的生成树}} x^{i(T)} y^{e(T)}
定义 3（删除-收缩递归）：对于 `G` 是一个无向图， `G-e` 是通过删除边 `e` 从 `G` 得到的图， `G/e` 是通过收缩边 `e` 从 `G` 得到的图， `k(G)` 是 `G` 的割边数， `l(G)` 是 `G` 的自环数：
.. math::
T_G(x, y) = \begin{cases}
x^{k(G)} y^{l(G)}, & \text{如果所有边都是割边或自环} \\
T_{G-e}(x, y) + T_{G/e}(x, y), & \text{否则，对于任意不是割边或自环的边 $e$}
\end{cases}
Parameters
----------
G : NetworkX 图
Returns
-------
`sympy.core.add.Add` 实例
表示 `G` 的 Tutte 多项式的 Sympy 表达式。
Examples
--------
>>> C = nx.cycle_graph(5)
>>> nx.tutte_polynomial(C)
x**4 + x**3 + x**2 + x + y
>>> D = nx.diamond_graph()
>>> nx.tutte_polynomial(D)
x**3 + 2*x**2 + 2*x*y + x + y**2 + y
Notes
-----
Tutte 多项式的一些特化：
- `T_G(1, 1)` 计算 `G` 的生成树数量
- `T_G(1, 2)` 计算 `G` 的连通生成子图数量
- `T_G(2, 1)` 计算 `G` 的生成森林数量
- `T_G(0, 2)` 计算 `G` 的强定向数量
- `T_G(2, 0)` 计算 `G` 的非循环定向数量
边收缩在 [6]_ 中定义，删除-收缩在 [6]_ 中引入。系数的组合意义在 [7]_ 中引入。普遍性、性质和应用在 [8]_ 中讨论。
实际上，当用户希望重复计算一个或多个图的边连通性相关信息时，预先计算 Tutte 多项式可能是有用的。
References
----------
.. [1] M. Brandt,
"The Tutte Polynomial."
Talking About Combinatorial Objects Seminar, 2015
https://math.berkeley.edu/~brandtm/talks/tutte.pdf
.. [2] A. Björklund, T. Husfeldt, P. Kaski, M. Koivisto,
"Computing the Tutte polynomial in vertex-exponential time"
49th Annual IEEE Symposium on Foundations of Computer Science, 2008
https://ieeexplore.ieee.org/abstract/document/4691000
.. [3] Y. Shi, M. Dehmer, X. Li, I. Gutman,
"Graph Polynomials," p. 14
.. [4] Y. Shi, M. Dehmer, X. Li, I. Gutman,
"Graph Polynomials," p. 46
.. [5] A. Nešetril, J. Goodall,
"Graph invariants, homomorphisms, and the Tutte polynomial"
https://iuuk.mff.cuni.cz/~andrew/Tutte.pdf
.. [6] D. B. West,
"Introduction to Graph Theory," p. 84
.. [7] G. Coutinho,
"A brief introduction to the Tutte polynomial"
Structural Analysis of Complex Networks, 2011
https://homepages.dcc.ufmg.br/~gabriel/seminars/coutinho_tuttepolynomial_seminar.pdf
.. [8] J. A. Ellis-Monaghan, C. Merino,
"Graph polynomials and their applications I: The Tutte polynomial"
Structural Analysis of Complex Networks, 2011
https://arxiv.org/pdf/0803.3079.pdf
"""
import sympy
x = sympy.Symbol("x")
y = sympy.Symbol("y")
stack = deque()
stack.append(nx.MultiGraph(G))
polynomial = 0
while stack:
G = stack.pop()
bridges = set(nx.bridges(G))
e = None
for i in G.edges:
if (i[0], i[1]) not in bridges and i[0] != i[1]:
e = i
break
if not e:
loops = list(nx.selfloop_edges(G, keys=True))
polynomial += x ** len(bridges) * y ** len(loops)
else:
# deletion-contraction
C = nx.contracted_edge(G, e, self_loops=True)
C.remove_edge(e[0], e[0])
G.remove_edge(*e)
stack.append(G)
stack.append(C)
return sympy.simplify(polynomial)
[docs]
@not_implemented_for("directed")
@nx._dispatchable
def chromatic_polynomial(G):
r"""返回图 `G` 的色多项式
此函数通过删除-收缩算法的迭代版本计算色多项式。
色多项式 `X_G(x)` 是一个基本的一元图多项式不变量。对自然数 `k` 计算 `X_G(k)` 可以枚举 `G` 的适当 k-着色。
有几种等价的定义；以下是三种：
定义 1（显式公式）：
对于无向图 `G` ， `c(G)` 是 `G` 的连通分量数， `E` 是 `G` 的边集， `G(S)` 是以 `S` 为边集的 `G` 的生成子图 [1]：
.. math::
X_G(x) = \sum_{S \subseteq E} (-1)^{|S|} x^{c(G(S))}
定义 2（插值多项式）：
对于无向图 `G` ， `n(G)` 是 `G` 的顶点数， `k_0 = 0` ，以及 `k_i` 是用 `i` 种不同颜色对 `G` 的顶点进行着色的不同方式数（对于最多 `n(G)` 的自然数 `i` ）， `X_G(x)` 是通过点 `(0, k_0), (1, k_1), \dots, (n(G), k_{n(G)})` 的唯一拉格朗日插值多项式，次数为 `n(G)` [2]。
定义 3（色递归）：
对于无向图 `G` ， `G-e` 是通过删除边 `e` 从 `G` 得到的图， `G/e` 是通过收缩边 `e` 从 `G` 得到的图， `n(G)` 是 `G` 的顶点数， `e(G)` 是 `G` 的边数 [3]：
.. math::
X_G(x) = \begin{cases}
x^{n(G)}, & \text{如果 $e(G)=0$} \\
X_{G-e}(x) - X_{G/e}(x), & \text{否则，对于任意边 $e$}
\end{cases}
此公式也称为基本约简定理 [4]。
Parameters
----------
G : NetworkX 图
Returns
-------
`sympy.core.add.Add` 实例
表示 `G` 的色多项式的 Sympy 表达式。
Examples
--------
>>> C = nx.cycle_graph(5)
>>> nx.chromatic_polynomial(C)
x**5 - 5*x**4 + 10*x**3 - 10*x**2 + 4*x
>>> G = nx.complete_graph(4)
>>> nx.chromatic_polynomial(G)
x**4 - 6*x**3 + 11*x**2 - 6*x
Notes
-----
系数的解释在 [5] 中讨论。几个特殊情况在 [2] 中列出。
色多项式是 Tutte 多项式的一个特例；特别是， ``X_G(x) = T_G(x, 0)`` [6]。
色多项式可能取负参数，尽管计算结果可能没有色解释。例如， ``X_G(-1)`` 枚举了 `G` 的无环方向 [7]。
References
----------
.. [1] D. B. West,
"Introduction to Graph Theory," p. 222
.. [2] E. W. Weisstein
"Chromatic Polynomial"
MathWorld--A Wolfram Web Resource
https://mathworld.wolfram.com/ChromaticPolynomial.html
.. [3] D. B. West,
"Introduction to Graph Theory," p. 221
.. [4] J. Zhang, J. Goodall,
"An Introduction to Chromatic Polynomials"
https://math.mit.edu/~apost/courses/18.204_2018/Julie_Zhang_paper.pdf
.. [5] R. C. Read,
"An Introduction to Chromatic Polynomials"
Journal of Combinatorial Theory, 1968
https://math.berkeley.edu/~mrklug/ReadChromatic.pdf
.. [6] W. T. Tutte,
"Graph-polynomials"
Advances in Applied Mathematics, 2004
https://www.sciencedirect.com/science/article/pii/S0196885803000411
.. [7] R. P. Stanley,
"Acyclic orientations of graphs"
Discrete Mathematics, 2006
https://math.mit.edu/~rstan/pubs/pubfiles/18.pdf
"""
import sympy
x = sympy.Symbol("x")
stack = deque()
stack.append(nx.MultiGraph(G, contraction_idx=0))
polynomial = 0
while stack:
G = stack.pop()
edges = list(G.edges)
if not edges:
polynomial += (-1) ** G.graph["contraction_idx"] * x ** len(G)
else:
e = edges[0]
C = nx.contracted_edge(G, e, self_loops=True)
C.graph["contraction_idx"] = G.graph["contraction_idx"] + 1
C.remove_edge(e[0], e[0])
G.remove_edge(*e)
stack.append(G)
stack.append(C)
return polynomial
