snark_tool/service/io/
reader_s6.rs

1use crate::graph::graph::{Graph, GraphConstructor};
2use crate::service::io::error::ReadError;
3use crate::service::io::reader::GraphFileReader;
4use crate::service::io::reader_g6::{get_graph_size, BIAS};
5use crate::service::io::writer_s6::{bitvec_from_u64, edge_encoding_size};
6use std::fs::File;
7use std::io::BufRead;
8use std::slice::Iter;
9use std::str::Chars;
10use std::{fs, io, marker, result};
11
12type Result<T> = result::Result<T, ReadError>;
13
14///
15/// Ideally use with `SimpleSparseGraph`
16///
17pub struct S6Reader<'a, G> {
18    lines: io::Lines<io::BufReader<&'a fs::File>>,
19
20    _ph: marker::PhantomData<G>,
21}
22
23impl<'a, G> GraphFileReader<'a, G> for S6Reader<'a, G>
24where
25    G: Graph + GraphConstructor,
26{
27    fn new(file: &'a File) -> Self {
28        S6Reader {
29            lines: io::BufReader::new(file).lines(),
30            _ph: marker::PhantomData,
31        }
32    }
33
34    fn next(&mut self) -> Option<Result<G>> {
35        let line = self.lines.next();
36        match line {
37            None => {
38                // warn - file contains less graphs than specified to work with
39                return None;
40            }
41            Some(line) => {
42                if let Ok(line_str) = line {
43                    if line_str.trim().is_empty() {
44                        return self.next();
45                    }
46                    let graph = S6Reader::read_graph(line_str);
47                    return Some(graph);
48                } else {
49                    // skip error lines?
50                    return self.next();
51                }
52            }
53        }
54    }
55}
56
57impl<'a, G> S6Reader<'_, G>
58where
59    G: Graph + GraphConstructor,
60{
61    pub fn read_graph(source: impl AsRef<str>) -> Result<G> {
62        let string = String::from(source.as_ref());
63
64        let mut chars = string.chars();
65        let char_opt = chars.next();
66        if char_opt.is_none() || !':'.eq(&char_opt.unwrap()) {
67            return Err(ReadError {
68                message: "".to_string(),
69            });
70        }
71        let size = get_graph_size(&mut chars)?;
72        let edge_encoding_size = edge_encoding_size(size as usize);
73        let graph = S6Reader::create_graph(&mut chars, size, edge_encoding_size)?;
74        Ok(graph)
75    }
76
77    fn create_graph(iterator: &mut Chars, size: u64, edge_encoding_size: u8) -> Result<G> {
78        let vertices = size as usize;
79        // reserve edges - in default for cubic graph
80        let edges = (size * 3 / 2) as usize;
81        let mut graph = G::with_capacity(vertices, edges);
82
83        for _node in 0..size {
84            graph.add_vertex();
85        }
86        let mut bit_vec = chars_to_bit_vector(iterator)?;
87
88        discard_additional_bits(&mut bit_vec, edge_encoding_size);
89        graph = S6Reader::decode_edges(&bit_vec, graph, edge_encoding_size)?;
90        Ok(graph)
91    }
92
93    fn decode_edges(bits: &Vec<bool>, mut graph: G, edge_encoding_size: u8) -> Result<G> {
94        let size = graph.size();
95        let mut v: usize = 0;
96
97        let mut bit_iter = bits.iter();
98        let mut bit_opt = bit_iter.next();
99        while bit_opt.is_some() {
100            let leading = bit_opt.unwrap();
101            if *leading {
102                v += 1;
103            }
104
105            let num = bitvec_to_u64(&mut bit_iter, edge_encoding_size)?;
106            if num >= size {
107                break;
108            }
109            if num > v {
110                v = num;
111            } else {
112                graph.add_edge(num, v);
113            }
114            bit_opt = bit_iter.next();
115        }
116        Ok(graph)
117    }
118}
119
120fn discard_additional_bits(bits: &mut Vec<bool>, edge_encoding_size: u8) {
121    let additional_bits = bits.len() % (edge_encoding_size + 1) as usize;
122    for _additional_bit in 0..additional_bits {
123        bits.pop();
124    }
125}
126
127fn chars_to_bit_vector(chars: &mut Chars) -> Result<Vec<bool>> {
128    let mut char_opt = chars.next();
129    let mut vec = vec![];
130    while char_opt.is_some() {
131        let num = (char_opt.unwrap() as u64) - BIAS as u64;
132        let mut char_bitvec = bitvec_from_u64(num, 6);
133        vec.append(&mut char_bitvec);
134        char_opt = chars.next();
135    }
136    Ok(vec)
137}
138
139pub fn bitvec_to_u64(bit_iter: &mut Iter<bool>, encoding_size: u8) -> Result<usize> {
140    let mut begin: u8 = 0;
141    let mut x: usize = 0;
142    loop {
143        begin += 1;
144        if begin > encoding_size {
145            break;
146        }
147        let bit = bit_iter.next();
148        if bit.is_none() {
149            return Err(ReadError {
150                message: "wrong s6 format - missing bits".to_string(),
151            });
152        }
153        x = (x << 1) | bit.unwrap().clone() as usize;
154    }
155    Ok(x)
156}
snark_tool/service/io/reader_s6.rs

snark_tool/service/io/
reader_s6.rs
