Graphicallity

Undirected degree sequence

Python

is_graphic(degree_seq: List[int]) → bool

C++

template<std::ranges::forward_range Range>
requires degree_range<Range>
bool is_graphic(Range &&degree_sequence)

Checks if the sequence can be the degree sequence of a valid undirected graph, containing no multi-edges or loops, based on the Erdős–Gallai algorithm [8, 9].

>>> import reticula as ret
>>> ret.is_graphic([2, 2, 1, 1])
True
>>> ret.is_graphic([2, 2, 1, 2])
False

Directed degree-pair sequence

Python

is_digraphic(in_out_degree_sequence: List[Pair[int, int]]) → bool

C++

template<std::ranges::input_range PairRange>
requires degree_pair_range<PairRange>
bool is_digraphic(PairRange &&in_out_degree_sequence)

Checks if the sequence can be the degree-pair sequence of a valid directed graph, containing no multi-edges or loops, based on the algorithm by Kleitman and Wang [10].

A degree pair sequence is a range (list) of pairs (2-tuples) of integers, where the first element of each item represents in-degree and the second item out-degree of one vertex.

>>> import reticula as ret
>>> ret.is_digraphic([(0, 1), (2, 0), (0, 1), (1, 1)])
True
>>> ret.is_digraphic([(0, 1), (2, 0), (0, 1), (1, 2)])
False