is_digraphical

is_digraphical(in_sequence, out_sequence)

如果某个有向图可以实现给定的入度和出度序列，则返回 True。

Parameters:

in_sequence列表或可迭代容器

一个整数节点入度序列

out_sequence列表或可迭代容器

一个整数节点出度序列

Returns:

validbool

如果入度和出度序列是可图的，则返回 True，否则返回 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)

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