Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/polynomials.py: 20%
51 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Provides algorithms supporting the computation of graph polynomials.
3Graph polynomials are polynomial-valued graph invariants that encode a wide
4variety of structural information. Examples include the Tutte polynomial,
5chromatic polynomial, characteristic polynomial, and matching polynomial. An
6extensive treatment is provided in [1]_.
8For a simple example, the `~sympy.matrices.matrices.MatrixDeterminant.charpoly`
9method can be used to compute the characteristic polynomial from the adjacency
10matrix of a graph. Consider the complete graph ``K_4``:
12>>> import sympy
13>>> x = sympy.Symbol("x")
14>>> G = nx.complete_graph(4)
15>>> A = nx.adjacency_matrix(G)
16>>> M = sympy.SparseMatrix(A.todense())
17>>> M.charpoly(x).as_expr()
18x**4 - 6*x**2 - 8*x - 3
21.. [1] Y. Shi, M. Dehmer, X. Li, I. Gutman,
22 "Graph Polynomials"
23"""
24from collections import deque
26import networkx as nx
27from networkx.utils import not_implemented_for
29__all__ = ["tutte_polynomial", "chromatic_polynomial"]
32@not_implemented_for("directed")
33@nx._dispatch
34def tutte_polynomial(G):
35 r"""Returns the Tutte polynomial of `G`
37 This function computes the Tutte polynomial via an iterative version of
38 the deletion-contraction algorithm.
40 The Tutte polynomial `T_G(x, y)` is a fundamental graph polynomial invariant in
41 two variables. It encodes a wide array of information related to the
42 edge-connectivity of a graph; "Many problems about graphs can be reduced to
43 problems of finding and evaluating the Tutte polynomial at certain values" [1]_.
44 In fact, every deletion-contraction-expressible feature of a graph is a
45 specialization of the Tutte polynomial [2]_ (see Notes for examples).
47 There are several equivalent definitions; here are three:
49 Def 1 (rank-nullity expansion): For `G` an undirected graph, `n(G)` the
50 number of vertices of `G`, `E` the edge set of `G`, `V` the vertex set of
51 `G`, and `c(A)` the number of connected components of the graph with vertex
52 set `V` and edge set `A` [3]_:
54 .. math::
56 T_G(x, y) = \sum_{A \in E} (x-1)^{c(A) - c(E)} (y-1)^{c(A) + |A| - n(G)}
58 Def 2 (spanning tree expansion): Let `G` be an undirected graph, `T` a spanning
59 tree of `G`, and `E` the edge set of `G`. Let `E` have an arbitrary strict
60 linear order `L`. Let `B_e` be the unique minimal nonempty edge cut of
61 $E \setminus T \cup {e}$. An edge `e` is internally active with respect to
62 `T` and `L` if `e` is the least edge in `B_e` according to the linear order
63 `L`. The internal activity of `T` (denoted `i(T)`) is the number of edges
64 in $E \setminus T$ that are internally active with respect to `T` and `L`.
65 Let `P_e` be the unique path in $T \cup {e}$ whose source and target vertex
66 are the same. An edge `e` is externally active with respect to `T` and `L`
67 if `e` is the least edge in `P_e` according to the linear order `L`. The
68 external activity of `T` (denoted `e(T)`) is the number of edges in
69 $E \setminus T$ that are externally active with respect to `T` and `L`.
70 Then [4]_ [5]_:
72 .. math::
74 T_G(x, y) = \sum_{T \text{ a spanning tree of } G} x^{i(T)} y^{e(T)}
76 Def 3 (deletion-contraction recurrence): For `G` an undirected graph, `G-e`
77 the graph obtained from `G` by deleting edge `e`, `G/e` the graph obtained
78 from `G` by contracting edge `e`, `k(G)` the number of cut-edges of `G`,
79 and `l(G)` the number of self-loops of `G`:
81 .. math::
82 T_G(x, y) = \begin{cases}
83 x^{k(G)} y^{l(G)}, & \text{if all edges are cut-edges or self-loops} \\
84 T_{G-e}(x, y) + T_{G/e}(x, y), & \text{otherwise, for an arbitrary edge $e$ not a cut-edge or loop}
85 \end{cases}
87 Parameters
88 ----------
89 G : NetworkX graph
91 Returns
92 -------
93 instance of `sympy.core.add.Add`
94 A Sympy expression representing the Tutte polynomial for `G`.
96 Examples
97 --------
98 >>> C = nx.cycle_graph(5)
99 >>> nx.tutte_polynomial(C)
100 x**4 + x**3 + x**2 + x + y
102 >>> D = nx.diamond_graph()
103 >>> nx.tutte_polynomial(D)
104 x**3 + 2*x**2 + 2*x*y + x + y**2 + y
106 Notes
107 -----
108 Some specializations of the Tutte polynomial:
110 - `T_G(1, 1)` counts the number of spanning trees of `G`
111 - `T_G(1, 2)` counts the number of connected spanning subgraphs of `G`
112 - `T_G(2, 1)` counts the number of spanning forests in `G`
113 - `T_G(0, 2)` counts the number of strong orientations of `G`
114 - `T_G(2, 0)` counts the number of acyclic orientations of `G`
116 Edge contraction is defined and deletion-contraction is introduced in [6]_.
117 Combinatorial meaning of the coefficients is introduced in [7]_.
118 Universality, properties, and applications are discussed in [8]_.
120 Practically, up-front computation of the Tutte polynomial may be useful when
121 users wish to repeatedly calculate edge-connectivity-related information
122 about one or more graphs.
124 References
125 ----------
126 .. [1] M. Brandt,
127 "The Tutte Polynomial."
128 Talking About Combinatorial Objects Seminar, 2015
129 https://math.berkeley.edu/~brandtm/talks/tutte.pdf
130 .. [2] A. Björklund, T. Husfeldt, P. Kaski, M. Koivisto,
131 "Computing the Tutte polynomial in vertex-exponential time"
132 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
133 https://ieeexplore.ieee.org/abstract/document/4691000
134 .. [3] Y. Shi, M. Dehmer, X. Li, I. Gutman,
135 "Graph Polynomials," p. 14
136 .. [4] Y. Shi, M. Dehmer, X. Li, I. Gutman,
137 "Graph Polynomials," p. 46
138 .. [5] A. Nešetril, J. Goodall,
139 "Graph invariants, homomorphisms, and the Tutte polynomial"
140 https://iuuk.mff.cuni.cz/~andrew/Tutte.pdf
141 .. [6] D. B. West,
142 "Introduction to Graph Theory," p. 84
143 .. [7] G. Coutinho,
144 "A brief introduction to the Tutte polynomial"
145 Structural Analysis of Complex Networks, 2011
146 https://homepages.dcc.ufmg.br/~gabriel/seminars/coutinho_tuttepolynomial_seminar.pdf
147 .. [8] J. A. Ellis-Monaghan, C. Merino,
148 "Graph polynomials and their applications I: The Tutte polynomial"
149 Structural Analysis of Complex Networks, 2011
150 https://arxiv.org/pdf/0803.3079.pdf
151 """
152 import sympy
154 x = sympy.Symbol("x")
155 y = sympy.Symbol("y")
156 stack = deque()
157 stack.append(nx.MultiGraph(G))
159 polynomial = 0
160 while stack:
161 G = stack.pop()
162 bridges = set(nx.bridges(G))
164 e = None
165 for i in G.edges:
166 if (i[0], i[1]) not in bridges and i[0] != i[1]:
167 e = i
168 break
169 if not e:
170 loops = list(nx.selfloop_edges(G, keys=True))
171 polynomial += x ** len(bridges) * y ** len(loops)
172 else:
173 # deletion-contraction
174 C = nx.contracted_edge(G, e, self_loops=True)
175 C.remove_edge(e[0], e[0])
176 G.remove_edge(*e)
177 stack.append(G)
178 stack.append(C)
179 return sympy.simplify(polynomial)
182@not_implemented_for("directed")
183@nx._dispatch
184def chromatic_polynomial(G):
185 r"""Returns the chromatic polynomial of `G`
187 This function computes the chromatic polynomial via an iterative version of
188 the deletion-contraction algorithm.
190 The chromatic polynomial `X_G(x)` is a fundamental graph polynomial
191 invariant in one variable. Evaluating `X_G(k)` for an natural number `k`
192 enumerates the proper k-colorings of `G`.
194 There are several equivalent definitions; here are three:
196 Def 1 (explicit formula):
197 For `G` an undirected graph, `c(G)` the number of connected components of
198 `G`, `E` the edge set of `G`, and `G(S)` the spanning subgraph of `G` with
199 edge set `S` [1]_:
201 .. math::
203 X_G(x) = \sum_{S \subseteq E} (-1)^{|S|} x^{c(G(S))}
206 Def 2 (interpolating polynomial):
207 For `G` an undirected graph, `n(G)` the number of vertices of `G`, `k_0 = 0`,
208 and `k_i` the number of distinct ways to color the vertices of `G` with `i`
209 unique colors (for `i` a natural number at most `n(G)`), `X_G(x)` is the
210 unique Lagrange interpolating polynomial of degree `n(G)` through the points
211 `(0, k_0), (1, k_1), \dots, (n(G), k_{n(G)})` [2]_.
214 Def 3 (chromatic recurrence):
215 For `G` an undirected graph, `G-e` the graph obtained from `G` by deleting
216 edge `e`, `G/e` the graph obtained from `G` by contracting edge `e`, `n(G)`
217 the number of vertices of `G`, and `e(G)` the number of edges of `G` [3]_:
219 .. math::
220 X_G(x) = \begin{cases}
221 x^{n(G)}, & \text{if $e(G)=0$} \\
222 X_{G-e}(x) - X_{G/e}(x), & \text{otherwise, for an arbitrary edge $e$}
223 \end{cases}
225 This formulation is also known as the Fundamental Reduction Theorem [4]_.
228 Parameters
229 ----------
230 G : NetworkX graph
232 Returns
233 -------
234 instance of `sympy.core.add.Add`
235 A Sympy expression representing the chromatic polynomial for `G`.
237 Examples
238 --------
239 >>> C = nx.cycle_graph(5)
240 >>> nx.chromatic_polynomial(C)
241 x**5 - 5*x**4 + 10*x**3 - 10*x**2 + 4*x
243 >>> G = nx.complete_graph(4)
244 >>> nx.chromatic_polynomial(G)
245 x**4 - 6*x**3 + 11*x**2 - 6*x
247 Notes
248 -----
249 Interpretation of the coefficients is discussed in [5]_. Several special
250 cases are listed in [2]_.
252 The chromatic polynomial is a specialization of the Tutte polynomial; in
253 particular, ``X_G(x) = T_G(x, 0)`` [6]_.
255 The chromatic polynomial may take negative arguments, though evaluations
256 may not have chromatic interpretations. For instance, ``X_G(-1)`` enumerates
257 the acyclic orientations of `G` [7]_.
259 References
260 ----------
261 .. [1] D. B. West,
262 "Introduction to Graph Theory," p. 222
263 .. [2] E. W. Weisstein
264 "Chromatic Polynomial"
265 MathWorld--A Wolfram Web Resource
266 https://mathworld.wolfram.com/ChromaticPolynomial.html
267 .. [3] D. B. West,
268 "Introduction to Graph Theory," p. 221
269 .. [4] J. Zhang, J. Goodall,
270 "An Introduction to Chromatic Polynomials"
271 https://math.mit.edu/~apost/courses/18.204_2018/Julie_Zhang_paper.pdf
272 .. [5] R. C. Read,
273 "An Introduction to Chromatic Polynomials"
274 Journal of Combinatorial Theory, 1968
275 https://math.berkeley.edu/~mrklug/ReadChromatic.pdf
276 .. [6] W. T. Tutte,
277 "Graph-polynomials"
278 Advances in Applied Mathematics, 2004
279 https://www.sciencedirect.com/science/article/pii/S0196885803000411
280 .. [7] R. P. Stanley,
281 "Acyclic orientations of graphs"
282 Discrete Mathematics, 2006
283 https://math.mit.edu/~rstan/pubs/pubfiles/18.pdf
284 """
285 import sympy
287 x = sympy.Symbol("x")
288 stack = deque()
289 stack.append(nx.MultiGraph(G, contraction_idx=0))
291 polynomial = 0
292 while stack:
293 G = stack.pop()
294 edges = list(G.edges)
295 if not edges:
296 polynomial += (-1) ** G.graph["contraction_idx"] * x ** len(G)
297 else:
298 e = edges[0]
299 C = nx.contracted_edge(G, e, self_loops=True)
300 C.graph["contraction_idx"] = G.graph["contraction_idx"] + 1
301 C.remove_edge(e[0], e[0])
302 G.remove_edge(*e)
303 stack.append(G)
304 stack.append(C)
305 return polynomial