rs_graph/dimacs/
graph.rs

1// Copyright (c) 2016-2022 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
17use super::{read_dimacs, Error as DimacsError};
18
19use crate::{Buildable, Builder};
20
21use std::cmp::{max, min};
22use std::collections::HashSet;
23use std::f64;
24use std::fs;
25use std::io::{BufRead, BufReader};
26
27// Possible metrics
28#[derive(Copy, Clone, PartialEq, Debug)]
29pub enum Metric {
30    // infinity norm,
31    LINF,
32    // l_p norm
33    L(f64),
34    // squared euclidean norm
35    L2S,
36}
37
38// Problem parameters
39#[derive(PartialEq, Debug)]
40pub enum Param {
41    // edge included only if length greater than or equal to this
42    MinLength(f64),
43    // edge included only if length less than or equal to this
44    MaxLength(f64),
45}
46
47/// Read DIMACS file.
48///
49/// - `fname` is the name of the file to be read
50/// - `weights` is the array of node weights
51pub fn read<G>(fname: &str) -> Result<(G, Vec<f64>), DimacsError>
52where
53    G: Buildable,
54{
55    read_from_buf(&mut BufReader::new(fs::File::open(fname)?))
56}
57
58/// Read DIMACS file from a buffered reader.
59///
60/// - `buf` the buffer with the file content
61pub fn read_from_buf<R, G>(buf: &mut R) -> Result<(G, Vec<f64>), DimacsError>
62where
63    R: BufRead,
64    G: Buildable,
65{
66    let mut g = G::new_builder();
67    let mut weights = vec![];
68    let mut nnodes = 0;
69    let mut nedges = 0;
70    let mut gnodes = vec![];
71    let mut nodes = HashSet::new();
72    let mut edges = HashSet::new();
73    let mut dim = 0;
74    let mut metric = None;
75    let mut vertices = vec![];
76    let mut minlength = None;
77    let mut maxlength = None;
78
79    let mut start = true;
80    read_dimacs(buf, &mut |d, toks| {
81        if start {
82            if d != 'p' {
83                return Err(DimacsError::Format {
84                    line: toks.line,
85                    msg: format!("expected problem line starting with 'p', got: {}", d),
86                });
87            }
88            let edge = toks.next().unwrap_or("end of line");
89            if edge != "edge" {
90                return Err(DimacsError::Format {
91                    line: toks.line,
92                    msg: format!("expected 'edge' in p line, got: {}", edge),
93                });
94            }
95            nnodes = toks.number()?;
96            nedges = toks.number()?;
97            toks.end()?;
98
99            g.reserve(nnodes, nedges);
100            gnodes = g.add_nodes(nnodes);
101            weights.clear();
102            weights.resize(nnodes, 0.0);
103
104            start = false;
105        } else {
106            match d {
107                'n' => {
108                    let id: usize = toks.number()?;
109                    let val = toks.number()?;
110                    toks.end()?;
111                    if id < 1 || id > nnodes {
112                        return Err(DimacsError::Format {
113                            line: toks.line,
114                            msg: format!("invalid node id {} (must be <= {})", id, nnodes),
115                        });
116                    }
117                    if !nodes.insert(id) {
118                        return Err(DimacsError::Format {
119                            line: toks.line,
120                            msg: format!("duplicate node id {}", id),
121                        });
122                    }
123                    weights[id - 1] = val;
124                }
125                'e' => {
126                    let u: usize = toks.number()?;
127                    let v: usize = toks.number()?;
128                    toks.end()?;
129                    if u < 1 || u > nnodes {
130                        return Err(DimacsError::Format {
131                            line: toks.line,
132                            msg: format!("invalid node id {} in edge", u),
133                        });
134                    }
135                    if v < 1 || v > nnodes {
136                        return Err(DimacsError::Format {
137                            line: toks.line,
138                            msg: format!("invalid node id {} in edge", v),
139                        });
140                    }
141                    if u == v {
142                        return Err(DimacsError::Format {
143                            line: toks.line,
144                            msg: format!("invalid loop ({},{}) in edge", u, u),
145                        });
146                    }
147                    if !edges.insert((min(u, v), max(u, v))) {
148                        return Err(DimacsError::Format {
149                            line: toks.line,
150                            msg: format!("duplicate edge ({},{})", u, v),
151                        });
152                    }
153                    g.add_edge(gnodes[u - 1], gnodes[v - 1]);
154                }
155                'd' => {
156                    let d: usize = toks.number()?;
157                    let m = match toks.next() {
158                        Some("LINF") => Metric::LINF,
159                        Some("L2S") => Metric::L2S,
160                        Some(m) if !m.is_empty() && m.starts_with('L') => {
161                            let p: f64 = match m[1..].parse() {
162                                Ok(x) => x,
163                                Err(_) => {
164                                    return Err(DimacsError::Format {
165                                        line: toks.line,
166                                        msg: "invalid norm".to_string(),
167                                    });
168                                }
169                            };
170                            if p <= 0.0 {
171                                return Err(DimacsError::Format {
172                                    line: toks.line,
173                                    msg: format!("p of p-norm must be > 0 (got: {})", p),
174                                });
175                            }
176                            Metric::L(p)
177                        }
178                        Some(_) => {
179                            return Err(DimacsError::Format {
180                                line: toks.line,
181                                msg: "invalid norm".to_string(),
182                            });
183                        }
184                        None => {
185                            return Err(DimacsError::Format {
186                                line: toks.line,
187                                msg: "missing norm".to_string(),
188                            });
189                        }
190                    };
191                    toks.end()?;
192
193                    if d < 1 {
194                        return Err(DimacsError::Format {
195                            line: toks.line,
196                            msg: format!("invalid dimension {} < 1", d),
197                        });
198                    }
199                    if dim > 0 {
200                        return Err(DimacsError::Format {
201                            line: toks.line,
202                            msg: "duplicate dimension".to_string(),
203                        });
204                    }
205
206                    dim = d;
207                    metric = Some(m);
208                    vertices.reserve(nnodes);
209                }
210                'v' => {
211                    if dim == 0 {
212                        return Err(DimacsError::Format {
213                            line: toks.line,
214                            msg: "missing dimension line before vertex line".to_string(),
215                        });
216                    }
217
218                    let mut vs: Vec<f64> = Vec::new();
219                    for _ in 0..dim {
220                        vs.push(toks.number()?);
221                    }
222                    toks.end()?;
223
224                    if dim != vs.len() {
225                        return Err(DimacsError::Format {
226                            line: toks.line,
227                            msg: format!("vertex line has too many entries {} (expected: {})", vs.len(), dim),
228                        });
229                    }
230
231                    vertices.push(vs);
232                }
233                'x' => {
234                    let par = toks.str()?;
235                    let l: f64 = toks.number()?;
236                    toks.end()?;
237                    match par {
238                        "MINLENGTH" => {
239                            if minlength.is_some() {
240                                return Err(DimacsError::Format {
241                                    line: toks.line,
242                                    msg: "duplicate parameter MINLENGTH".to_string(),
243                                });
244                            }
245                            minlength = Some(l)
246                        }
247                        "MAXLENGTH" => {
248                            if maxlength.is_some() {
249                                return Err(DimacsError::Format {
250                                    line: toks.line,
251                                    msg: "duplicate parameter MAXLENGTH".to_string(),
252                                });
253                            }
254                            maxlength = Some(l)
255                        }
256                        _ => {
257                            return Err(DimacsError::Format {
258                                line: toks.line,
259                                msg: format!("unknown parameter {}", par),
260                            });
261                        }
262                    };
263                }
264                _ => {
265                    return Err(DimacsError::Format {
266                        line: toks.line,
267                        msg: format!("invalid command {}", d),
268                    });
269                }
270            }
271        }
272
273        Ok(())
274    })?;
275
276    // verify consistency with vertex data
277    if dim > 0 {
278        let metric = metric.unwrap();
279        let minl = match minlength {
280            Some(l) => l,
281            _ => 0.0,
282        };
283        let maxl = match maxlength {
284            Some(l) => l,
285            _ => f64::INFINITY,
286        };
287        for u in 0..nnodes {
288            for v in u + 1..nnodes {
289                let d = dist(&vertices[u], &vertices[v], metric);
290                // invalid edges might have infinite lengths
291                if !edges.contains(&(u + 1, v + 1)) {
292                    // edge does not exist, the distance should be invalid
293                    if d >= minl && d <= maxl {
294                        return Err(DimacsError::Format {
295                            line: 0,
296                            msg: format!("edge ({},{}) should be contained in the graph", u, v),
297                        });
298                    }
299                } else {
300                    // edge exists, the distance must be valid
301                    if d < minl {
302                        return Err(DimacsError::Format {
303                            line: 0,
304                            msg: format!("edge ({},{}) should not be contained in the graph (too short)", u, v),
305                        });
306                    }
307                    if d > maxl {
308                        return Err(DimacsError::Format {
309                            line: 0,
310                            msg: format!("edge ({},{}) should not be contained in the graph (too long)", u, v),
311                        });
312                    }
313                }
314            }
315        }
316    }
317
318    Ok((g.into_graph(), weights))
319}
320
321fn dist(x: &[f64], y: &[f64], metric: Metric) -> f64 {
322    let mut d: f64 = 0.0;
323    match metric {
324        Metric::LINF => {
325            for i in 0..x.len() {
326                d = f64::max(d, f64::abs(x[i] - y[i]));
327            }
328        }
329        Metric::L2S => {
330            for i in 0..x.len() {
331                d += (x[i] - y[i]) * (x[i] - y[i]);
332            }
333        }
334        Metric::L(p) => {
335            for i in 0..x.len() {
336                d += (x[i] - y[i]).abs().powf(p);
337            }
338            d = d.powf(1.0 / p);
339        }
340    }
341    d
342}
343
344#[cfg(test)]
345mod tests {
346    use super::read_dimacs;
347    use super::read_from_buf;
348    use crate::traits::{FiniteGraph, IndexGraph, Undirected};
349    use crate::LinkedListGraph;
350    use std::io::Cursor;
351
352    #[test]
353    fn test_read() {
354        let file = "
355c some comment
356
357p edge 12 5
358";
359        read_dimacs(&mut Cursor::new(file), &mut |c, toks| {
360            assert_eq!(c, 'p');
361            assert_eq!(toks.next(), Some("edge"));
362            assert_eq!(toks.number::<usize>().unwrap(), 12);
363            assert_eq!(toks.number::<usize>().unwrap(), 5);
364            assert_eq!(toks.next(), None);
365            Ok(())
366        })
367        .unwrap();
368    }
369
370    #[test]
371    fn parse_file_test() {
372        let file = "c this is a test file
373
374p edge 6 9
375  n 1 12
376n 6 42.23
377
378c there might be empty lines
379
380e 1 4
381e 1 5
382e 1 6
383e 2 4
384e 2 5
385e 2 6
386e 3 4
387e 3 5
388e 3 6
389
390d 2 L2
391v 1 1
392v 1 2
393v 1 3
394v 10 1
395v 10 2
396v 10 3
397
398x MINLENGTH 5
399x MAXLENGTH 100
400
401c end of the file
402";
403        let (g, weights) = read_from_buf::<_, LinkedListGraph>(&mut Cursor::new(file)).unwrap();
404
405        assert_eq!(g.num_nodes(), 6);
406        assert_eq!(g.num_edges(), 9);
407
408        for u in 0..3 {
409            let mut vs: Vec<_> = g.neighs(g.id2node(u)).map(|(_, v)| g.node_id(v)).collect();
410            vs.sort();
411            assert_eq!(vs, vec![3, 4, 5]);
412        }
413
414        for v in 3..6 {
415            let mut vs: Vec<_> = g.neighs(g.id2node(v)).map(|(_, v)| g.node_id(v)).collect();
416            vs.sort();
417            assert_eq!(vs, vec![0, 1, 2]);
418        }
419
420        for u in g.nodes() {
421            match (g.node_id(u), weights[g.node_id(u)]) {
422                (0, w) => assert_eq!(w, 12.0),
423                (5, w) => assert_eq!(w, 42.23),
424                (_, w) => assert_eq!(w, 0.0),
425            }
426        }
427    }
428}
rs_graph/dimacs/graph.rs

rs_graph/dimacs/
graph.rs
