rs_graph/dimacs/
max.rs

1/*
2 * Copyright (c) 2021 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//! This module implements a read function for the famous DIMACS max
19//! flow format. A DIMACS file must look as follows.
20//!
21//! 1. empty lines are allowed and ignored
22//! 2. a line starting with `c` is a comment line and is ignored
23//! 3. the first non-comment line must have the form `p max <n> <m>`,
24//!    where `<n>` is an integer > 0 denoting the number of nodes and
25//!    `<m>` an integer > 0 denoting the number of arcs.
26//! 4. after the problem line there must follow exactly two node lines
27//!    of the form `n <node> <type>` where `<node>` is the node number
28//!    between `1..n` and `<type>` is either `s` (if this is the source
29//!    node) or `t` (if this is the sink node).
30//! 5. after the node lines there must be exactly `m` arc lines `a <u>
31//!    <v> <c>` denoting the source and sink nodes of an arc as well as
32//!    the arcs capacity `<c>` (an integer >= 0).
33//!
34//! Loops are not allowed. This module accepts parallel edges as long
35//! as the used graph type supports them. In the "official" DIMACS
36//! format parallel edges are forbidden.
37
38use super::{DimacsReader, Error, Result};
39use crate::builder::{Buildable, Builder};
40use crate::traits::IndexDigraph;
41use std::io::{Read, Write};
42
43pub struct Instance<G> {
44    /// The graph.
45    pub graph: G,
46    /// The source node id.
47    pub src: usize,
48    /// The sink node id.
49    pub snk: usize,
50    /// The upper bounds.
51    pub upper: Vec<usize>,
52}
53
54pub fn read<R: Read, G>(reader: R) -> Result<Instance<G>>
55where
56    G: IndexDigraph + Buildable,
57{
58    let mut reader = DimacsReader::new(reader);
59
60    // Read the problem line.
61    let mut pline = reader.expect_line('p')?;
62    pline.expect("max")?;
63    let nnodes = pline.number()?;
64    let nedges = pline.number()?;
65    pline.end()?;
66
67    let mut builder = G::Builder::new();
68    let mut upper = vec![0; nedges];
69    let nodes = builder.add_nodes(nnodes);
70    let mut src = None;
71    let mut snk = None;
72
73    for _ in 0..2 {
74        let mut nline = reader.expect_line('n')?;
75        let u: usize = nline.number()?;
76        if u < 1 || u > nnodes {
77            return Err(Error::Data {
78                line: nline.line,
79                msg: format!("invalid node id {} (must be in 1..{})", u, nnodes),
80            });
81        }
82        let what = nline.str()?;
83        match what {
84            "s" => {
85                if src.is_some() {
86                    return Err(Error::Format {
87                        line: nline.line,
88                        msg: "duplicate source node".to_string(),
89                    });
90                }
91                src = Some(u);
92            }
93            "t" => {
94                if snk.is_some() {
95                    return Err(Error::Format {
96                        line: nline.line,
97                        msg: "duplicate sink node".to_string(),
98                    });
99                }
100                snk = Some(u);
101            }
102            _ => {
103                return Err(Error::Format {
104                    line: nline.line,
105                    msg: format!("invalid node type, must be 's' or 't', got: {}", what),
106                });
107            }
108        }
109    }
110
111    for _ in 0..nedges {
112        let mut aline = reader.expect_line('a')?;
113        let u: usize = aline.number()?;
114        let v: usize = aline.number()?;
115        let c: usize = aline.number()?;
116
117        if u < 1 || u > nnodes {
118            return Err(Error::Data {
119                line: aline.line,
120                msg: format!("invalid source node id {} (must be in 1..{})", u, nnodes),
121            });
122        }
123
124        if v < 1 || v > nnodes {
125            return Err(Error::Data {
126                line: aline.line,
127                msg: format!("invalid sink node id {} (must be in 1..{})", u, nnodes),
128            });
129        }
130
131        if u == v {
132            return Err(Error::Data {
133                line: aline.line,
134                msg: format!("invalid loop ({},{}) in edge", u, u),
135            });
136        }
137
138        let e = builder.add_edge(nodes[u - 1], nodes[v - 1]);
139        upper[builder.edge2id(e)] = c;
140    }
141
142    if let Some(toks) = reader.read_line()? {
143        return Err(Error::Format {
144            line: toks.line,
145            msg: format!(
146                "unexpected line at the end of file (expected exactly {} 'a' lines)",
147                nedges,
148            ),
149        });
150    }
151
152    let graph = builder.into_graph();
153    let src = src.unwrap() - 1;
154    let snk = snk.unwrap() - 1;
155    Ok(Instance { graph, src, snk, upper })
156}
157
158pub fn read_from_file<G>(filename: &str) -> Result<Instance<G>>
159where
160    G: IndexDigraph + Buildable,
161{
162    read(std::fs::File::open(filename)?)
163}
164
165/// Write a min-cost-flow instance.
166pub fn write<W, G>(mut w: W, instance: &Instance<G>) -> std::io::Result<()>
167where
168    W: Write,
169    G: IndexDigraph,
170{
171    let g = &instance.graph;
172    writeln!(w, "p max {} {}", g.num_nodes(), g.num_edges())?;
173    writeln!(w, "n {} s", instance.src + 1)?;
174    writeln!(w, "n {} t", instance.snk + 1)?;
175    for e in g.edges() {
176        let eid = g.edge_id(e);
177        writeln!(
178            w,
179            "a {} {} {}",
180            g.node_id(g.src(e)) + 1,
181            g.node_id(g.snk(e)) + 1,
182            instance.upper[eid],
183        )?;
184    }
185
186    Ok(())
187}
188
189/// Write a min-cost-flow instance to a named file.
190pub fn write_to_file<W, G>(filename: &str, instance: &Instance<G>) -> std::io::Result<()>
191where
192    W: Write,
193    G: IndexDigraph,
194{
195    write(&mut std::fs::File::create(filename)?, instance)
196}
197
198#[cfg(test)]
199mod tests {
200
201    use crate::dimacs;
202    use crate::{traits::*, Buildable, Builder, VecGraph};
203    use std::io::{self, Cursor};
204
205    #[test]
206    fn parse_file_test() {
207        let file = "c this is a test file
208
209p max 6 9
210n 5 s
211n 6 t
212
213c there might be empty lines
214
215a 5 1 10
216a 5 2 10
217a 1 2 2
218a 1 3 4
219a 1 4 8
220a 2 4 9
221a 3 6 10
222a 4 3 6
223a 4 6 10
224
225c end of the file
226";
227        let instance = dimacs::max::read(io::Cursor::new(file)).unwrap();
228
229        let g: VecGraph = instance.graph;
230        let src = instance.src;
231        let snk = instance.snk;
232        let upper = instance.upper;
233
234        assert_eq!(g.num_nodes(), 6);
235        assert_eq!(g.num_edges(), 9);
236        assert_eq!(src, 4);
237        assert_eq!(snk, 5);
238
239        let mut arcs: Vec<_> = g
240            .edges()
241            .map(|e| (g.node_id(g.src(e)) + 1, g.node_id(g.snk(e)) + 1, upper[g.edge_id(e)]))
242            .collect();
243
244        arcs.sort();
245
246        assert_eq!(
247            arcs,
248            vec![
249                (1, 2, 2),
250                (1, 3, 4),
251                (1, 4, 8),
252                (2, 4, 9),
253                (3, 6, 10),
254                (4, 3, 6),
255                (4, 6, 10),
256                (5, 1, 10),
257                (5, 2, 10),
258            ]
259        );
260    }
261
262    #[test]
263    fn write_test_file() {
264        let g = VecGraph::<u32>::new_with(|b| {
265            let nodes = b.add_nodes(4);
266            b.add_edge(nodes[0], nodes[1]);
267            b.add_edge(nodes[0], nodes[2]);
268            b.add_edge(nodes[1], nodes[2]);
269            b.add_edge(nodes[1], nodes[3]);
270            b.add_edge(nodes[2], nodes[3]);
271        });
272        let upper = vec![4, 2, 2, 3, 5];
273
274        let mut buf = Cursor::new(Vec::new());
275        dimacs::max::write(
276            &mut buf,
277            &dimacs::max::Instance {
278                graph: &g,
279                src: 0,
280                snk: 3,
281                upper,
282            },
283        )
284        .unwrap();
285
286        assert_eq!(
287            String::from_utf8(buf.into_inner()).unwrap(),
288            "p max 4 5
289n 1 s
290n 4 t
291a 1 2 4
292a 1 3 2
293a 2 3 2
294a 2 4 3
295a 3 4 5
296"
297        );
298    }
299}
rs_graph/dimacs/max.rs

rs_graph/dimacs/
max.rs
