rs-graph 0.6.3

// 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 graph::{Node, IndexGraph};
use builder::Builder;

use super::{read_dimacs, DimacsError};

use num::traits::FromPrimitive;

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

/// 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>,
          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 = try!(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![];

        try!(read_dimacs(buf,
                         &mut |d, toks| {
                             match state {
                                 State::Prob => {
                                     if d != 'p' {
                                         return Err(DimacsError::Format(toks.line,
                                                                        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(toks.line, 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;
                                 }
                                 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(toks.line,
                                                                      format!("invalid node id {} (must be <= {})", u, n)));
                                     }

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

                                     if s.is_some() && t.is_some() {
                                         state = State::Arcs;
                                     }
                                 }
                                 State::Arcs => {
                                     if d != 'a' {
                                         return Err(DimacsError::Format(toks.line,
                                                                        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(toks.line,
                                                                      format!("invalid source node id {} (must be <= {})", u, n)));
                                     }
                                     if v < 1 || v > n {
                                         return Err(DimacsError::Data(toks.line,
                                                                      format!("invalid sink node id {} (must be <= {})", v, n)));
                                     }
                                     if u == v {
                                         return Err(DimacsError::Data(toks.line, format!("invalid loop ({},{}) in edge", u, u)));
                                     }
                                     let e = g.add_edge(nodes[u-1], nodes[v-1]);
                                     upper[g.edge_id(e)] = F::from_usize(c).unwrap();
                                 }
                             }

                             Ok(())
                         }));

        let s = g.node_id(s.map(|s| nodes[s - 1]).ok_or_else(|| DimacsError::Format(0, "missing source node".to_string()))?);
        let t = g.node_id(t.map(|t| nodes[t - 1]).ok_or_else(|| DimacsError::Format(0, "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 {Graph, Digraph, IndexGraph, LinkedListGraph};
    use dimacs::maxflow::Instance;
    use std::io;

    #[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)]);
    }

}