Warning
This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
is_digraphical¶
- is_digraphical(in_sequence, out_sequence)[source]¶
Returns True if some directed graph can realize the in- and out-degree sequences.
Parameters : in_sequence : list or iterable container
A sequence of integer node in-degrees
out_sequence : list or iterable container
A sequence of integer node out-degrees
Returns : valid : bool
True if in and out-sequences are digraphic False if not.
Notes
This algorithm is from Kleitman and Wang [R241]. The worst case runtime is O(s * log n) where s and n are the sum and length of the sequences respectively.
References
[R241] (1, 2) 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)