graph6/

lib.rs

//! # graph6
//!
//! `graph6` is a library for converting between strings in graph6 format and adjacency matrices.

/// Converts a string in graph6 format to its adjacency matrix, and returns the matrix and the graph size.
///
/// The returned adjacency matrix is a vector with elements stored in row-major order. Note, this function only supports graphs with less than 63 vertices.
///
/// # Panics
///
/// Panics if the graph has more than 62 vertices.
///
/// # Example
///
/// ```
/// let graph = String::from("BW");
/// let (adjacency_matrix, size) = graph6::string_to_adjacency_matrix(&graph);
///
/// assert_eq!(adjacency_matrix, vec![0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0]);
/// assert_eq!(size, 3);
/// ```
pub fn string_to_adjacency_matrix(graph_str: &str) -> (Vec<f32>, usize) {
    let bytes = graph_str.as_bytes();

    let size = size_from_bytes(bytes).unwrap_or_else(|err| {
        panic!("{}", err);
    });

    let mut bit_vec: Vec<u8> = Vec::new();
    bytes.iter().skip(1).map(|byte| byte - 63).for_each(|byte| {
        for shift in (0..6).rev() {
            if (byte & 1 << shift) > 0 {
                bit_vec.push(1);
            } else {
                bit_vec.push(0);
            }
        }
    });

    let adjusted_bit_vec_len = bit_vec.len() - (bit_vec.len() - (size * (size - 1)) / 2);

    let mut bit_vec_iter = bit_vec[0..adjusted_bit_vec_len].iter();

    let mut adjacency_matrix = vec![0.0; size * size];
    for i in 1..size {
        for j in 0..i {
            if *(bit_vec_iter.next().unwrap()) == 1 {
                adjacency_matrix[i * size + j] = 1.0;
                adjacency_matrix[j * size + i] = 1.0;
            }
        }
    }

    (adjacency_matrix, size)
}

/// Converts an adjacency matrix to its string representation in graph6 format.
///
/// The adjacency matrix must be a vector with elements stored in row-major order.
///
/// # Panics
///
/// Panics if `size` is greater than 258,047.
///
/// # Example
///
/// ```
/// let adjacency_matrix = vec![0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0];
/// let size = 3;
/// let graph = graph6::adjacency_matrix_to_string(&adjacency_matrix, size);
///
/// assert_eq!(graph, String::from("BW"));
/// ```
pub fn adjacency_matrix_to_string(adjacency_matrix: &[f32], size: usize) -> String {
    let mut size_bytes = size_to_bytes(size).unwrap_or_else(|err| {
        panic!("{}", err);
    });

    let mut bit_vec = Vec::new();
    for i in 1..size {
        for j in 0..i {
            if adjacency_matrix[i * size + j] == 1.0 {
                bit_vec.push(1);
            } else {
                bit_vec.push(0);
            }
        }
    }

    let mut bytes = bit_vec_to_bytes(bit_vec);

    size_bytes.append(&mut bytes);

    unsafe { String::from_utf8_unchecked(size_bytes) }
}

/// Converts an integer to its bit vector representation.
fn int_to_bit_vec(mut x: usize) -> Vec<u8> {
    let mut bit_vec = Vec::new();

    while x != 0 {
        if x & 1 == 1 {
            bit_vec.push(1);
        } else {
            bit_vec.push(0);
        }

        x >>= 1;
    }

    bit_vec.reverse();

    bit_vec
}

/// Converts a bit vector to a vector of "bytes" (each element of the vector is a group of six bits).
fn bit_vec_to_bytes(mut bit_vec: Vec<u8>) -> Vec<u8> {
    // The length of bit_vec must be a multiple of six. If it isn't, bit_vec is padded with zeroes to round its length to the next multiple of six.
    let next_multiple_of_six = bit_vec.len() - 1 - (bit_vec.len() - 1) % 6 + 6;
    for _ in 0..(next_multiple_of_six - bit_vec.len()) {
        bit_vec.push(0);
    }

    let mut bytes = Vec::new();
    let mut bit_vec_iter = bit_vec.iter();

    for _ in 0..(bit_vec.len() / 6) {
        let mut byte: u8 = 0;
        for shift in (0..6).rev() {
            // Since the number of loop iterations is equal to the length of bit_vec, the call to unwrap will never panic.
            byte |= bit_vec_iter.next().unwrap() << shift;
        }
        bytes.push(byte);
    }

    bytes.iter().map(|byte| byte + 63).collect()
}

/// Returns the size of a graph given its string representation.
fn size_from_bytes(bytes: &[u8]) -> Result<usize, &'static str> {
    // The first byte is 126 for graphs with more than 62 vertices.
    if bytes[0] == 126 {
        return Err("size is greater than 62");
    }

    Ok((bytes[0] - 63) as usize)
}

/// Converts an integer, i.e., the size of a graph, to its representation in bytes.
fn size_to_bytes(size: usize) -> Result<Vec<u8>, &'static str> {
    match size {
        s if s <= 62 => Ok(vec![size as u8 + 63]),
        s if s <= 258047 => {
            let mut size_bytes = vec![126];
            size_bytes.append(&mut bit_vec_to_bytes(int_to_bit_vec(size)));
            Ok(size_bytes)
        }
        _ => Err("size is greater than 258,047"),
    }
}

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

    #[test]
    fn size_four_graph_to_adjacency_matrix() {
        let graph_str = String::from("C]");

        let (adjacency_matrix, size) = string_to_adjacency_matrix(&graph_str);

        assert_eq!(
            adjacency_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!(size, 4);
    }

    #[test]
    fn size_120000_to_bytes() {
        let size = 120000;
        let bytes = vec![126, 121, 101, 63];

        assert_eq!(size_to_bytes(size).unwrap(), bytes);
    }
}