rs-graph 0.6.3

// Copyright (c) 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/>
//

use std::io::{BufRead, BufReader};
use std::fs;
use std::collections::HashSet;
use std::cmp::{min, max};
use std::f64;

use super::{read_dimacs, DimacsError};

use Builder;

// Possible metrics
#[derive(Copy,Clone,PartialEq,Debug)]
pub enum Metric {
    // infinity norm,
    LINF,
    // l_p norm
    L(f64),
    // squared euclidean norm
    L2S,
}

// Problem parameters
#[derive(PartialEq,Debug)]
pub enum Param {
    // edge included only if length greater than or equal to this
    MinLength(f64),
    // edge included only if length less than or equal to this
    MaxLength(f64),
}

/// Read DIMACS file.
///
/// - `fname` is the name of the file to be read
/// - `weights` is the array of node weights
pub fn read<B>(fname: &str) -> Result<(B, Vec<f64>), DimacsError>
    where B: Builder
{
    read_from_buf(&mut BufReader::new(fs::File::open(fname)?))
}

/// Read DIMACS file from a buffered reader.
///
/// - `buf` the buffer with the file content
pub fn read_from_buf<R, B>(buf: &mut R) -> Result<(B, Vec<f64>), DimacsError>
    where R: BufRead,
          B: Builder,
{
    let mut g = B::with_capacities(0, 0);
    let mut weights = vec![];
    let mut n = 0;
    let mut m = 0;
    let mut gnodes = vec![];
    let mut nodes = HashSet::new();
    let mut edges = HashSet::new();
    let mut dim = 0;
    let mut metric = None;
    let mut vertices = vec![];
    let mut minlength = None;
    let mut maxlength = None;

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

            g.reserve(n, m);
            gnodes = g.add_nodes(n);
            weights.clear();
            weights.resize(n, 0.0);

            start = false;
        } else {
            match d {
                'n' => {
                    let id: usize = try!(toks.number());
                    let val = try!(toks.number());
                    try!(toks.end());
                    if id < 1 || id > n {
                        return Err(DimacsError::Format(toks.line,
                                                       format!("invalid node id {} (must be <= {})", id, n)));
                    }
                    if !nodes.insert(id) {
                        return Err(DimacsError::Format(toks.line, format!("duplicate node id {}", id)));
                    }
                    weights[id - 1] = val;
                }
                'e' => {
                    let u: usize = try!(toks.number());
                    let v: usize = try!(toks.number());
                    try!(toks.end());
                    if u < 1 || u > n {
                        return Err(DimacsError::Format(toks.line, format!("invalid node id {} in edge", u)));
                    }
                    if v < 1 || v > n {
                        return Err(DimacsError::Format(toks.line, format!("invalid node id {} in edge", v)));
                    }
                    if u == v {
                        return Err(DimacsError::Format(toks.line, format!("invalid loop ({},{}) in edge", u, u)));
                    }
                    if !edges.insert((min(u, v), max(u, v))) {
                        return Err(DimacsError::Format(toks.line, format!("duplicate edge ({},{})", u, v)));
                    }
                    g.add_edge(gnodes[u - 1], gnodes[v - 1]);
                }
                'd' => {
                    let d: usize = try!(toks.number());
                    let m = match toks.next() {
                        Some("LINF") => Metric::LINF,
                        Some("L2S") => Metric::L2S,
                        Some(m) if !m.is_empty() && m.starts_with('L') => {
                            let p: f64 = match m[1..].parse() {
                                Ok(x) => x,
                                Err(_) => return Err(DimacsError::Format(toks.line, "invalid norm".to_string())),
                            };
                            if p <= 0.0 {
                                return Err(DimacsError::Format(toks.line, format!("p of p-norm must be > 0 (got: {})", p)));
                            }
                            Metric::L(p)
                        }
                        Some(_) => return Err(DimacsError::Format(toks.line, "invalid norm".to_string())),
                        None => return Err(DimacsError::Format(toks.line, "missing norm".to_string())),
                    };
                    try!(toks.end());

                    if d < 1 {
                        return Err(DimacsError::Format(toks.line, format!("invalid dimension {} < 1", d)));
                    }
                    if dim > 0 {
                        return Err(DimacsError::Format(toks.line, "duplicate dimension".to_string()));
                    }

                    dim = d;
                    metric = Some(m);
                    vertices.reserve(n);
                }
                'v' => {
                    if dim == 0 {
                        return Err(DimacsError::Format(toks.line,
                                                       "missing dimension line before vertex line".to_string()));
                    }

                    let mut vs: Vec<f64> = Vec::new();
                    for _ in 0..dim {
                        vs.push(try!(toks.number()));
                    }
                    try!(toks.end());

                    if dim != vs.len() {
                        return Err(DimacsError::Format(toks.line,
                                                       format!("vertex line has too many entries {} (expected: {})",
                                                               vs.len(),
                                                               dim)));
                    }

                    vertices.push(vs);
                }
                'x' => {
                    let par = try!(toks.str());
                    let l: f64 = try!(toks.number());
                    try!(toks.end());
                    match par {
                        "MINLENGTH" => {
                            if minlength.is_some() {
                                return Err(DimacsError::Format(toks.line, "duplicate parameter MINLENGTH".to_string()));
                            }
                            minlength = Some(l)
                        }
                        "MAXLENGTH" => {
                            if maxlength.is_some() {
                                return Err(DimacsError::Format(toks.line, "duplicate parameter MAXLENGTH".to_string()));
                            }
                            maxlength = Some(l)
                        }
                        _ => return Err(DimacsError::Format(toks.line, format!("unknown parameter {}", par))),
                    };
                }
                _ => {
                    return Err(DimacsError::Format(toks.line, format!("invalid command {}", d)));
                }
            }
        }

        Ok(())
    }));

    // verify consistency with vertex data
    if dim > 0 {
        let metric = metric.unwrap();
        let minl = match minlength {
            Some(l) => l,
            _ => 0.0,
        };
        let maxl = match maxlength {
            Some(l) => l,
            _ => f64::INFINITY,
        };
        for u in 0..n {
            for v in u + 1..n {
                let d = dist(&vertices[u], &vertices[v], metric);
                match (edges.contains(&(u + 1, v + 1)), d >= minl, d <= maxl) {
                    (false, true, true) => {
                        return Err(DimacsError::Format(0,
                                                       format!("edge ({},{}) should be contained in the graph", u, v)))
                    }
                    (true, false, _) => {
                        return Err(DimacsError::Format(0,
                                                       format!("edge ({},{}) should not be contained in the graph (too short)",
                                                               u,
                                                               v)))
                    }
                    (true, _, false) => {
                        return Err(DimacsError::Format(0,
                                                       format!("edge ({},{}) should not be contained in the graph (too long)",
                                                               u,
                                                               v)))
                    }
                    _ => (),
                }
            }
        }
    }

    Ok((g, weights))
}


fn dist(x: &[f64], y: &[f64], metric: Metric) -> f64 {
    let mut d: f64 = 0.0;
    match metric {
        Metric::LINF => {
            for i in 0..x.len() {
                d = f64::max(d, f64::abs(x[i] - y[i]));
            }
        }
        Metric::L2S => {
            for i in 0..x.len() {
                d += (x[i] - y[i]) * (x[i] - y[i]);
            }
        }
        Metric::L(p) => {
            for i in 0..x.len() {
                d += (x[i] - y[i]).abs().powf(p);
            }
            d = d.powf(1.0 / p);
        }
    }
    d
}

#[cfg(test)]
mod tests {
    use super::read_dimacs;
    use super::read_from_buf;
    use {Graph, IndexGraph, LinkedListGraph};
    use std::io::Cursor;

    #[test]
    fn test_read() {
        let file = "
c some comment

p edge 12 5
";
        read_dimacs(&mut Cursor::new(file),
                    &mut |c, toks| {
                        assert_eq!(c, 'p');
                        assert_eq!(toks.next(), Some("edge"));
                        assert_eq!(toks.number::<usize>().unwrap(), 12);
                        assert_eq!(toks.number::<usize>().unwrap(), 5);
                        assert_eq!(toks.next(), None);
                        Ok(())
                    })
            .unwrap();
    }

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

p edge 6 9
  n 1 12
n 6 42.23

c there might be empty lines

e 1 4
e 1 5
e 1 6
e 2 4
e 2 5
e 2 6
e 3 4
e 3 5
e 3 6

d 2 L2
v 1 1
v 1 2
v 1 3
v 10 1
v 10 2
v 10 3

x MINLENGTH 5
x MAXLENGTH 100

c end of the file
";
        let (g, weights) = read_from_buf::<_, LinkedListGraph>(&mut Cursor::new(file)).unwrap();
        let weights = nodevec![&g, weights];

        assert_eq!(g.num_nodes(), 6);
        assert_eq!(g.num_edges(), 9);

        for u in 0..3 {
            let mut vs: Vec<_> = g.neighs(g.id2node(u)).map(|(_,v)| g.node_id(v)).collect();
            vs.sort();
            assert_eq!(vs, vec![3, 4, 5]);
        }

        for v in 3..6 {
            let mut vs: Vec<_> = g.neighs(g.id2node(v)).map(|(_,v)| g.node_id(v)).collect();
            vs.sort();
            assert_eq!(vs, vec![0, 1, 2]);
        }

        for u in g.nodes() {
            match (g.node_id(u), weights[u]) {
                (0, w) => assert_eq!(w, 12.0),
                (5, w) => assert_eq!(w, 42.23),
                (_, w) => assert_eq!(w, 0.0),
            }
        }
    }
}