use super::{read_dimacs, DimacsError};
use crate::{Buildable, Builder};
use std::cmp::{max, min};
use std::collections::HashSet;
use std::f64;
use std::fs;
use std::io::{BufRead, BufReader};
#[derive(Copy, Clone, PartialEq, Debug)]
pub enum Metric {
LINF,
L(f64),
L2S,
}
#[derive(PartialEq, Debug)]
pub enum Param {
MinLength(f64),
MaxLength(f64),
}
pub fn read<G>(fname: &str) -> Result<(G, Vec<f64>), DimacsError>
where
G: Buildable,
{
read_from_buf(&mut BufReader::new(fs::File::open(fname)?))
}
pub fn read_from_buf<R, G>(buf: &mut R) -> Result<(G, Vec<f64>), DimacsError>
where
R: BufRead,
G: Buildable,
{
let mut g = G::new_builder();
let mut weights = vec![];
let mut nnodes = 0;
let mut nedges = 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;
read_dimacs(buf, &mut |d, toks| {
if start {
if d != 'p' {
return Err(DimacsError::Format {
line: toks.line,
msg: 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 {
line: toks.line,
msg: format!("expected 'edge' in p line, got: {}", edge),
});
}
nnodes = toks.number()?;
nedges = toks.number()?;
toks.end()?;
g.reserve(nnodes, nedges);
gnodes = g.add_nodes(nnodes);
weights.clear();
weights.resize(nnodes, 0.0);
start = false;
} else {
match d {
'n' => {
let id: usize = toks.number()?;
let val = toks.number()?;
toks.end()?;
if id < 1 || id > nnodes {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("invalid node id {} (must be <= {})", id, nnodes),
});
}
if !nodes.insert(id) {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("duplicate node id {}", id),
});
}
weights[id - 1] = val;
}
'e' => {
let u: usize = toks.number()?;
let v: usize = toks.number()?;
toks.end()?;
if u < 1 || u > nnodes {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("invalid node id {} in edge", u),
});
}
if v < 1 || v > nnodes {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("invalid node id {} in edge", v),
});
}
if u == v {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("invalid loop ({},{}) in edge", u, u),
});
}
if !edges.insert((min(u, v), max(u, v))) {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("duplicate edge ({},{})", u, v),
});
}
g.add_edge(gnodes[u - 1], gnodes[v - 1]);
}
'd' => {
let d: usize = 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 {
line: toks.line,
msg: "invalid norm".to_string(),
});
}
};
if p <= 0.0 {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("p of p-norm must be > 0 (got: {})", p),
});
}
Metric::L(p)
}
Some(_) => {
return Err(DimacsError::Format {
line: toks.line,
msg: "invalid norm".to_string(),
});
}
None => {
return Err(DimacsError::Format {
line: toks.line,
msg: "missing norm".to_string(),
});
}
};
toks.end()?;
if d < 1 {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("invalid dimension {} < 1", d),
});
}
if dim > 0 {
return Err(DimacsError::Format {
line: toks.line,
msg: "duplicate dimension".to_string(),
});
}
dim = d;
metric = Some(m);
vertices.reserve(nnodes);
}
'v' => {
if dim == 0 {
return Err(DimacsError::Format {
line: toks.line,
msg: "missing dimension line before vertex line".to_string(),
});
}
let mut vs: Vec<f64> = Vec::new();
for _ in 0..dim {
vs.push(toks.number()?);
}
toks.end()?;
if dim != vs.len() {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("vertex line has too many entries {} (expected: {})", vs.len(), dim),
});
}
vertices.push(vs);
}
'x' => {
let par = toks.str()?;
let l: f64 = toks.number()?;
toks.end()?;
match par {
"MINLENGTH" => {
if minlength.is_some() {
return Err(DimacsError::Format {
line: toks.line,
msg: "duplicate parameter MINLENGTH".to_string(),
});
}
minlength = Some(l)
}
"MAXLENGTH" => {
if maxlength.is_some() {
return Err(DimacsError::Format {
line: toks.line,
msg: "duplicate parameter MAXLENGTH".to_string(),
});
}
maxlength = Some(l)
}
_ => {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("unknown parameter {}", par),
});
}
};
}
_ => {
return Err(DimacsError::Format {
line: toks.line,
msg: format!("invalid command {}", d),
});
}
}
}
Ok(())
})?;
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..nnodes {
for v in u + 1..nnodes {
let d = dist(&vertices[u], &vertices[v], metric);
if !edges.contains(&(u + 1, v + 1)) {
if d >= minl && d <= maxl {
return Err(DimacsError::Format {
line: 0,
msg: format!("edge ({},{}) should be contained in the graph", u, v),
});
}
} else {
if d < minl {
return Err(DimacsError::Format {
line: 0,
msg: format!("edge ({},{}) should not be contained in the graph (too short)", u, v),
});
}
if d > maxl {
return Err(DimacsError::Format {
line: 0,
msg: format!("edge ({},{}) should not be contained in the graph (too long)", u, v),
});
}
}
}
}
}
Ok((g.to_graph(), 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 crate::traits::{GraphSize, IndexGraph, Undirected};
use crate::vec::NodeVec;
use crate::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::new_from_vec(&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),
}
}
}
}