rs_graph/dimacs/
min.rs

1/*
2 * Copyright (c) 2021, 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
18//! This module implements a read function for the DIMACS min cost
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 min <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 node lines of the form
27//!    `n <node> <balance>` where `<node>` is the node number between
28//!    `1..n` and `<balance>` is node's supply (if positive) or demand
29//!    (if negative). Nodes that have balance 0 do not need to be
30//!    specified.
31//! 5. after the node lines there must be exactly `m` arc lines `a <u>
32//!    <v> <lb> <ub> <c>` denoting the source and sink nodes of an arc
33//!    as well as the arcs lower bound `<lb>`, upper bound `<ub>` and
34//!    cost `<c>`.
35//!
36//! Loops are not allowed. This module accepts parallel arcs as long
37//! as the used graph type supports them. In the "official" DIMACS
38//! format parallel arcs are forbidden.
39
40use super::{DimacsReader, Error, Result};
41use crate::builder::{Buildable, Builder};
42use crate::traits::IndexDigraph;
43use num_traits::Zero;
44use std::fmt::Display;
45use std::io::{Read, Write};
46use std::str::FromStr;
47
48pub struct Instance<G, T> {
49    /// The graph.
50    pub graph: G,
51    /// The node balance.
52    pub balances: Vec<T>,
53    /// The lower bounds.
54    pub lower: Vec<T>,
55    /// The upper bounds.
56    pub upper: Vec<T>,
57    /// The arc costs.
58    pub costs: Vec<T>,
59}
60
61pub fn read<R: Read, G, T>(reader: R) -> Result<Instance<G, T>>
62where
63    G: IndexDigraph + Buildable,
64    T: FromStr + Zero + Clone,
65    T::Err: Display,
66{
67    let mut reader = DimacsReader::new(reader);
68
69    // Read the problem line.
70    let mut pline = reader.expect_line('p')?;
71    pline.expect("min")?;
72    let nnodes = pline.number()?;
73    let nedges = pline.number()?;
74    pline.end()?;
75
76    let mut builder = G::Builder::new();
77    let mut balances = vec![T::zero(); nnodes];
78    let mut costs = Vec::with_capacity(nedges);
79    let mut lower = Vec::with_capacity(nedges);
80    let mut upper = Vec::with_capacity(nedges);
81
82    let nodes = builder.add_nodes(nnodes);
83
84    while let Some((d, mut toks)) = reader.read_one_line_of(&["n", "a"])? {
85        #[allow(clippy::branches_sharing_code)]
86        if d == "n" {
87            let u: usize = toks.number()?;
88            if u < 1 || u > nnodes {
89                return Err(Error::Data {
90                    line: toks.line,
91                    msg: format!("invalid node id {} (must be in 1..{})", u, nnodes),
92                });
93            }
94            balances[u - 1] = toks.number()?;
95        } else {
96            let u: usize = toks.number()?;
97            let v: usize = toks.number()?;
98            let lb: T = toks.number()?;
99            let ub: T = toks.number()?;
100            let c: T = toks.number()?;
101
102            if u < 1 || u > nnodes {
103                return Err(Error::Data {
104                    line: toks.line,
105                    msg: format!("invalid source node id {} (must be in 1..{})", u, nnodes),
106                });
107            }
108
109            if v < 1 || v > nnodes {
110                return Err(Error::Data {
111                    line: toks.line,
112                    msg: format!("invalid sink node id {} (must be in 1..{})", u, nnodes),
113                });
114            }
115
116            if u == v {
117                return Err(Error::Data {
118                    line: toks.line,
119                    msg: format!("invalid loop ({},{}) in edge", u, u),
120                });
121            }
122
123            if upper.len() == nedges {
124                return Err(Error::Data {
125                    line: toks.line,
126                    msg: format!("unexpected 'a' line (expected exactly {} arcs)", nedges),
127                });
128            }
129
130            builder.add_edge(nodes[u - 1], nodes[v - 1]);
131            lower.push(lb);
132            upper.push(ub);
133            costs.push(c);
134        }
135
136        toks.end()?;
137    }
138
139    Ok(Instance {
140        graph: builder.into_graph(),
141        balances,
142        lower,
143        upper,
144        costs,
145    })
146}
147
148pub fn read_from_file<G, T>(filename: &str) -> Result<Instance<G, T>>
149where
150    G: IndexDigraph + Buildable,
151    T: FromStr + Zero + Clone,
152    T::Err: Display,
153{
154    read(std::fs::File::open(filename)?)
155}
156
157/// Write a min-cost-flow instance.
158pub fn write<W, G, T>(mut w: W, instance: &Instance<G, T>) -> std::io::Result<()>
159where
160    W: Write,
161    G: IndexDigraph,
162    T: Zero + Display + Clone,
163{
164    let g = &instance.graph;
165    writeln!(w, "p min {} {}", g.num_nodes(), g.num_edges())?;
166    for u in g.nodes() {
167        let b = instance.balances[g.node_id(u)].clone();
168        if !b.is_zero() {
169            writeln!(w, "n {} {}", g.node_id(u) + 1, b)?;
170        }
171    }
172    for e in g.edges() {
173        let eid = g.edge_id(e);
174        writeln!(
175            w,
176            "a {} {} {} {} {}",
177            g.node_id(g.src(e)) + 1,
178            g.node_id(g.snk(e)) + 1,
179            instance.lower[eid],
180            instance.upper[eid],
181            instance.costs[eid]
182        )?;
183    }
184
185    Ok(())
186}
187
188/// Write a min-cost-flow instance to a named file.
189pub fn write_to_file<G, T>(filename: &str, instance: &Instance<G, T>) -> std::io::Result<()>
190where
191    G: IndexDigraph,
192    T: Zero + Display + Clone,
193{
194    write(&mut std::fs::File::create(filename)?, instance)
195}
196
197/// Write a solution of a min-cost-flow problem.
198pub fn write_solution<'a, W, G, T, Fs>(mut w: W, g: &'a G, flow: Fs, value: T) -> std::io::Result<()>
199where
200    W: Write,
201    G: IndexDigraph,
202    T: Display + Zero,
203    Fs: Fn(G::Edge<'a>) -> T,
204{
205    writeln!(w, "s {}", value)?;
206    for e in g.edges() {
207        let fl = (flow)(e);
208        if !fl.is_zero() {
209            writeln!(w, "f {} {} {}", g.node_id(g.src(e)) + 1, g.node_id(g.snk(e)) + 1, fl)?;
210        }
211    }
212
213    Ok(())
214}
215
216/// Write a solution of a min-cost-flow problem to a named file.
217pub fn write_solution_to_file<'a, G, T, Fs>(filename: &str, g: &'a G, flow: Fs, value: T) -> std::io::Result<()>
218where
219    G: IndexDigraph,
220    T: Display + Zero,
221    Fs: Fn(G::Edge<'a>) -> T,
222{
223    write_solution(&mut std::fs::File::create(filename)?, g, flow, value)
224}
225
226/// Read a solution of a min-cost-flow problem.
227#[allow(clippy::type_complexity)]
228pub fn read_solution<R, T>(r: R) -> Result<(T, Vec<(usize, usize, T)>)>
229where
230    R: Read,
231    T: FromStr,
232    T::Err: Display,
233{
234    let mut reader = DimacsReader::new(r);
235    let mut flows = vec![];
236    let mut sol = None;
237
238    // Read the solution value line.
239    while let Some((d, mut toks)) = reader.read_one_line_of(&["f", "s"])? {
240        if d == "f" {
241            flows.push((toks.number::<usize>()? - 1, toks.number::<usize>()? - 1, toks.number()?));
242        } else {
243            if sol.is_some() {
244                return Err(Error::Format {
245                    line: toks.line,
246                    msg: "The solution value must be specified exactly once".to_string(),
247                });
248            }
249            sol = Some(toks.number()?);
250        }
251        toks.end()?;
252    }
253
254    Ok((
255        sol.ok_or_else(|| Error::Format {
256            line: 0,
257            msg: "Missing solution value".to_string(),
258        })?,
259        flows,
260    ))
261}
262
263/// Read a solution of a min-cost-flow problem from a named file.
264#[allow(clippy::type_complexity)]
265pub fn read_solution_from_file<T>(filename: &str) -> Result<(T, Vec<(usize, usize, T)>)>
266where
267    T: FromStr,
268    T::Err: Display,
269{
270    read_solution(std::fs::File::open(filename)?)
271}
272
273#[cfg(test)]
274mod tests {
275
276    use crate::dimacs;
277    use crate::{traits::*, Buildable, Builder, VecGraph};
278    use std::io::{self, Cursor};
279
280    #[test]
281    fn parse_file_test() {
282        let file = "c this is a test file
283
284p min 8 11
285n 1 10
286n 2 20
287n 4 -5
288n 7 -15
289n 8 -10
290
291c there might be empty lines
292
293a 1 4 0 15 2
294a 2 1 0 10 1
295a 2 3 0 10 0
296a 2 6 0 10 6
297a 3 4 0 5 1
298a 3 5 0 10 4
299a 4 7 0 10 5
300a 5 6 0 20 2
301a 5 7 0 15 7
302a 6 8 0 10 8
303a 7 8 0 15 9
304
305c end of the file
306";
307        let instance = dimacs::min::read::<_, _, isize>(io::Cursor::new(file)).unwrap();
308
309        let g: VecGraph = instance.graph;
310        let balances = instance.balances;
311        let lower = instance.lower;
312        let upper = instance.upper;
313        let costs = instance.costs;
314
315        assert_eq!(g.num_nodes(), 8);
316        assert_eq!(g.num_edges(), 11);
317
318        assert_eq!(balances, vec![10, 20, 0, -5, 0, 0, -15, -10]);
319        assert_eq!(lower, vec![0; g.num_edges()]);
320        assert_eq!(upper, vec![15, 10, 10, 10, 5, 10, 10, 20, 15, 10, 15]);
321        assert_eq!(costs, vec![2, 1, 0, 6, 1, 4, 5, 2, 7, 8, 9]);
322
323        let edges = (0..g.num_edges())
324            .map(|i| g.id2edge(i))
325            .map(|e| (g.node_id(g.src(e)) + 1, g.node_id(g.snk(e)) + 1))
326            .collect::<Vec<_>>();
327
328        assert_eq!(
329            edges,
330            vec![
331                (1, 4),
332                (2, 1),
333                (2, 3),
334                (2, 6),
335                (3, 4),
336                (3, 5),
337                (4, 7),
338                (5, 6),
339                (5, 7),
340                (6, 8),
341                (7, 8),
342            ]
343        );
344    }
345
346    #[test]
347    fn write_test_file() {
348        let g = VecGraph::<u32>::new_with(|b| {
349            let nodes = b.add_nodes(4);
350            b.add_edge(nodes[0], nodes[1]);
351            b.add_edge(nodes[0], nodes[2]);
352            b.add_edge(nodes[1], nodes[2]);
353            b.add_edge(nodes[1], nodes[3]);
354            b.add_edge(nodes[2], nodes[3]);
355        });
356        let balances = vec![4, 0, 0, -4];
357        let lower = vec![0; g.num_edges()];
358        let upper = vec![4, 2, 2, 3, 5];
359        let costs = vec![2, 2, 1, 3, 1];
360
361        let mut buf = Cursor::new(Vec::new());
362        dimacs::min::write(
363            &mut buf,
364            &dimacs::min::Instance {
365                graph: &g,
366                balances,
367                lower,
368                upper,
369                costs,
370            },
371        )
372        .unwrap();
373
374        assert_eq!(
375            String::from_utf8(buf.into_inner()).unwrap(),
376            "p min 4 5
377n 1 4
378n 4 -4
379a 1 2 0 4 2
380a 1 3 0 2 2
381a 2 3 0 2 1
382a 2 4 0 3 3
383a 3 4 0 5 1
384"
385        );
386    }
387
388    #[test]
389    fn write_solution_file() -> std::result::Result<(), Box<dyn std::error::Error>> {
390        let g = VecGraph::<u32>::new_with(|b| {
391            let nodes = b.add_nodes(4);
392            b.add_edge(nodes[0], nodes[1]);
393            b.add_edge(nodes[0], nodes[2]);
394            b.add_edge(nodes[1], nodes[2]);
395            b.add_edge(nodes[1], nodes[3]);
396            b.add_edge(nodes[2], nodes[3]);
397        });
398        let flow = vec![2, 2, 2, 0, 4];
399
400        let mut buf = Cursor::new(Vec::new());
401        dimacs::min::write_solution(&mut buf, &g, |e| flow[g.edge_id(e)], 14)?;
402
403        let soltxt = String::from_utf8(buf.into_inner())?;
404        assert_eq!(
405            soltxt,
406            "s 14
407f 1 2 2
408f 1 3 2
409f 2 3 2
410f 3 4 4
411"
412        );
413
414        let (value, flows) = dimacs::min::read_solution(Cursor::new(soltxt))?;
415        assert_eq!(value, 14);
416        assert_eq!(flows, vec![(0, 1, 2), (0, 2, 2), (1, 2, 2), (2, 3, 4)]);
417
418        Ok(())
419    }
420}
rs_graph/dimacs/min.rs

rs_graph/dimacs/
min.rs
