"""测试图形的序列。"""
import heapq
import networkx as nx
__all__ = [
"is_graphical",
"is_multigraphical",
"is_pseudographical",
"is_digraphical",
"is_valid_degree_sequence_erdos_gallai",
"is_valid_degree_sequence_havel_hakimi",
]
[docs]
@nx._dispatchable(graphs=None)
def is_graphical(sequence, method="eg"):
"""如果序列是一个有效的度序列，则返回 True。
度序列是有效的，如果某些图可以实现它。
Parameters
----------
sequence : 列表或可迭代容器
一个整数节点度的序列
method : "eg" | "hh" （默认：'eg'）
用于验证度序列的方法。
"eg" 对应于 Erdős-Gallai 算法
[EG1960]_, [choudum1986]_，以及
"hh" 对应于 Havel-Hakimi 算法
[havel1955]_, [hakimi1962]_, [CL1996]_。
Returns
-------
valid : bool
如果序列是有效的度序列，则为 True，否则为 False。
Examples
--------
>>> G = nx.path_graph(4)
>>> sequence = (d for n, d in G.degree())
>>> nx.is_graphical(sequence)
True
测试一个非图形序列：
>>> sequence_list = [d for n, d in G.degree()]
>>> sequence_list[-1] += 1
>>> nx.is_graphical(sequence_list)
False
References
----------
.. [EG1960] Erdős 和 Gallai, Mat. Lapok 11 264, 1960.
.. [choudum1986] S.A. Choudum. "A simple proof of the Erdős-Gallai theorem on
graph sequences." Bulletin of the Australian Mathematical Society, 33,
pp 67-70, 1986. https://doi.org/10.1017/S0004972700002872
.. [havel1955] Havel, V. "A Remark on the Existence of Finite Graphs"
Casopis Pest. Mat. 80, 477-480, 1955.
.. [hakimi1962] Hakimi, S. "On the Realizability of a Set of Integers as
Degrees of the Vertices of a Graph." SIAM J. Appl. Math. 10, 496-506, 1962.
.. [CL1996] G. Chartrand 和 L. Lesniak, "Graphs and Digraphs",
Chapman and Hall/CRC, 1996.
"""
if method == "eg":
valid = is_valid_degree_sequence_erdos_gallai(list(sequence))
elif method == "hh":
valid = is_valid_degree_sequence_havel_hakimi(list(sequence))
else:
msg = "`method` must be 'eg' or 'hh'"
raise nx.NetworkXException(msg)
return valid
def _basic_graphical_tests(deg_sequence):
# Sort and perform some simple tests on the sequence
deg_sequence = nx.utils.make_list_of_ints(deg_sequence)
p = len(deg_sequence)
num_degs = [0] * p
dmax, dmin, dsum, n = 0, p, 0, 0
for d in deg_sequence:
# Reject if degree is negative or larger than the sequence length
if d < 0 or d >= p:
raise nx.NetworkXUnfeasible
# Process only the non-zero integers
elif d > 0:
dmax, dmin, dsum, n = max(dmax, d), min(dmin, d), dsum + d, n + 1
num_degs[d] += 1
# Reject sequence if it has odd sum or is oversaturated
if dsum % 2 or dsum > n * (n - 1):
raise nx.NetworkXUnfeasible
return dmax, dmin, dsum, n, num_degs
[docs]
@nx._dispatchable(graphs=None)
def is_valid_degree_sequence_havel_hakimi(deg_sequence):
r"""如果度序列可以通过简单图实现，则返回 True。
验证过程使用 Havel-Hakimi 定理 [havel1955]_, [hakimi1962]_, [CL1996]_。
最坏情况下的运行时间是 $O(s)$，其中 $s$ 是序列的和。
Parameters
----------
deg_sequence : list
一个整数列表，每个元素指定图中一个节点的度数。
Returns
-------
valid : bool
如果 deg_sequence 是图形的，则返回 True，否则返回 False。
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
>>> sequence = (d for _, d in G.degree())
>>> nx.is_valid_degree_sequence_havel_hakimi(sequence)
True
测试一个非有效序列：
>>> sequence_list = [d for _, d in G.degree()]
>>> sequence_list[-1] += 1
>>> nx.is_valid_degree_sequence_havel_hakimi(sequence_list)
False
Notes
-----
ZZ 条件指出，对于序列 d，如果
.. math::
|d| >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)}
则 d 是图形的。这在 [1]_ 中的定理 6 中被证明。
References
----------
.. [1] I.E. Zverovich 和 V.E. Zverovich。"对图形序列理论的贡献"，离散数学，105，第 292-303 页（1992）。
.. [havel1955] Havel, V. "关于有限图存在性的一个注记"，Casopis Pest. Mat. 80，第 477-480 页，1955。
.. [hakimi1962] Hakimi, S. "关于将一组整数实现为图的顶点度数的可行性"，SIAM J. Appl. Math. 10，第 496-506 页，1962。
.. [CL1996] G. Chartrand 和 L. Lesniak，"图和有向图"，Chapman and Hall/CRC，1996。
"""
try:
dmax, dmin, dsum, n, num_degs = _basic_graphical_tests(deg_sequence)
except nx.NetworkXUnfeasible:
return False
# Accept if sequence has no non-zero degrees or passes the ZZ condition
if n == 0 or 4 * dmin * n >= (dmax + dmin + 1) * (dmax + dmin + 1):
return True
modstubs = [0] * (dmax + 1)
# Successively reduce degree sequence by removing the maximum degree
while n > 0:
# Retrieve the maximum degree in the sequence
while num_degs[dmax] == 0:
dmax -= 1
# If there are not enough stubs to connect to, then the sequence is
# not graphical
if dmax > n - 1:
return False
# Remove largest stub in list
num_degs[dmax], n = num_degs[dmax] - 1, n - 1
# Reduce the next dmax largest stubs
mslen = 0
k = dmax
for i in range(dmax):
while num_degs[k] == 0:
k -= 1
num_degs[k], n = num_degs[k] - 1, n - 1
if k > 1:
modstubs[mslen] = k - 1
mslen += 1
# Add back to the list any non-zero stubs that were removed
for i in range(mslen):
stub = modstubs[i]
num_degs[stub], n = num_degs[stub] + 1, n + 1
return True
[docs]
@nx._dispatchable(graphs=None)
def is_valid_degree_sequence_erdos_gallai(deg_sequence):
r"""如果度序列可以通过简单图实现，则返回 True。
验证使用的是 Erdős-Gallai 定理 [EG1960]。
Parameters
----------
deg_sequence : 列表
一个整数列表
Returns
-------
valid : 布尔值
如果 deg_sequence 是图形的则返回 True，否则返回 False。
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
>>> sequence = (d for _, d in G.degree())
>>> nx.is_valid_degree_sequence_erdos_gallai(sequence)
True
测试一个非有效的序列：
>>> sequence_list = [d for _, d in G.degree()]
>>> sequence_list[-1] += 1
>>> nx.is_valid_degree_sequence_erdos_gallai(sequence_list)
False
Notes
-----
此实现使用了 Erdős-Gallai 准则的等价形式。
最坏情况下的运行时间是 $O(n)$，其中 $n$ 是序列的长度。
具体来说，序列 d 是图形的当且仅当序列的和是偶数，并且对于序列中的所有强索引 k，
.. math::
\sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{j=k+1}^{n} \min(d_i,k)
= k(n-1) - ( k \sum_{j=0}^{k-1} n_j - \sum_{j=0}^{k-1} j n_j )
强索引 k 是任何满足 d_k >= k 的索引，值 n_j 是 j 在 d 中的出现次数。最大强索引称为 Durfee 索引。
这种特定的重排来自 [2]_ 中定理 3 的证明。
ZZ 条件表示，对于序列 d，如果
.. math::
|d| >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)}
则 d 是图形的。这在 [2]_ 中的定理 6 中被证明。
References
----------
.. [1] A. Tripathi 和 S. Vijay. "A note on a theorem of Erdős & Gallai",
Discrete Mathematics, 265, pp. 417-420 (2003).
.. [2] I.E. Zverovich 和 V.E. Zverovich. "Contributions to the theory
of graphic sequences", Discrete Mathematics, 105, pp. 292-303 (1992).
.. [EG1960] Erdős 和 Gallai, Mat. Lapok 11 264, 1960.
"""
try:
dmax, dmin, dsum, n, num_degs = _basic_graphical_tests(deg_sequence)
except nx.NetworkXUnfeasible:
return False
# Accept if sequence has no non-zero degrees or passes the ZZ condition
if n == 0 or 4 * dmin * n >= (dmax + dmin + 1) * (dmax + dmin + 1):
return True
# Perform the EG checks using the reformulation of Zverovich and Zverovich
k, sum_deg, sum_nj, sum_jnj = 0, 0, 0, 0
for dk in range(dmax, dmin - 1, -1):
if dk < k + 1: # Check if already past Durfee index
return True
if num_degs[dk] > 0:
run_size = num_degs[dk] # Process a run of identical-valued degrees
if dk < k + run_size: # Check if end of run is past Durfee index
run_size = dk - k # Adjust back to Durfee index
sum_deg += run_size * dk
for v in range(run_size):
sum_nj += num_degs[k + v]
sum_jnj += (k + v) * num_degs[k + v]
k += run_size
if sum_deg > k * (n - 1) - k * sum_nj + sum_jnj:
return False
return True
[docs]
@nx._dispatchable(graphs=None)
def is_multigraphical(sequence):
"""如果某个多重图可以实现该序列，则返回 True。
Parameters
----------
sequence : list
一个整数列表
Returns
-------
valid : bool
如果 deg_sequence 是一个多重图度序列，则返回 True，否则返回 False。
Examples
--------
>>> G = nx.MultiGraph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
>>> sequence = (d for _, d in G.degree())
>>> nx.is_multigraphical(sequence)
True
测试一个非多重图序列：
>>> sequence_list = [d for _, d in G.degree()]
>>> sequence_list[-1] += 1
>>> nx.is_multigraphical(sequence_list)
False
Notes
-----
最坏情况下的运行时间是 $O(n)$，其中 $n$ 是序列的长度。
References
----------
.. [1] S. L. Hakimi. "关于将一组整数作为线性图顶点的度数实现的问题", J. SIAM, 10, 第 496-506 页 (1962).
"""
try:
deg_sequence = nx.utils.make_list_of_ints(sequence)
except nx.NetworkXError:
return False
dsum, dmax = 0, 0
for d in deg_sequence:
if d < 0:
return False
dsum, dmax = dsum + d, max(dmax, d)
if dsum % 2 or dsum < 2 * dmax:
return False
return True
[docs]
@nx._dispatchable(graphs=None)
def is_pseudographical(sequence):
"""如果某个伪图可以实现该序列，则返回 True。
每个和为偶数的非负整数序列都是伪图的（参见 [1]）。
Parameters
----------
sequence : 列表或可迭代容器
一个整数节点度序列
Returns
-------
valid : bool
如果序列是伪图的度序列，则返回 True，否则返回 False。
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
>>> sequence = (d for _, d in G.degree())
>>> nx.is_pseudographical(sequence)
True
测试一个非伪图序列：
>>> sequence_list = [d for _, d in G.degree()]
>>> sequence_list[-1] += 1
>>> nx.is_pseudographical(sequence_list)
False
Notes
-----
最坏情况下的运行时间是 $O(n)$，其中 n 是序列的长度。
References
----------
.. [1] F. Boesch 和 F. Harary。"图及其度列表的线移除算法"，IEEE 电路与系统汇刊，CAS-23(12)，
第 778-782 页（1976 年）。
"""
try:
deg_sequence = nx.utils.make_list_of_ints(sequence)
except nx.NetworkXError:
return False
return sum(deg_sequence) % 2 == 0 and min(deg_sequence) >= 0
[docs]
@nx._dispatchable(graphs=None)
def is_digraphical(in_sequence, out_sequence):
r"""如果某个有向图可以实现给定的入度和出度序列，则返回 True。
Parameters
----------
in_sequence : 列表或可迭代容器
一个整数节点入度序列
out_sequence : 列表或可迭代容器
一个整数节点出度序列
Returns
-------
valid : bool
如果入度和出度序列是可图的，则返回 True，否则返回 False。
Examples
--------
>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 3), (3, 4), (4, 2), (5, 1), (5, 4)])
>>> in_seq = (d for n, d in G.in_degree())
>>> out_seq = (d for n, d in G.out_degree())
>>> nx.is_digraphical(in_seq, out_seq)
True
测试一个非可图场景：
>>> in_seq_list = [d for n, d in G.in_degree()]
>>> in_seq_list[-1] += 1
>>> nx.is_digraphical(in_seq_list, out_seq)
False
Notes
-----
该算法来自 Kleitman 和 Wang [1]。
最坏情况下的运行时间是 $O(s \times \log n)$，其中 $s$ 和 $n$ 分别是序列的和与长度。
References
----------
.. [1] D.J. Kleitman 和 D.L. Wang
构造具有给定价和因子的图和有向图的算法，离散数学，6(1)，第79-88页 (1973)
"""
try:
in_deg_sequence = nx.utils.make_list_of_ints(in_sequence)
out_deg_sequence = nx.utils.make_list_of_ints(out_sequence)
except nx.NetworkXError:
return False
# Process the sequences and form two heaps to store degree pairs with
# either zero or non-zero out degrees
sumin, sumout, nin, nout = 0, 0, len(in_deg_sequence), len(out_deg_sequence)
maxn = max(nin, nout)
maxin = 0
if maxn == 0:
return True
stubheap, zeroheap = [], []
for n in range(maxn):
in_deg, out_deg = 0, 0
if n < nout:
out_deg = out_deg_sequence[n]
if n < nin:
in_deg = in_deg_sequence[n]
if in_deg < 0 or out_deg < 0:
return False
sumin, sumout, maxin = sumin + in_deg, sumout + out_deg, max(maxin, in_deg)
if in_deg > 0:
stubheap.append((-1 * out_deg, -1 * in_deg))
elif out_deg > 0:
zeroheap.append(-1 * out_deg)
if sumin != sumout:
return False
heapq.heapify(stubheap)
heapq.heapify(zeroheap)
modstubs = [(0, 0)] * (maxin + 1)
# Successively reduce degree sequence by removing the maximum out degree
while stubheap:
# Take the first value in the sequence with non-zero in degree
(freeout, freein) = heapq.heappop(stubheap)
freein *= -1
if freein > len(stubheap) + len(zeroheap):
return False
# Attach out stubs to the nodes with the most in stubs
mslen = 0
for i in range(freein):
if zeroheap and (not stubheap or stubheap[0][0] > zeroheap[0]):
stubout = heapq.heappop(zeroheap)
stubin = 0
else:
(stubout, stubin) = heapq.heappop(stubheap)
if stubout == 0:
return False
# Check if target is now totally connected
if stubout + 1 < 0 or stubin < 0:
modstubs[mslen] = (stubout + 1, stubin)
mslen += 1
# Add back the nodes to the heap that still have available stubs
for i in range(mslen):
stub = modstubs[i]
if stub[1] < 0:
heapq.heappush(stubheap, stub)
else:
heapq.heappush(zeroheap, stub[0])
if freeout < 0:
heapq.heappush(zeroheap, freeout)
return True
