Function is_graphical 

pub fn is_graphical(
    out_degrees: &[igraph_int_t],
    in_degrees: Option<&[igraph_int_t]>,
    allowed: impl Into<AllowedEdgeTypes>,
) -> Result<bool>

Is there a graph with the given degree sequence?

For an undirected graph pass the degrees as out_degrees and in_degrees = None; for a directed graph pass both the out- and the in-degree sequences (of equal length). allowed says which edges the realization may use (anything convertible into AllowedEdgeTypes, e.g. EdgeTypeSw::Simple or AllowedEdgeTypes::ALL). Sequences with negative entries are simply not graphical.

The tests used are, for undirected graphs: the Erdős–Gallai conditions (Cloteaux’s linear-time algorithm) for simple graphs; an even degree sum when loops and multi-edges are allowed; additionally a degree sum at least twice the maximum degree for loopless multigraphs; Cairns–Mendan’s modified Erdős–Gallai conditions for at most one self-loop per vertex. For directed graphs: the Fulkerson–Chen–Anstee theorem with Berger’s relaxation for simple digraphs; equal in- and out-degree sums with loops and multi-edges; additionally an out-degree sum at least the maximum total degree for loopless multigraphs; the Gale–Ryser theorem when single self-loops are allowed.

Binds igraph_is_graphical. See also Graph::realize_degree_sequence, which builds a realization of a graphical sequence (for the edge types it implements: simple, loopless multi- and loopy multigraphs when undirected, simple digraphs when directed, it succeeds exactly when this test says yes; single self-loops without multi-edges, and non-simple digraphs, fail with ErrorKind::Unimplemented), and Graph::degree_sequence_game, which samples one at random.

Time complexity: O(n), n being the length of the sequence(s).

Errors

ErrorKind::InvalidValue if the out- and in-degree sequences have different lengths, or if the sum of the (non-negative) degrees exceeds i64::MAX / 2: igraph would add them up with signed overflow, which is undefined behavior in C, so such sequences are rejected on the Rust side.

Examples

use igraph::mixing::{is_graphical, AllowedEdgeTypes};
use igraph::prelude::*;

// (3, 3): two vertices of degree 3 need a triple edge or loops.
assert!(!is_graphical(&[3, 3], None, EdgeTypeSw::Simple)?);
assert!(is_graphical(&[3, 3], None, EdgeTypeSw::Multi)?);
assert!(is_graphical(&[3, 3], None, EdgeTypeSw::Loops)?);
// (1, 2, 5) needs multi-edges *and* loops.
assert!(!is_graphical(&[1, 2, 5], None, EdgeTypeSw::Multi)?);
assert!(is_graphical(&[1, 2, 5], None, AllowedEdgeTypes::ALL)?);
// Directed: a 3-cycle has out- and in-degrees all equal to 1.
assert!(is_graphical(&[1, 1, 1], Some(&[1, 1, 1]), EdgeTypeSw::Simple)?);
assert!(!is_graphical(&[2, 0], Some(&[0, 2]), EdgeTypeSw::Simple)?);

// A graphical sequence can be realized with the same edge types.
let seq = [3, 3, 2, 2, 2, 1, 1];
assert!(is_graphical(&seq, None, AllowedEdgeTypes::SIMPLE)?);
let g = Graph::realize_degree_sequence(
    &seq, None, AllowedEdgeTypes::SIMPLE, RealizeDegseq::Smallest)?;
assert_eq!(g.degree(.., NeighborMode::All, Loops::Twice)?, seq);