is_digraphical

is_digraphical(in_sequence, out_sequence)

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

参数:

in_sequencelist 或 可迭代容器

一个包含整数节点入度的序列

out_sequencelist 或 可迭代容器

一个包含整数节点出度的序列

返回:

validbool

如果入度和出度序列是可有向图的，则为 True；否则为 False。

注释

该算法来自 Kleitman 和 Wang [1]。最坏情况下的运行时长为 \(O(s \times \log n)\)，其中 \(s\) 和 \(n\) 分别是序列的总和和长度。

参考文献

[1]

D.J. Kleitman and D.L. Wang Algorithms for Constructing Graphs and Digraphs with Given Valences and Factors, Discrete Mathematics, 6(1), pp. 79-88 (1973)

示例

>>> 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