rs-graph 0.14.1

// Copyright (c) 2015, 2016, 2017 Frank Fischer <frank-fischer@shadow-soft.de>
//
// This program is free software: you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

//! This module implements a read function for the famous DIMACS max
//! flow format. A DIMACS file must look as follows.
//!
//! 1. empty lines are allowed and ignored
//! 2. a line starting with `c` is a comment line and is ignored
//! 3. the first non-comment line must have the form `p max <n> <m>`,
//!    where `<n>` is an integer > 0 denoting the number of nodes and
//!    `<m>` an integer > 0 denoting the number of arcs.
//! 4. after the problem line there must follow exactly two node lines
//!    of the form `n <node> <type>` where `<node>` is the node number
//!    between `1..n` and `<type>` is either `s` (if this is the source
//!    node) or `t` (if this is the sink node).
//! 5. after the node lines there must be exactly `m` arc lines `a <u>
//!    <v> <c>` denoting the source and sink nodes of an arc as well as
//!    the arcs capacity `<c>` (an integer >= 0).

use builder::{Buildable, Builder};
use graph::{IndexGraph, Node};

use super::{read_dimacs, DimacsError};

use num::traits::FromPrimitive;

use std::fs;
use std::io;

/// A maxflow instance.
pub struct Instance<G, F, N>
where
    G: for<'a> IndexGraph<'a, Node = N>,
{
    /// The graph.
    pub graph: G,
    /// The source node.
    pub src: N,
    /// The sink node.
    pub snk: N,
    /// The upper bounds.
    pub upper: Vec<F>,
}

impl<G, F, N> Instance<G, F, N>
where
    G: for<'a> IndexGraph<'a, Node = N> + Buildable,
    F: FromPrimitive,
    N: Node,
{
    /// Read DIMACS file and return instance.
    ///
    /// - `fname` is the name of the file to be read
    pub fn read(fname: &str) -> Result<Self, DimacsError> {
        let f = fs::File::open(fname)?;
        Instance::read_from_buf(&mut io::BufReader::new(f))
    }

    /// Read DIMACS file from a buffered reader and return instance.
    ///
    /// - `buf` the buffer with the file content
    pub fn read_from_buf<R>(buf: &mut R) -> Result<Self, DimacsError>
    where
        R: io::BufRead,
    {
        let mut g = G::Builder::new();
        let mut n = 0;
        let mut m = 0;
        let mut s = None;
        let mut t = None;
        let mut upper = vec![];

        enum State {
            Prob,
            SrcSnk,
            Arcs,
        };
        let mut state = State::Prob;
        let mut nodes = vec![];

        read_dimacs(buf, &mut |d, toks| match state {
            State::Prob => {
                if d != 'p' {
                    return Err(DimacsError::Format {
                        line: toks.line,
                        msg: format!("expected problem line starting with 'p', got: {}", d),
                    });
                }
                let max = toks.next().unwrap_or("end of line");
                if max != "max" {
                    return Err(DimacsError::Format {
                        line: toks.line,
                        msg: format!("expected 'max' in p line, got: {}", max),
                    });
                }
                n = try!(toks.number());
                m = try!(toks.number());
                try!(toks.end());

                nodes = g.add_nodes(n);
                upper.extend((0..m).map(|_| F::from_usize(0).unwrap()));

                state = State::SrcSnk;
                Ok(())
            }
            State::SrcSnk => {
                let u: usize = try!(toks.number());
                let what = try!(toks.str());
                try!(toks.end());

                if u < 1 || u > n {
                    return Err(DimacsError::Data {
                        line: toks.line,
                        msg: format!("invalid node id {} (must be <= {})", u, n),
                    });
                }

                match what {
                    "s" => {
                        if s.is_some() {
                            return Err(DimacsError::Format {
                                line: toks.line,
                                msg: "duplicate source node".to_string(),
                            });
                        }
                        s = Some(u);
                    }
                    "t" => {
                        if t.is_some() {
                            return Err(DimacsError::Format {
                                line: toks.line,
                                msg: "duplicate sink node".to_string(),
                            });
                        }
                        t = Some(u);
                    }
                    _ => {
                        return Err(DimacsError::Format {
                            line: toks.line,
                            msg: "unexpected line (require source and sink nodes first)".to_string(),
                        });
                    }
                }

                if s.is_some() && t.is_some() {
                    state = State::Arcs;
                }
                Ok(())
            }
            State::Arcs => {
                if d != 'a' {
                    return Err(DimacsError::Format {
                        line: toks.line,
                        msg: format!("expected arc line starting with 'a', got: {}", d),
                    });
                }
                let u: usize = try!(toks.number());
                let v: usize = try!(toks.number());
                let c: usize = try!(toks.number());
                if u < 1 || u > n {
                    return Err(DimacsError::Data {
                        line: toks.line,
                        msg: format!("invalid source node id {} (must be <= {})", u, n),
                    });
                }
                if v < 1 || v > n {
                    return Err(DimacsError::Data {
                        line: toks.line,
                        msg: format!("invalid sink node id {} (must be <= {})", v, n),
                    });
                }
                if u == v {
                    return Err(DimacsError::Data {
                        line: toks.line,
                        msg: format!("invalid loop ({},{}) in edge", u, u),
                    });
                }
                let e = g.add_edge(nodes[u - 1], nodes[v - 1]);
                upper[g.edge2id(e)] = F::from_usize(c).unwrap();
                Ok(())
            }
        })?;

        let s = g.node2id(s.map(|s| nodes[s - 1]).ok_or_else(|| DimacsError::Format {
            line: 0,
            msg: "missing source node".to_string(),
        })?);
        let t = g.node2id(t.map(|t| nodes[t - 1]).ok_or_else(|| DimacsError::Format {
            line: 0,
            msg: "missing sink node".to_string(),
        })?);

        let g = g.to_graph();
        let s = g.id2node(s);
        let t = g.id2node(t);

        Ok(Instance {
            graph: g,
            src: s,
            snk: t,
            upper: upper,
        })
    }
}

#[cfg(test)]
mod tests {

    use dimacs::maxflow::Instance;
    use std::io;
    use {Digraph, Graph, IndexGraph, LinkedListGraph};

    #[test]
    fn parse_file_test() {
        let file = "c this is a test file

p max 6 9
n 5 s
n 6 t

c there might be empty lines

a 5 1 10
a 5 2 10
a 1 2 2
a 1 3 4
a 1 4 8
a 2 4 9
a 3 6 10
a 4 3 6
a 4 6 10

c end of the file
";
        let instance = Instance::read_from_buf(&mut io::Cursor::new(file)).unwrap();

        let g: LinkedListGraph = instance.graph;
        let src = instance.src;
        let snk = instance.snk;
        let upper = instance.upper;

        assert_eq!(g.num_nodes(), 6);
        assert_eq!(g.num_edges(), 9);
        assert_eq!(g.node_id(src), 4);
        assert_eq!(g.node_id(snk), 5);

        let mut arcs: Vec<_> = g
            .edges()
            .map(|e| (g.node_id(g.src(e)) + 1, g.node_id(g.snk(e)) + 1, upper[g.edge_id(e)]))
            .collect();

        arcs.sort();

        assert_eq!(
            arcs,
            vec![
                (1, 2, 2),
                (1, 3, 4),
                (1, 4, 8),
                (2, 4, 9),
                (3, 6, 10),
                (4, 3, 6),
                (4, 6, 10),
                (5, 1, 10),
                (5, 2, 10),
            ]
        );
    }

}