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

//! # graph6
//!
//! `graph6` is a library for encoding and decoding graphs in graph6 format.
//!
//! Currently, it supports decoding for graphs of size less than 63.

/// Decodes a string in graph6 format to an adjacency matrix.
///
/// The returned adjacency matrix is a vector with elements stored in row-major order.
///
/// # Panics
///
/// Panics if `graph_encoding` is empty.
///
/// # Example
///
/// ```
/// let graph_encoding = String::from("BW");
/// let adjacency_matrix = graph6::decode(&graph_encoding);
///
/// assert_eq!(adjacency_matrix, vec![0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0]);
/// ```
pub fn decode(graph_encoding: &str) -> Vec<f32> {
    if graph_encoding.is_empty() {
        panic!("graph encoding is empty");
    }

    adjacency_matrix(graph_encoding.as_bytes())
}

/// Returns the size of a graph given in graph6 format.
///
/// This function assumes that the size of the given graph is less than 63.
fn size(bytes: &[u8]) -> usize {
    // Since size is only called after checking that the given encoding is nonempty, the call to unwrap will never panic.
    let first_byte = bytes.first().unwrap();
    *first_byte as usize - 63
}

/// Returns the adjacency matrix of a graph given in graph6 format.
///
/// This function assumes that the size of the given graph is less than 63.
fn adjacency_matrix(bytes: &[u8]) -> Vec<f32> {
    let mut bit_vector: usize = 0;
    let mut shift = 0;

    bytes
        .iter()
        .skip(1) // The first byte encodes the size so it's ignored.
        .rev()
        .map(|byte| byte - 63)
        .for_each(|byte| {
            bit_vector |= (byte as usize) << shift;
            shift += 6;
        });

    let bit_vector_len = (bytes.len() - 1) * 6;

    let size = size(bytes);
    let actual_bit_vector_len = (size * (size - 1)) / 2;

    // The bit vector is padded with zeros to make the number of bits a multiple of six. The extra bits are removed before filling in the adjacency matrix.
    bit_vector >>= bit_vector_len - actual_bit_vector_len;

    let mut adjacency_matrix = vec![0.0; size * size];
    for i in 1..size {
        for j in 0..i {
            if (bit_vector & 0x1 << (actual_bit_vector_len - 1)) > 0 {
                adjacency_matrix[i * size + j] = 1.0;
                adjacency_matrix[j * size + i] = 1.0;
            }
            bit_vector <<= 1;
        }
    }

    adjacency_matrix
}

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

    #[test]
    fn size_five() {
        let graph_encoding = String::from("DQc");

        assert_eq!(5, size(graph_encoding.as_bytes()));
    }

    #[test]
    fn four_by_four_matrix() {
        let graph_encoding = String::from("C]");
        let matrix = vec![0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0];

        assert_eq!(matrix, adjacency_matrix(graph_encoding.as_bytes()));
    }
}