rs_graph/dimacs/
mod.rs

1// Copyright (c) 2015-2021, 2023 Frank Fischer <frank-fischer@shadow-soft.de>
2//
3// This program is free software: you can redistribute it and/or
4// modify it under the terms of the GNU General Public License as
5// published by the Free Software Foundation, either version 3 of the
6// License, or (at your option) any later version.
7//
8// This program is distributed in the hope that it will be useful, but
9// WITHOUT ANY WARRANTY; without even the implied warranty of
10// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11// General Public License for more details.
12//
13// You should have received a copy of the GNU General Public License
14// along with this program.  If not, see  <http://www.gnu.org/licenses/>
15//
16
17//! Reading files in DIMACS format.
18
19pub mod max;
20pub mod min;
21
22pub mod graph;
23pub use self::graph::read as read_graph;
24
25use std::error;
26use std::fmt;
27use std::io::{self, BufRead, BufReader, Read};
28use std::str::{FromStr, SplitWhitespace};
29
30/// Error when reading a file in DIMACS format.
31#[derive(Debug)]
32pub enum Error {
33    Io(io::Error),
34    Format { line: usize, msg: String },
35    Data { line: usize, msg: String },
36}
37
38impl From<io::Error> for Error {
39    fn from(err: io::Error) -> Self {
40        Error::Io(err)
41    }
42}
43
44impl fmt::Display for Error {
45    fn fmt(&self, fmt: &mut fmt::Formatter) -> std::result::Result<(), fmt::Error> {
46        use self::Error::*;
47        match self {
48            Io(err) => err.fmt(fmt),
49            Format { line, msg } => write!(fmt, "Format error on line {}: {}", line, msg),
50            Data { line, msg } => write!(fmt, "Data error on line {}: {}", line, msg),
51        }
52    }
53}
54
55impl error::Error for Error {
56    fn cause(&self) -> Option<&dyn error::Error> {
57        match self {
58            Error::Io(err) => Some(err),
59            _ => None,
60        }
61    }
62}
63
64pub type Result<T> = std::result::Result<T, Error>;
65
66pub struct DimacsReader<R: Read> {
67    io: BufReader<R>,
68
69    line: String,
70    line_number: usize,
71}
72
73impl<R: Read> DimacsReader<R> {
74    pub fn new(reader: R) -> Self {
75        DimacsReader {
76            io: BufReader::new(reader),
77            line: String::new(),
78            line_number: 0,
79        }
80    }
81
82    fn read_line(&mut self) -> Result<Option<Tokens>> {
83        let line = &mut self.line;
84        loop {
85            line.clear();
86            if self.io.read_line(line)? == 0 {
87                return Ok(None);
88            }
89
90            self.line_number += 1;
91            for (i, c) in line.char_indices() {
92                if char::is_whitespace(c) {
93                    continue;
94                }
95                if c == 'c' || c == '\n' {
96                    break;
97                }
98                return Ok(Some(Tokens {
99                    it: line[i..].split_whitespace(),
100                    line: self.line_number,
101                }));
102            }
103        }
104    }
105
106    // Expect a line with the given descriptor.
107    //
108    // If the next line does not have this descriptor, an error is returned.
109    // Otherwise the *remaining* tokens are returned.
110    fn expect_line(&mut self, descriptor: char) -> Result<Tokens> {
111        let line_number = self.line_number;
112        let mut toks = self.read_line()?.ok_or_else(|| Error::Format {
113            line: line_number,
114            msg: format!("unexpected end of file, expected '{}' line", descriptor),
115        })?;
116        match toks.next() {
117            Some(d) if d.len() == 1 && d.starts_with(descriptor) => Ok(toks),
118            Some(d) => Err(Error::Format {
119                line: line_number,
120                msg: format!("unexpected line, expected '{}', got '{}'", descriptor, d),
121            }),
122            None => Err(Error::Format {
123                line: line_number,
124                msg: "unexpected empty line".to_string(),
125            }),
126        }
127    }
128
129    // Read the next line with one of the given descriptors.
130    //
131    // If the next line does not have this descriptor, `Ok(None)`.
132    // Otherwise the descriptor and the *remaining* tokens are returned.
133    fn read_one_line_of(&mut self, descriptors: &[&str]) -> Result<Option<(&str, Tokens)>> {
134        let line_number = self.line_number;
135        if let Some(mut toks) = self.read_line()? {
136            match toks.next() {
137                Some(d) if descriptors.iter().any(|&desc| d.starts_with(desc)) => Ok(Some((d, toks))),
138                Some(d) => Err(Error::Format {
139                    line: line_number,
140                    msg: format!(
141                        "unexpected line, expected on of '{}', got '{}'",
142                        descriptors.join("', '"),
143                        d
144                    ),
145                }),
146                None => Err(Error::Format {
147                    line: line_number,
148                    msg: "unexpected empty line".to_string(),
149                }),
150            }
151        } else {
152            Ok(None)
153        }
154    }
155}
156
157/// Iterates over the tokens in a line.
158pub struct Tokens<'a> {
159    it: SplitWhitespace<'a>,
160    pub line: usize,
161}
162
163impl<'a> Iterator for Tokens<'a> {
164    type Item = &'a str;
165
166    fn next(&mut self) -> Option<&'a str> {
167        self.it.next()
168    }
169}
170
171impl<'a> Tokens<'a> {
172    /// Return an error if the next token is not the given token.
173    pub fn expect(&mut self, tok: &str) -> Result<()> {
174        let nxt = self.str()?;
175        if nxt == tok {
176            Ok(())
177        } else {
178            Err(Error::Format {
179                line: self.line,
180                msg: format!("expected '{}', got '{}", tok, nxt),
181            })
182        }
183    }
184
185    /// Return an error if the next token is not the given token list.
186    pub fn expect_one_of(&mut self, toks: &[&str]) -> Result<()> {
187        let nxt = self.str()?;
188        if toks.iter().any(|&tok| tok == nxt) {
189            Ok(())
190        } else {
191            Err(Error::Format {
192                line: self.line,
193                msg: format!("expected one of '{}', got '{}", toks.join("', '"), nxt),
194            })
195        }
196    }
197
198    /// Returns the next token as `&str`.
199    pub fn str(&mut self) -> Result<&'a str> {
200        self.it.next().ok_or_else(|| Error::Format {
201            line: self.line,
202            msg: "expected token".to_string(),
203        })
204    }
205
206    /// Returns the next token converted to a number.
207    pub fn number<T>(&mut self) -> Result<T>
208    where
209        T: FromStr,
210        T::Err: fmt::Display,
211    {
212        self.it
213            .next()
214            .ok_or_else(|| Error::Format {
215                line: self.line,
216                msg: "expected number".to_string(),
217            })?
218            .parse()
219            .map_err(|e| Error::Format {
220                line: self.line,
221                msg: format!("{}", e),
222            })
223    }
224
225    /// Ensures that there is no next token.
226    pub fn end(&mut self) -> Result<()> {
227        if let Some(s) = self.it.next() {
228            Err(Error::Format {
229                line: self.line,
230                msg: format!("unexpected token at end of line: {}", s),
231            })
232        } else {
233            Ok(())
234        }
235    }
236}
237
238/// Read a DIMACS file.
239///
240/// - `fin` is the buffered reader with the file content
241/// - `f` is callback called once for each non-comment line with
242///   `(c,toks)`, where `c` is the descripter of the line and `toks`
243///   an iterator over the tokens
244fn read_dimacs<R, F>(fin: &mut R, f: &mut F) -> Result<()>
245where
246    R: io::BufRead,
247    F: FnMut(char, &mut Tokens) -> Result<()>,
248{
249    let mut nline = 0;
250    let mut line = String::new();
251
252    while {
253        line.clear();
254        fin.read_line(&mut line)
255    }? > 0
256    {
257        nline += 1;
258        let mut it = line.chars();
259        while let Some(c) = it.next() {
260            match c {
261                _ if char::is_whitespace(c) => continue,
262                'c' | '\n' => break,
263                _ => {
264                    let mut tok = Tokens {
265                        it: it.as_str().split_whitespace(),
266                        line: nline,
267                    };
268                    f(c, &mut tok)?;
269                    break;
270                }
271            }
272        }
273    }
274
275    Ok(())
276}
rs_graph/dimacs/mod.rs

rs_graph/dimacs/
mod.rs
