graphalgs 0.2.0

Graph algorithms based on the Rust 'petgraph' library.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

//! Special algorithms that are difficult to categorize.
mod prufer;
pub use prufer::{prufer_code, prufer_decode};

mod laplacian;
pub use laplacian::laplacian_matrix;

mod st;
pub use st::count_spanning_trees;

use std::collections::BinaryHeap;

/// Check whether the sequence of numbers is graph-like.
///
/// A sequence of non-negative integers is called a graph-like
/// if it is a sequence of powers of some simple graph.
///
/// # Example
///
/// ```
/// use graphalgs::spec::is_degree_sequence_graphlike;
///
/// // Graph: [ 1-2-2-1 ] (the numbers are degrees of the vertices).
/// assert!(is_degree_sequence_graphlike(&[2, 2, 1, 1]));
///
/// // A single vertex of a graph cannot have degree 2.
/// assert!(!is_degree_sequence_graphlike(&[2]));
/// ```
pub fn is_degree_sequence_graphlike(degrees: &[usize]) -> bool {
    // At each step of the algorithm, we remove the vertex with the maximum degree d,
    // and then try to reduce the d of the following degrees by 1.
    // If at some point this becomes impossible, then this sequence is not a graph sequence.

    // The sum of the degrees of the vertices must be even.
    if degrees.iter().sum::<usize>() % 2 == 1 {
        return false;
    }

    // Isolated vertexes are not of interest.
    let mut degrees = degrees
        .iter()
        .copied()
        .filter(|d| *d > 0usize)
        .collect::<BinaryHeap<usize>>();

    while !degrees.is_empty() {
        let d = degrees.pop().unwrap();
        if d > degrees.len() {
            return false;
        }

        let mut temp = Vec::<usize>::new();
        for _ in 0..d {
            let x = degrees.pop().unwrap();
            if x == 0 {
                return false;
            }
            temp.push(x - 1);
        }

        for x in temp.into_iter() {
            if x != 0 {
                degrees.push(x);
            }
        }
    }

    true
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_is_the_degree_sequence_graphlike() {
        assert!(is_degree_sequence_graphlike(&[]));
        assert!(is_degree_sequence_graphlike(&[0]));
        assert!(!is_degree_sequence_graphlike(&[1]));
        assert!(!is_degree_sequence_graphlike(&[2]));
        assert!(!is_degree_sequence_graphlike(&[5]));
        assert!(is_degree_sequence_graphlike(&[1, 1]));
        assert!(!is_degree_sequence_graphlike(&[1, 2]));
        assert!(is_degree_sequence_graphlike(&[0, 0, 0]));
        assert!(!is_degree_sequence_graphlike(&[1, 1, 1]));
        assert!(!is_degree_sequence_graphlike(&[1, 2, 0]));
        assert!(is_degree_sequence_graphlike(&[1, 2, 1]));
        assert!(is_degree_sequence_graphlike(&[5, 5, 4, 3, 2, 2, 2, 1]));
        assert!(is_degree_sequence_graphlike(&[5, 3, 5, 5, 2, 2, 1, 1]));
        assert!(!is_degree_sequence_graphlike(&[5, 5, 5, 4, 2, 1, 1, 1]));
        assert!(is_degree_sequence_graphlike(&[
            1, 1, 1, 4, 2, 3, 1, 3, 1, 1
        ]));
        assert!(!is_degree_sequence_graphlike(&[
            1, 1, 10, 4, 2, 3, 1, 3, 1, 1
        ]));
    }
}