const START: usize = 1;
const END: usize = 5;

fn main() {

    /*let mut edges = [
        (1, 3, 6, 6),
        (1, 2, 5, 5),
        (1, 4, 5, 5),
        (2, 5, 3, 3),
        (2, 3, 2, 2),
        (4, 3, 3, 3),
        (4, 6, 5, 5),
        (3, 5, 3, 3),
        (3, 6, 7, 7),
        (5, 7, 8, 8),
        (5, 6, 1, 1),
        (6, 7, 7, 7)
    ];*/

    let mut edges = [
        (1, 2, 20, 0),
        (1, 3, 30, 0),
        (1, 4, 10, 0),
        (2, 3, 40, 0),
        (2, 5, 30, 0),
        (3, 5, 20, 0),
        (3, 4, 10, 5),
        (4, 5, 20, 0)
    ];

    let mut paths: Vec<(Vec<usize>, usize)> = Vec::new();
    while let Some((vec, min)) = traverse(START, edges.iter(), (Vec::new(), 0)) {
        paths.push((vec.clone(), min));
        let c_edges = edges.clone();
        let mut enumeration = c_edges.iter().enumerate().collect::<Vec<_>>();
        for (&n1, &n2) in vec.iter().zip(vec.iter().skip(1)) {
            let c_enumeration = enumeration.clone();
            let path = c_enumeration.iter().find(|&&(_, &(on1, on2, _, _))|
                n1 == on1 && n2 == on2 || n1 == on2 && n2 == on1).unwrap();
            match path {
                &(index, &(on1, on2, _, _)) if n1 == on1 && n2 == on2 => {
                    edges[index].2 -= min;
                    edges[index].3 += min;
                }
                &(index, &(on1, on2, _, _)) if n1 == on2 && n2 == on1 => {
                    edges[index].3 -= min;
                    edges[index].2 += min;
                }
                _  => {}
            }
            enumeration = enumeration.iter().filter(|&p| p != path).cloned().collect();
        }
    }
    println!("{:?}\nMaximum flow: {}",
        paths, paths.clone().iter().fold(0, |acc, &(_, min)| acc + min));
}


fn traverse<'a, I>(current_node: usize, iter: I, state: (Vec<usize>, usize)) ->
    Option<(Vec<usize>, usize)>
    where I: Iterator<Item=&'a (usize, usize, usize, usize)> + Clone {
    let mut vec = state.0.clone();
    vec.push(current_node);

    if current_node == END {
        return Some((vec.clone(), state.1));
    }

    let paths = iter.clone()
        .filter(|&&(n1, n2, _, _)| n1 == current_node || n2 == current_node)
        .map(|p| {
            if p.0 == current_node { (p.1, p.2, p) }
            else { (p.0, p.3, p) }
        });

    paths
        .filter(|&(next,val,_)| !vec.iter().any(|&n| n == next) && val != 0)
        .map(|(next, val, path)| traverse(next,
            iter.clone().filter(|&p| p != path).collect::<Vec<_>>().into_iter(),
            (vec.clone(), if state.1 == 0 || val < state.1 { val } else { state.1 })))
        .find(|opt| opt.is_some() &&
            opt.as_ref().unwrap().0.clone().pop().unwrap() == END).unwrap_or(None)
}