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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

use super::{GraphConversion, IOError};
use crate::utils::{fill_bitvector, get_size};

/// Creates an undirected graph from a graph6 representation
pub struct Graph {
    pub bit_vec: Vec<usize>,
    pub n: usize,
}
impl Graph {
    /// Creates a new undirected graph from a graph6 representation
    ///
    /// # Arguments
    /// * `repr` - A graph6 representation of the graph
    ///
    /// # Example
    /// ```
    /// use graph6_rs::Graph;
    /// let graph = Graph::from_g6("A_").unwrap();
    /// assert_eq!(graph.n, 2);
    /// assert_eq!(graph.bit_vec, &[0, 1, 1, 0]);
    /// ```
    pub fn from_g6(repr: &str) -> Result<Self, IOError> {
        let bytes = repr.as_bytes();
        let n = get_size(bytes, 0)?;
        let bit_vec = Self::build_bitvector(bytes, n);
        Ok(Self { bit_vec, n })
    }

    /// Builds the bitvector from the graph6 representation
    fn build_bitvector(bytes: &[u8], n: usize) -> Vec<usize> {
        let bv_len = n * (n - 1) / 2;
        let mut bit_vec = fill_bitvector(bytes, n, 1);
        Self::adjust_bitvector_len(&mut bit_vec, bv_len);
        Self::fill_from_triangle(&bit_vec, n)
    }

    /// Adjusts the length of the bitvector to the correct length
    fn adjust_bitvector_len(bit_vec: &mut Vec<usize>, bv_len: usize) {
        let adj_bv_len = bit_vec.len() - (bit_vec.len() - bv_len);
        bit_vec.truncate(adj_bv_len);
    }

    /// Fills the adjacency bitvector from an upper triangle
    fn fill_from_triangle(tri: &[usize], n: usize) -> Vec<usize> {
        let mut bit_vec = vec![0; n * n];
        let mut tri_iter = tri.iter();
        for i in 1..n {
            for j in 0..i {
                let idx = i * n + j;
                let jdx = j * n + i;
                let val = *tri_iter.next().unwrap();
                bit_vec[idx] = val;
                bit_vec[jdx] = val;
            }
        }
        bit_vec
    }
}
impl GraphConversion for Graph {
    /// Returns the bitvector representation of the graph
    fn bit_vec(&self) -> &[usize] {
        &self.bit_vec
    }

    /// Returns the number of vertices in the graph
    fn size(&self) -> usize {
        self.n
    }

    /// Returns true if the graph is directed
    fn is_directed(&self) -> bool {
        false
    }
}

#[cfg(test)]
mod testing {
    use super::{Graph, GraphConversion};

    #[test]
    fn test_graph_n2() {
        let graph = Graph::from_g6("A_").unwrap();
        assert_eq!(graph.size(), 2);
        assert_eq!(graph.bit_vec(), &[0, 1, 1, 0]);
    }

    #[test]
    fn test_graph_n2_empty() {
        let graph = Graph::from_g6("A?").unwrap();
        assert_eq!(graph.size(), 2);
        assert_eq!(graph.bit_vec(), &[0, 0, 0, 0]);
    }

    #[test]
    fn test_graph_n3() {
        let graph = Graph::from_g6("Bw").unwrap();
        assert_eq!(graph.size(), 3);
        assert_eq!(graph.bit_vec(), &[0, 1, 1, 1, 0, 1, 1, 1, 0]);
    }

    #[test]
    fn test_graph_n4() {
        let graph = Graph::from_g6("C~").unwrap();
        assert_eq!(graph.size(), 4);
        assert_eq!(
            graph.bit_vec(),
            &[0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0]
        );
    }

    #[test]
    fn test_to_adjacency() {
        let graph = Graph::from_g6("A_").unwrap();
        let adj = graph.to_adjmat();
        assert_eq!(adj, "0 1\n1 0\n");
    }

    #[test]
    fn test_to_dot() {
        let graph = Graph::from_g6("A_").unwrap();
        let dot = graph.to_dot(None);
        assert_eq!(dot, "graph {\n0 -- 1;\n}");
    }

    #[test]
    fn test_to_dot_with_label() {
        let graph = Graph::from_g6("A_").unwrap();
        let dot = graph.to_dot(Some(1));
        assert_eq!(dot, "graph graph_1 {\n0 -- 1;\n}");
    }

    #[test]
    fn test_to_net() {
        let repr = r"A_";
        let graph = Graph::from_g6(repr).unwrap();
        let net = graph.to_net();
        assert_eq!(net, "*Vertices 2\n1 \"0\"\n2 \"1\"\n*Arcs\n1 2\n2 1\n");
    }
}