Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

# networkx.algorithms.graphical.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 – True if in and out-sequences are digraphic False if not.

Return type

bool

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)