rs_graph/steinlib/
parser.rs

1/*
2 * Copyright (c) 2017-2022 Frank Fischer <frank-fischer@shadow-soft.de>
3 *
4 * This program is free software: you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation, either version 3 of the
7 * License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
16 */
17
18use super::Instance;
19
20use crate::{Buildable, Builder, IndexGraph};
21
22use std::error;
23use std::fmt;
24use std::fs;
25use std::io;
26
27use super::EdgeAttr;
28use std::collections::HashMap;
29
30use peg;
31
32/// Error raised by the parser.
33pub type ParseError = peg::error::ParseError<peg::str::LineCol>;
34
35//include!(concat!(env!("OUT_DIR"), "/parser.rs"));
36peg::parser! {
37
38    grammar steinlib_parser() for str {
39      pub(super) rule doc() -> Vec<Section>
40        = ws()* i("33D32945") ws()+ i("STP") ws()+ i("File,") ws()+ i("STP") ws()+ i("Format") ws()+ i("Version") ws()+ i("1.") "0"+ nl()+
41          secs:(
42             comment_section() /
43              graph_section() /
44              terminals_section() /
45              coordinates_section() /
46              drawing_section()
47              ) ** (nl()*)
48           nl()*
49           i("EOF") nl()* ![_]
50           { secs }
51
52      pub(super) rule comment_section() -> Section
53        = i("SECTION") ws()+ i("Comment") nl()+ h:comment_entry() ** (nl()*) nl()* i("END") nl()
54           {
55             Section::Comment(h.into_iter().collect())
56           }
57
58      rule comment_entry() -> (String, String)
59        = ws()* key:$(['a'..='z' | 'A' ..= 'Z']+) ws()+ val:(quoted() / word()) nl()
60          {
61             (key.to_string(), val)
62          }
63
64      pub(super) rule graph_section() -> Section
65        = i("SECTION") ws()+ i("Graph") nl()+
66            g:(edge_line() / arc_line() / node_count() / edge_count() / arc_count()) ** (nl()*) nl()*
67          i("END") nl() { Section::Graph(g) }
68
69      rule edge_line() -> GraphLine
70        = i("E") ws()+ u:int() ws()+ v:int() ws()+ w:float() nl() { GraphLine::Edge(u, v, w) }
71
72      rule arc_line() -> GraphLine
73        = i("A") ws()+ u:int() ws()+ v:int() ws()+ w:float() nl() { GraphLine::Arc(u, v, w) }
74
75      rule node_count() -> GraphLine
76        = i("Nodes") ws()+ n:int() nl() { GraphLine::NumNodes(n) }
77
78      rule edge_count() -> GraphLine
79        = i("Edges") ws()+ n:int() nl() { GraphLine::NumEdges(n) }
80
81      rule arc_count() -> GraphLine
82        = i("Arcs") ws()+ n:int() nl() { GraphLine::NumArcs(n) }
83
84
85      pub(super) rule terminals_section() -> Section
86        = i("SECTION") ws()+ i("Terminals")
87          nl()+
88          i("Terminals") ws()+ n:int()
89           nl()+
90          t:terminal() ** (nl()*)
91           nl()*
92           i("END") nl()
93           { Section::Terminals(n, t) }
94
95      rule terminal() -> usize
96        = i("T") ws()* n:int() nl() { n }
97
98
99      pub(super) rule coordinates_section() -> Section
100        = i("SECTION") ws()+ i("Coordinates") nl()
101          coords:coordinate() ** (nl()*)
102           nl()*
103           i("END") nl()
104           { Section::Coordinates(coords) }
105
106      rule coordinate() -> (usize,Vec<f64>)
107        = ws()* beg:position!() i("D")+ end:position!() ws()+ u:int() ws()+ nums:float() **<{end-beg}> (ws()+) nl() { (u,nums) }
108
109
110      pub(super) rule drawing_section() -> Section
111        = i("SECTION") ws()+ i("Drawing") nl()
112          d:arc_drawing() ** (nl()*)
113           nl()*
114           i("END") nl()
115           { Section::Drawing(d) }
116
117      rule arc_drawing() -> (usize, usize, Vec<EdgeAttr>)
118        = ['a' | 'A' | 'e' | 'E'] ws()+ u:int() ws()+ v:int() ws()+ attrs:arc_attrs() ** (ws()+) nl()
119          { (u, v, attrs) }
120
121      rule arc_attrs() -> EdgeAttr
122        = a:$(i("bl") / i("br"))
123          {
124             match a {
125                "bl" | "bL" | "Bl" | "BL" => EdgeAttr::BendLeft,
126                _ => EdgeAttr::BendRight
127            }
128          }
129
130      rule int() -> usize
131        = n:$(['-' | '+']? digit()+) { n.parse().unwrap() }
132
133      rule float() -> f64
134        = n:$(['-' | '+']? (digit()+ "."? digit()* / "." digit()+) (['e' | 'E'] ['-' | '+']? digit()+)?) { n.parse().unwrap() }
135
136      rule digit()
137        = ['0' ..= '9']
138
139      rule quoted() -> String
140        = "\"" s:$(( "\\" [_] / !['\\' | '"'] [_] )*) "\"" { s.to_string() }
141
142      rule word() -> String
143        = s:$((![' ' | '\t' | '\r' | '\n'] [_])+) { s.to_string() }
144
145      rule nl()
146        = quiet!{ws()* ("#" (!['\n'] [_])*)? "\n" ws()*}
147
148      rule ws()
149        = quiet!{[' ' | '\t' | '\r']}
150
151      rule i(literal: &'static str)
152        = input:$([_]*<{literal.len()}>)
153          {? if input.eq_ignore_ascii_case(literal) { Ok(()) } else { Err(literal) } }
154    }
155}
156
157#[derive(Debug)]
158pub enum SteinlibError {
159    Io(io::Error),
160    Parse(ParseError),
161    NoMixed,
162    UnmatchedDimension { dim: usize },
163    UnmatchedTerminalCount { got: usize, expected: usize },
164    InvalidLoop { node: usize },
165    Format { msg: String },
166}
167
168impl From<io::Error> for SteinlibError {
169    fn from(err: io::Error) -> Self {
170        SteinlibError::Io(err)
171    }
172}
173
174impl From<ParseError> for SteinlibError {
175    fn from(err: ParseError) -> Self {
176        SteinlibError::Parse(err)
177    }
178}
179
180impl fmt::Display for SteinlibError {
181    fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
182        use self::SteinlibError::*;
183        match self {
184            Io(err) => err.fmt(fmt),
185            Parse(err) => err.fmt(fmt),
186            NoMixed => write!(fmt, "Mixed graphs are not supported"),
187            UnmatchedDimension { dim } => write!(
188                fmt,
189                "Dimension of coordinates for node {} differs from previous dimension",
190                dim
191            ),
192            UnmatchedTerminalCount { got, expected } => write!(
193                fmt,
194                "Unexpected number of terminals (expected: {}, got: {})",
195                expected, got
196            ),
197            InvalidLoop { node } => write!(fmt, "Loops are not allowed (got ({},{}))", node, node),
198            Format { msg } => write!(fmt, "Format error: {}", msg),
199        }
200    }
201}
202
203impl error::Error for SteinlibError {
204    fn cause(&self) -> Option<&dyn error::Error> {
205        match self {
206            SteinlibError::Io(err) => Some(err),
207            SteinlibError::Parse(err) => Some(err),
208            _ => None,
209        }
210    }
211}
212
213#[derive(Debug, PartialEq)]
214pub enum GraphLine {
215    Edge(usize, usize, f64),
216    Arc(usize, usize, f64),
217    NumNodes(usize),
218    NumEdges(usize),
219    NumArcs(usize),
220}
221
222#[derive(Debug, PartialEq)]
223pub enum Section {
224    Comment(HashMap<String, String>),
225    Graph(Vec<GraphLine>),
226    Coordinates(Vec<(usize, Vec<f64>)>),
227    Terminals(usize, Vec<usize>),
228    Drawing(Vec<(usize, usize, Vec<EdgeAttr>)>),
229}
230
231pub fn read<G>(fname: &str) -> Result<Instance<G>, SteinlibError>
232where
233    G: for<'a> IndexGraph + Buildable,
234{
235    let mut f = fs::File::open(fname)?;
236    read_from_buf(&mut f)
237}
238
239/// Read `SteinLib` file from a buffered reader.
240///
241/// - `buf` the buffer with the file content
242pub fn read_from_buf<G, R>(buf: &mut R) -> Result<Instance<G>, SteinlibError>
243where
244    R: io::Read,
245    G: IndexGraph + Buildable,
246{
247    let data = {
248        let mut s = String::new();
249        buf.read_to_string(&mut s)?;
250        steinlib_parser::doc(&s)?
251    };
252
253    let mut b = G::Builder::new();
254
255    let mut nodes = vec![];
256    let mut nodecoords = vec![];
257    let mut nedges = 0;
258    let mut narcs = 0;
259    let mut weights = vec![];
260    let mut edgeattrs = vec![];
261    let mut edges = HashMap::new();
262
263    for sec in data {
264        match sec {
265            Section::Comment(_) => (),
266            Section::Terminals(n, terms) => {
267                if n != terms.len() {
268                    return Err(SteinlibError::UnmatchedTerminalCount {
269                        got: terms.len(),
270                        expected: n,
271                    });
272                }
273            }
274            Section::Graph(graph_lines) => {
275                let mut cntarcs = 0;
276                let mut cntedges = 0;
277                for line in graph_lines {
278                    match line {
279                        GraphLine::NumNodes(n) => {
280                            if !nodes.is_empty() {
281                                return Err(SteinlibError::Format {
282                                    msg: "Duplicate 'Nodes' keyword".to_string(),
283                                });
284                            }
285                            nodes.extend_from_slice(&b.add_nodes(n));
286                            nodecoords.resize(nodes.len(), vec![]);
287                        }
288                        GraphLine::NumEdges(m) => {
289                            if nedges > 0 {
290                                return Err(SteinlibError::Format {
291                                    msg: "Duplicate 'Edges' keyword".to_string(),
292                                });
293                            } else if narcs > 0 {
294                                return Err(SteinlibError::NoMixed);
295                            }
296                            nedges = m;
297                            b.reserve(0, m);
298                        }
299                        GraphLine::NumArcs(m) => {
300                            if narcs > 0 {
301                                return Err(SteinlibError::Format {
302                                    msg: "Duplicate 'Arcs' keyword".to_string(),
303                                });
304                            } else if nedges > 0 {
305                                return Err(SteinlibError::NoMixed);
306                            }
307                            narcs = m;
308                            b.reserve(0, m);
309                        }
310                        GraphLine::Edge(u, v, w) => {
311                            if nedges == 0 {
312                                return Err(SteinlibError::Format {
313                                    msg: "Midding 'Edges' line before first edge".to_string(),
314                                });
315                            } else if nedges <= cntedges {
316                                return Err(SteinlibError::Format {
317                                    msg: format!("Too many edges (expected: {})", nedges),
318                                });
319                            } else if u == v {
320                                return Err(SteinlibError::InvalidLoop { node: u });
321                            } else if u < 1 || u > nodes.len() {
322                                return Err(SteinlibError::Format {
323                                    msg: format!("Invalid node in edge: {} (must be in 1..{})", u, nodes.len()),
324                                });
325                            } else if v < 1 || v > nodes.len() {
326                                return Err(SteinlibError::Format {
327                                    msg: format!("Invalid node in edge: {} (must be in 1..{})", v, nodes.len()),
328                                });
329                            }
330                            b.add_edge(nodes[u - 1], nodes[v - 1]);
331                            weights.push(w);
332                            edges.insert((u, v), cntedges);
333                            cntedges += 1;
334                        }
335                        GraphLine::Arc(u, v, w) => {
336                            if narcs == 0 {
337                                return Err(SteinlibError::Format {
338                                    msg: "Midding 'Arcs' line before first arc".to_string(),
339                                });
340                            } else if narcs <= cntarcs {
341                                return Err(SteinlibError::Format {
342                                    msg: format!("Too many arcs (expected: {})", narcs),
343                                });
344                            } else if u == v {
345                                return Err(SteinlibError::InvalidLoop { node: u });
346                            } else if u < 1 || u > nodes.len() {
347                                return Err(SteinlibError::Format {
348                                    msg: format!("Invalid node in arc: {} (must be in 1..{})", u, narcs),
349                                });
350                            } else if v < 1 || v > nodes.len() {
351                                return Err(SteinlibError::Format {
352                                    msg: format!("Invalid node in arc: {} (must be in 1..{})", v, narcs),
353                                });
354                            }
355                            b.add_edge(nodes[u - 1], nodes[v - 1]);
356                            weights.push(w);
357                            edges.insert((u, v), cntedges);
358                            cntarcs += 1;
359                        }
360                    }
361                }
362
363                if nedges != cntedges {
364                    return Err(SteinlibError::Format {
365                        msg: format!("Wrong number of edges (found: {}, expected: {})", cntedges, nedges),
366                    });
367                }
368                if narcs != cntarcs {
369                    return Err(SteinlibError::Format {
370                        msg: format!("Wrong number of arcs (found: {}, expected: {})", cntarcs, narcs),
371                    });
372                }
373            }
374            Section::Coordinates(coords) => {
375                let mut dim = 0;
376                for (u, coord) in coords {
377                    if u < 1 || u > nodes.len() {
378                        return Err(SteinlibError::Format {
379                            msg: format!("Invalid node in coordinate: {} (must be in 1..{})", u, narcs),
380                        });
381                    }
382                    if dim > 0 && coord.len() != dim {
383                        return Err(SteinlibError::UnmatchedDimension { dim: u });
384                    }
385                    dim = coord.len();
386                    nodecoords[u - 1] = coord;
387                }
388            }
389            Section::Drawing(drawings) => {
390                edgeattrs.resize(nedges, vec![]);
391                for (u, v, attrs) in drawings {
392                    if let Some(&e) = edges.get(&(u, v)) {
393                        edgeattrs[e] = attrs;
394                    } else {
395                        return Err(SteinlibError::Format {
396                            msg: format!("Unknown edge in drawing: ({},{})", u, v),
397                        });
398                    }
399                }
400            }
401        };
402    }
403
404    Ok(Instance {
405        graph: b.into_graph(),
406        weights,
407        coordinates: nodecoords,
408        edgeattrs,
409    })
410}
411
412#[cfg(test)]
413mod tests {
414
415    use super::steinlib_parser::doc as steinlib;
416    use super::steinlib_parser::{
417        comment_section, coordinates_section, drawing_section, graph_section, terminals_section,
418    };
419    use super::{read_from_buf, GraphLine, Section};
420    use crate::steinlib::EdgeAttr;
421    use crate::traits::{FiniteDigraph, FiniteGraph, IndexGraph};
422    use crate::LinkedListGraph;
423
424    #[test]
425    fn test_graph_section() {
426        let r = graph_section("SECTION Graph\n  NODES 5\n  ARCS 2\n   E 1 2 3 # Kante bla\n  A 4 5 6\nEND\n");
427        assert_eq!(
428            r,
429            Ok(Section::Graph(vec![
430                GraphLine::NumNodes(5),
431                GraphLine::NumArcs(2),
432                GraphLine::Edge(1, 2, 3.0),
433                GraphLine::Arc(4, 5, 6.0),
434            ]))
435        );
436    }
437
438    #[test]
439    fn test_coordinates_section() {
440        let r = coordinates_section("SECTION coordinates\n  D 1 5\n  DD 2 2 3\n \n  DDD 3 1  2 3 # Kante bla\nEND\n");
441        assert_eq!(
442            r,
443            Ok(Section::Coordinates(vec![
444                (1, vec![5.0]),
445                (2, vec![2.0, 3.0]),
446                (3, vec![1.0, 2.0, 3.0]),
447            ]))
448        );
449    }
450
451    #[test]
452    fn test_comment_section() {
453        let r = comment_section("SECTION comment\n  Name \"blaa\" \n\n Creator   \"Me the king\"\nEND\n");
454        assert_eq!(
455            r,
456            Ok(Section::Comment(
457                [
458                    ("Name".to_string(), "blaa".to_string()),
459                    ("Creator".to_string(), "Me the king".to_string())
460                ]
461                .iter()
462                .cloned()
463                .collect()
464            ))
465        );
466    }
467
468    #[test]
469    fn test_terminals_section() {
470        let r = terminals_section("SECTION Terminals\n  TERMINALS  2 \n\n  T 1 \n T 2 \nEND\n");
471        assert_eq!(r, Ok(Section::Terminals(2, vec![1, 2])));
472    }
473
474    #[test]
475    fn test_drawing_section() {
476        let r = drawing_section("SECTION Drawing\n  E 1 2 bl \n E 3 4 br \nEND\n");
477        assert_eq!(
478            r,
479            Ok(Section::Drawing(vec![
480                (1, 2, vec![EdgeAttr::BendLeft]),
481                (3, 4, vec![EdgeAttr::BendRight]),
482            ]))
483        )
484    }
485
486    #[test]
487    fn test_parser() {
488        let file = "33D32945 STP File, STP Format Version 1.0
489   SECTION Comment
490   Name    \"Odd Wheel\"
491   Creator \"T. Koch, A. Martin and S. Voss\"
492   Remark  \"Example used to describe the STP data format\"
493   END
494   SECTION Graph
495   Nodes 7
496   Edges 9
497   E 1 2 1
498   E 1 4 1
499   E 1 6 1
500   E 2 3 1
501   E 3 4 1
502   E 4 5 1
503   E 5 6 1
504   E 6 7 1
505   E 7 2 1
506   END
507
508
509   SECTION Terminals
510   Terminals 4
511   T 1
512   T 3
513   T 5
514   T 7
515   END
516
517   SECTION Coordinates
518   DD 1  80 50
519   DD 2  30 50
520   DD 3  55  5
521   DD 4 105  5
522   DD 5 130 50
523   DD 6 105 95
524   DD 7  55 95
525   END
526
527   SECTION Drawing
528   E 1 2 bl
529   E 6 7 BR
530   END
531
532   EOF";
533
534        let r = steinlib(file);
535        assert_eq!(
536            r,
537            Ok(vec![
538                Section::Comment(
539                    [
540                        ("Name".to_string(), "Odd Wheel".to_string()),
541                        ("Creator".to_string(), "T. Koch, A. Martin and S. Voss".to_string()),
542                        (
543                            "Remark".to_string(),
544                            "Example used to describe the STP data format".to_string(),
545                        ),
546                    ]
547                    .iter()
548                    .cloned()
549                    .collect(),
550                ),
551                Section::Graph(vec![
552                    GraphLine::NumNodes(7),
553                    GraphLine::NumEdges(9),
554                    GraphLine::Edge(1, 2, 1.0),
555                    GraphLine::Edge(1, 4, 1.0),
556                    GraphLine::Edge(1, 6, 1.0),
557                    GraphLine::Edge(2, 3, 1.0),
558                    GraphLine::Edge(3, 4, 1.0),
559                    GraphLine::Edge(4, 5, 1.0),
560                    GraphLine::Edge(5, 6, 1.0),
561                    GraphLine::Edge(6, 7, 1.0),
562                    GraphLine::Edge(7, 2, 1.0),
563                ]),
564                Section::Terminals(4, vec![1, 3, 5, 7]),
565                Section::Coordinates(vec![
566                    (1, vec![80.0, 50.0]),
567                    (2, vec![30.0, 50.0]),
568                    (3, vec![55.0, 5.0]),
569                    (4, vec![105.0, 5.0]),
570                    (5, vec![130.0, 50.0]),
571                    (6, vec![105.0, 95.0]),
572                    (7, vec![55.0, 95.0]),
573                ]),
574                Section::Drawing(vec![
575                    (1, 2, vec![EdgeAttr::BendLeft]),
576                    (6, 7, vec![EdgeAttr::BendRight]),
577                ]),
578            ])
579        )
580    }
581
582    #[test]
583    fn test_read() {
584        let mut file: &[u8] = &b"33D32945 STP File, STP Format Version 1.0
585   SECTION Comment
586   Name    \"Odd Wheel\"
587   Creator \"T. Koch, A. Martin and S. Voss\"
588   Remark  \"Example used to describe the STP data format\"
589   END
590   SECTION Graph
591   Nodes 7
592   Edges 9
593   E 1 2 1
594   E 1 4 2
595   E 1 6 3
596   E 2 3 4
597   E 3 4 5
598   E 4 5 6
599   E 5 6 7
600   E 6 7 8
601   E 7 2 9
602   END
603
604
605   SECTION Terminals
606   Terminals 4
607   T 1
608   T 3
609   T 5
610   T 7
611   END
612
613   SECTION Coordinates
614   DD 1  80 50
615   DD 2  30 50
616   DD 3  55  5
617   DD 4 105  5
618   DD 5 130 50
619   DD 6 105 95
620   DD 7  55 95
621   END
622
623   SECTION Drawing
624   E 1 2 bl
625   E 6 7 BR
626   END
627
628   EOF"[..];
629
630        let instance = read_from_buf::<LinkedListGraph, _>(&mut file).unwrap();
631        let g = instance.graph;
632        let weights = instance.weights;
633        let coords = instance.coordinates;
634        let edgeattrs = instance.edgeattrs;
635
636        assert_eq!(g.num_nodes(), 7);
637        assert_eq!(g.num_edges(), 9);
638
639        let edges: Vec<_> = g
640            .edges()
641            .map(|e| (g.node_id(g.src(e)) + 1, g.node_id(g.snk(e)) + 1, weights[g.edge_id(e)]))
642            .collect();
643        assert_eq!(
644            edges,
645            vec![
646                (1, 2, 1.0),
647                (1, 4, 2.0),
648                (1, 6, 3.0),
649                (2, 3, 4.0),
650                (3, 4, 5.0),
651                (4, 5, 6.0),
652                (5, 6, 7.0),
653                (6, 7, 8.0),
654                (7, 2, 9.0),
655            ]
656        );
657
658        assert_eq!(
659            coords,
660            vec![
661                vec![80.0, 50.0],
662                vec![30.0, 50.0],
663                vec![55.0, 5.0],
664                vec![105.0, 5.0],
665                vec![130.0, 50.0],
666                vec![105.0, 95.0],
667                vec![55.0, 95.0],
668            ]
669        );
670
671        let edgeattrs: Vec<_> = g
672            .edges()
673            .map(|e| {
674                (
675                    g.node_id(g.src(e)) + 1,
676                    g.node_id(g.snk(e)) + 1,
677                    edgeattrs[g.edge_id(e)].clone(),
678                )
679            })
680            .filter(|&(_, _, ref attrs)| !attrs.is_empty())
681            .collect();
682
683        assert_eq!(
684            edgeattrs,
685            vec![(1, 2, vec![EdgeAttr::BendLeft]), (6, 7, vec![EdgeAttr::BendRight])]
686        )
687    }
688}
rs_graph/steinlib/parser.rs

rs_graph/steinlib/
parser.rs
