is_digraphical

is_digraphical(in_sequence, out_sequence)

Returns True if some directed graph can realize the in- and out-degree sequences.

Parameters:

in_sequencelist or iterable container

A sequence of integer node in-degrees

out_sequencelist or iterable container

A sequence of integer node out-degrees

Returns:

validbool

True if in and out-sequences are digraphic False if not.

Notes

This algorithm is from Kleitman and Wang [1]. The worst case runtime is \(O(s \times \log n)\) where \(s\) and \(n\) are the sum and length of the sequences respectively.

References

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