rs_graph/
mps.rs

1/*
2 * Copyright (c) 2021, 2023 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
18//! Read and write routines for the MPS format.
19
20use crate::{Buildable, Builder, IndexDigraph};
21use std::collections::HashMap;
22use std::error;
23use std::fmt;
24use std::io::{self, BufRead, BufReader, Read};
25
26/// Error when reading a file in MPS format.
27#[derive(Debug)]
28pub enum Error {
29    Io(io::Error),
30    Format { line: usize, msg: String },
31    Data { line: usize, msg: String },
32}
33
34impl From<io::Error> for Error {
35    fn from(err: io::Error) -> Self {
36        Error::Io(err)
37    }
38}
39
40impl fmt::Display for Error {
41    fn fmt(&self, fmt: &mut fmt::Formatter) -> std::result::Result<(), fmt::Error> {
42        use self::Error::*;
43        match self {
44            Io(err) => err.fmt(fmt),
45            Format { line, msg } => write!(fmt, "Format error on line {}: {}", line, msg),
46            Data { line, msg } => write!(fmt, "Data error on line {}: {}", line, msg),
47        }
48    }
49}
50
51impl error::Error for Error {
52    fn cause(&self) -> Option<&dyn error::Error> {
53        match self {
54            Error::Io(err) => Some(err),
55            _ => None,
56        }
57    }
58}
59
60pub type Result<T> = std::result::Result<T, Error>;
61
62/// An MCF instance.
63pub struct Instance<G> {
64    /// The name of the instance.
65    pub name: Option<String>,
66    /// The graph.
67    pub graph: G,
68    /// The node balance.
69    pub balances: Vec<f64>,
70    /// The lower bounds.
71    pub lower: Vec<f64>,
72    /// The upper bounds.
73    pub upper: Vec<f64>,
74    /// The arc costs.
75    pub costs: Vec<f64>,
76    /// Names of the nodes.
77    ///
78    /// These are the row names in the MPS file.
79    pub node_names: Vec<String>,
80    /// Names of the edges.
81    ///
82    /// These are the column names in the MPS file.
83    pub edge_names: Vec<String>,
84}
85
86fn find_token(line: &str, beg: usize, end: usize) -> &str {
87    if end <= line.len() {
88        line[beg..end].trim()
89    } else if beg < line.len() {
90        line[beg..].trim()
91    } else {
92        &line[0..0]
93    }
94}
95
96struct Reader<R: BufRead> {
97    line: usize,
98    buf: String,
99    io: R,
100}
101
102impl<R: BufRead> Reader<R> {
103    /// Read the next input line, return `true` on success.
104    ///
105    /// Empty lines and comment lines (those starting with a '*') are skipped
106    fn next_line(&mut self) -> Result<bool> {
107        loop {
108            self.line += 1;
109            self.buf.clear();
110            if self.io.read_line(&mut self.buf)? == 0 {
111                return Ok(false);
112            }
113
114            // skip empty lines and comments, i.e. lines starting with a '*'
115            if !self.buf.trim().is_empty() && !self.buf.starts_with('*') {
116                return Ok(true);
117            }
118        }
119    }
120
121    /// Reads the next non-section line.
122    ///
123    /// If the next line is a non-section line, returns `true`.
124    /// If the next line is a section line, returns `false`.
125    /// If there is no next line, returns an error.
126    fn next_field_line(&mut self) -> Result<bool> {
127        if self.next_line()? {
128            Ok(!self.is_section_header())
129        } else {
130            Err(self.fmt_error("Unexpected end of file (require ENDATA)".to_string()))
131        }
132    }
133
134    /// Return `true` if the current line is a section header.
135    ///
136    /// These are those lines not starting with a space.
137    fn is_section_header(&self) -> bool {
138        !self.buf.starts_with(' ')
139    }
140
141    /// Return the i-th field.
142    fn field(&self, i: usize) -> &str {
143        match i {
144            0 => {
145                assert!(self.is_section_header());
146                find_token(&self.buf, 0, 14)
147            }
148            2 => find_token(&self.buf, 1, 3),
149            5 => find_token(&self.buf, 4, 14),
150            15 => find_token(&self.buf, 14, 24),
151            25 => find_token(&self.buf, 24, 39),
152            40 => find_token(&self.buf, 39, 49),
153            50 => find_token(&self.buf, 49, self.buf.len().max(50)),
154            _ => unimplemented!("Invalid field number"),
155        }
156    }
157
158    /// Return the i-th field or an error if it is empty.
159    fn non_empty_field(&self, i: usize) -> Result<&str> {
160        let f = self.field(i);
161        if !f.is_empty() {
162            Ok(f)
163        } else {
164            Err(self.fmt_error(format!("Expected non-empty field in column {}", i)))
165        }
166    }
167
168    /// Return an error if not all fields starting from the given field are empty.
169    fn ensure_is_empty(&self, i: usize) -> Result<()> {
170        if let 1 | 2 | 5 | 15 | 25 | 40 | 50 = i {
171            if i > self.buf.len() || self.buf[i..].trim().is_empty() {
172                Ok(())
173            } else {
174                Err(self.fmt_error(format!("Unexpected data after column {}", i)))
175            }
176        } else {
177            unimplemented!("Invalid field number")
178        }
179    }
180
181    /// Returns a format-error for the current line.
182    fn fmt_error(&self, msg: String) -> Error {
183        Error::Format { line: self.line, msg }
184    }
185
186    /// Returns a data-error for the current line.
187    fn data_error(&self, msg: String) -> Error {
188        Error::Data { line: self.line, msg }
189    }
190}
191
192struct NodeInfo<N> {
193    node: N,
194    balance: Option<f64>,
195}
196
197impl<N> NodeInfo<N> {
198    fn new(u: N) -> NodeInfo<N> {
199        NodeInfo { node: u, balance: None }
200    }
201}
202
203struct EdgeInfo<N> {
204    cost: Option<f64>,
205    src: Option<N>,
206    snk: Option<N>,
207    lb: Option<f64>,
208    ub: Option<f64>,
209}
210
211impl<N> EdgeInfo<N> {
212    fn new() -> EdgeInfo<N> {
213        EdgeInfo {
214            cost: None,
215            src: None,
216            snk: None,
217            lb: None,
218            ub: None,
219        }
220    }
221}
222
223fn add_edge<R: BufRead, N: Copy>(
224    reader: &Reader<R>,
225    col: &str,
226    row: &str,
227    coeff: &str,
228    e: &mut EdgeInfo<N>,
229    obj_row: &Option<String>,
230    rows: &HashMap<String, NodeInfo<N>>,
231) -> Result<()> {
232    let coeff = coeff
233        .parse::<f64>()
234        .map_err(|err| reader.fmt_error(format!("Invalid coefficient: {}", err)))?;
235
236    if obj_row.as_ref().map(|obj| obj == row).unwrap_or(false) {
237        // Coefficient for the objective
238        if e.cost.is_some() {
239            return Err(reader.data_error(format!("Multiple cost coefficients in column {}", col)));
240        }
241        e.cost = Some(coeff)
242    } else {
243        let u = rows
244            .get(row)
245            .ok_or_else(|| reader.data_error(format!("Unknown row: {}", row)))?;
246
247        #[allow(clippy::float_cmp)]
248        if coeff == 1.0 {
249            // Coefficient for some flow conservation constraint
250            if e.src.is_some() {
251                return Err(reader.data_error(format!("Multiple +1 coefficients in column {}", col)));
252            }
253            e.src = Some(u.node);
254        } else if coeff == -1.0 {
255            if e.snk.is_some() {
256                return Err(reader.data_error(format!("Multiple -1 coefficients in column {}", col)));
257            }
258            e.snk = Some(u.node);
259        } else {
260            return Err(reader.data_error(format!("Only coefficients +1 and -1 are supported (got: {})", coeff)));
261        }
262    }
263
264    Ok(())
265}
266
267fn add_rhs<R: BufRead, N: Copy>(
268    reader: &Reader<R>,
269    row: &str,
270    rhs: &str,
271    rows: &mut HashMap<String, NodeInfo<N>>,
272) -> Result<()> {
273    let rhs = rhs
274        .parse::<f64>()
275        .map_err(|err| reader.fmt_error(format!("Invalid right-hand side: {}", err)))?;
276
277    let u = rows
278        .get_mut(row)
279        .ok_or_else(|| reader.data_error(format!("Unknown row: {}", row)))?;
280
281    if u.balance.is_some() {
282        return Err(reader.data_error(format!("Multiple right-hand side values in row {}", row)));
283    }
284    u.balance = Some(rhs);
285
286    Ok(())
287}
288
289/// Read a file in MPS format from the reader.
290pub fn read<G, R: Read>(reader: R) -> Result<Instance<G>>
291where
292    G: IndexDigraph + Buildable,
293{
294    let mut reader = Reader {
295        io: BufReader::new(reader),
296        line: 0,
297        buf: String::new(),
298    };
299
300    let mut name = None;
301    let mut minimize = None;
302    let mut obj_row = None;
303    let mut cols = HashMap::new(); // corresponding to edges
304    let mut rows = HashMap::new(); // corresponding to nodes
305    let mut rhsname = None;
306    let mut bndname = None;
307    let mut graph = G::new_builder();
308
309    if !reader.next_line()? {
310        return Err(reader.fmt_error("Empty file".to_string()));
311    }
312
313    loop {
314        if !reader.is_section_header() {
315            return Err(reader.fmt_error("Expected a section header (non-whitespace in column 0)".to_string()));
316        }
317        let section = reader.field(0);
318        match section {
319            "NAME" => {
320                let n = reader.field(15);
321                if !n.is_empty() {
322                    name = Some(n.to_string());
323                }
324                if reader.next_field_line()? {
325                    return Err(reader.fmt_error("Invalid record in NAME section".to_string()));
326                }
327            }
328            "ROWS" => {
329                while reader.next_field_line()? {
330                    match reader.field(2) {
331                        "N" => {
332                            if obj_row.is_some() {
333                                return Err(reader.fmt_error("Only one objective row is supported".to_string()));
334                            }
335                            obj_row = Some(reader.non_empty_field(5)?.to_string());
336                        }
337                        "E" => {
338                            let row = reader.non_empty_field(5)?;
339                            reader.ensure_is_empty(15)?;
340                            if rows.insert(row.to_string(), NodeInfo::new(graph.add_node())).is_some() {
341                                return Err(reader.data_error(format!("Row {} specified multiple times", row)));
342                            }
343                        }
344                        "L" | "G" => {
345                            return Err(reader.fmt_error("Only equality constraints are supported".to_string()))
346                        }
347                        _ => {
348                            return Err(reader
349                                .fmt_error(format!("Invalid row type {} (expected N, L, E or G)", reader.field(2))))
350                        }
351                    }
352                }
353            }
354            "COLUMNS" => {
355                while reader.next_field_line()? {
356                    if !reader.field(2).is_empty() {
357                        return Err(reader.fmt_error("Unexpected field in column 2".to_string()));
358                    }
359
360                    let col = reader.non_empty_field(5)?; // name of the edge
361                                                          // Get the edge.
362                    let e = cols.entry(col.to_string()).or_insert_with(EdgeInfo::new);
363
364                    let row1 = reader.non_empty_field(15)?; // node
365                    let coeff1 = reader.non_empty_field(25)?; // src/snk
366
367                    add_edge(&reader, col, row1, coeff1, e, &obj_row, &rows)?;
368
369                    let row2 = reader.field(40);
370                    let coeff2 = reader.field(50);
371                    if row2.is_empty() != coeff2.is_empty() {
372                        if row2.is_empty() {
373                            return Err(reader.fmt_error("Second row name missing".to_string()));
374                        } else {
375                            return Err(reader.fmt_error("Second coefficient missing".to_string()));
376                        }
377                    }
378
379                    if !row2.is_empty() {
380                        add_edge(&reader, col, row2, coeff2, e, &obj_row, &rows)?;
381                    }
382                }
383            }
384            "RHS" => {
385                while reader.next_field_line()? {
386                    if !reader.field(2).is_empty() {
387                        return Err(reader.fmt_error("Unexpected field in column 2".to_string()));
388                    }
389
390                    if let Some(rhsname) = rhsname.as_ref() {
391                        if rhsname != reader.non_empty_field(5)? {
392                            return Err(reader.data_error("Only one right-hand side is suported".to_string()));
393                        }
394                    } else {
395                        rhsname = Some(reader.non_empty_field(5)?.to_string());
396                    }
397
398                    let row1 = reader.non_empty_field(15)?;
399                    let rhs1 = reader.non_empty_field(25)?;
400                    add_rhs(&reader, row1, rhs1, &mut rows)?;
401
402                    let row2 = reader.field(40);
403                    let rhs2 = reader.field(50);
404
405                    if row2.is_empty() != rhs2.is_empty() {
406                        if row2.is_empty() {
407                            return Err(reader.fmt_error("Second row name missing".to_string()));
408                        } else {
409                            return Err(reader.fmt_error("Second right-hand side value missing".to_string()));
410                        }
411                    }
412                    if !row2.is_empty() {
413                        add_rhs(&reader, row2, rhs2, &mut rows)?;
414                    }
415                }
416            }
417            "BOUNDS" => {
418                while reader.next_field_line()? {
419                    if let Some(bndname) = bndname.as_ref() {
420                        if bndname != reader.non_empty_field(5)? {
421                            return Err(reader.data_error("Only one bound name is suported".to_string()));
422                        }
423                    } else {
424                        bndname = Some(reader.non_empty_field(5)?.to_string());
425                    }
426
427                    let typ = reader.non_empty_field(2)?;
428                    let (lb, ub) = match typ {
429                        "FR" => {
430                            reader.ensure_is_empty(25)?;
431                            (-f64::INFINITY, f64::INFINITY)
432                        }
433                        "MI" => {
434                            reader.ensure_is_empty(25)?;
435                            (-f64::INFINITY, 0.0)
436                        }
437                        _ => {
438                            reader.ensure_is_empty(40)?;
439                            let val = reader
440                                .non_empty_field(25)?
441                                .parse::<f64>()
442                                .map_err(|err| reader.fmt_error(format!("Invalid bound: {}", err)))?;
443                            (val, val)
444                        }
445                    };
446
447                    let col = reader.non_empty_field(15)?;
448                    let e = cols
449                        .get_mut(col)
450                        .ok_or_else(|| reader.data_error(format!("Unknown column: {}", col)))?;
451
452                    if let "UP" | "FX" | "MI" | "FR" = typ {
453                        if e.ub.is_some() {
454                            return Err(reader.data_error(format!("Multiple upper bounds for {}", col)));
455                        }
456                        e.ub = Some(ub);
457                    }
458                    if let "LO" | "FX" | "FR" = typ {
459                        if e.lb.is_some() {
460                            return Err(reader.data_error(format!("Multiple lower bounds for {}", col)));
461                        }
462                        e.lb = Some(lb);
463                    }
464                }
465            }
466            "RANGES" => {
467                if reader.next_field_line()? {
468                    return Err(reader.data_error("RANGES section is not supported".to_string()));
469                }
470            }
471            "OBJSENSE" => {
472                while reader.next_field_line()? {
473                    if minimize.is_some() {
474                        return Err(reader.fmt_error("OBJSENSE must be specified at most once".to_string()));
475                    }
476                    match reader.field(5) {
477                        "MIN" => minimize = Some(true),
478                        "MAX" => minimize = Some(false),
479                        _ => {
480                            return Err(reader.fmt_error(format!(
481                                "Invalid objective sense {} (must be 'MIN' or 'MAX')",
482                                reader.field(5)
483                            )))
484                        }
485                    }
486                    reader.ensure_is_empty(15)?;
487                }
488            }
489            "ENDATA" => {
490                if reader.next_line()? {
491                    return Err(reader.fmt_error("Unexpected line after ENDATA".to_string()));
492                }
493                break;
494            }
495            _ => {
496                return Err(reader.fmt_error(format!("Unknown section: {}", section)));
497            }
498        }
499    }
500
501    // We have everything, create the graph.
502    let n = rows.len();
503    let m = cols.len();
504
505    let mut node_names = vec![String::new(); n];
506    let mut balances = vec![0.0; n];
507    let mut edge_names = Vec::with_capacity(m);
508    let mut lower = Vec::with_capacity(m);
509    let mut upper = Vec::with_capacity(m);
510    let mut costs = Vec::with_capacity(m);
511
512    for (uname, u) in rows {
513        node_names[graph.node2id(u.node)] = uname;
514        balances[graph.node2id(u.node)] = u.balance.unwrap_or(0.0);
515    }
516
517    for (ename, e) in cols {
518        let u = e
519            .src
520            .ok_or_else(|| reader.data_error(format!("Missing +1 coefficient for edge {}", ename)))?;
521        let v = e
522            .snk
523            .ok_or_else(|| reader.data_error(format!("Missing -1 coefficient for edge {}", ename)))?;
524        graph.add_edge(u, v);
525        edge_names.push(ename);
526        lower.push(e.lb.unwrap_or(0.0));
527        upper.push(e.ub.unwrap_or(f64::INFINITY));
528        costs.push(e.cost.unwrap_or(0.0));
529    }
530    let graph = graph.into_graph();
531
532    if !minimize.unwrap_or(true) {
533        for c in &mut costs {
534            *c = -*c;
535        }
536    }
537
538    Ok(Instance {
539        name,
540        graph,
541        balances,
542        lower,
543        upper,
544        costs,
545        node_names,
546        edge_names,
547    })
548}
549
550pub fn read_from_file<G>(filename: &str) -> Result<Instance<G>>
551where
552    G: IndexDigraph + Buildable,
553{
554    read(std::fs::File::open(filename)?)
555}
rs_graph/mps.rs

rs_graph/
mps.rs
