Struct NetworkSimplex 

pub struct NetworkSimplex<F, C> { /* private fields */ }

Implementations

impl<F, C> NetworkSimplex<F, C>

where F: Copy + PartialOrd + Zero + Add<Output = F> + Sub<Output = F> + AddAssign + SubAssign, C: Copy + PartialOrd + Zero + One + Add<Output = C> + Sub<Output = C> + AddAssign + SubAssign + Neg<Output = C> + Mul<Output = C> + From<F>,

pub fn new(n: usize) -> Self

Examples found in repository

crates/library_checker/src/graph/assignment.rs (line 10)

pub fn assignment(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, a: [[i64; n]; n]);
    let mut ns = NetworkSimplex::<i64, i64>::new(n * 2);
    for (i, a) in a.iter().enumerate() {
        ns.add_supply(i, 1);
        ns.add_demand(i + n, 1);
        for (j, &a) in a.iter().enumerate() {
            ns.add_edge(i, j + n, 0, 1, a);
        }
    }
    let sol = ns.solve_minimize();
    if let Some(sol) = sol {
        iter_print!(writer, sol.cost);
        let p = (0..n * n)
            .filter(|&eid| sol.flows[eid] != 0)
            .map(|eid| eid % n);
        iter_print!(writer, @it p);
    } else {
        iter_print!(writer, "infeasible");
    }
}

crates/library_checker/src/graph/min_cost_b_flow.rs (line 10)

pub fn min_cost_b_flow(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, m, b: [i64; n], edges: [(usize, usize, i64, i64, i128); m]);
    let mut ns = NetworkSimplex::<i64, i128>::new(n);
    for (i, b) in b.into_iter().enumerate() {
        ns.add_demand_supply(i, b);
    }
    for (s, t, l, u, c) in edges {
        ns.add_edge(s, t, l, u, c);
    }
    let sol = ns.solve_minimize();
    if let Some(sol) = sol {
        iter_print!(writer, sol.cost);
        for i in 0..n {
            iter_print!(writer, sol.potentials[i]);
        }
        for i in 0..m {
            iter_print!(writer, sol.flows[i]);
        }
    } else {
        iter_print!(writer, "infeasible");
    }
}

pub fn add_demand(&mut self, vid: usize, demand: F)

Add demand

Examples found in repository

crates/library_checker/src/graph/assignment.rs (line 13)

pub fn assignment(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, a: [[i64; n]; n]);
    let mut ns = NetworkSimplex::<i64, i64>::new(n * 2);
    for (i, a) in a.iter().enumerate() {
        ns.add_supply(i, 1);
        ns.add_demand(i + n, 1);
        for (j, &a) in a.iter().enumerate() {
            ns.add_edge(i, j + n, 0, 1, a);
        }
    }
    let sol = ns.solve_minimize();
    if let Some(sol) = sol {
        iter_print!(writer, sol.cost);
        let p = (0..n * n)
            .filter(|&eid| sol.flows[eid] != 0)
            .map(|eid| eid % n);
        iter_print!(writer, @it p);
    } else {
        iter_print!(writer, "infeasible");
    }
}

pub fn add_supply(&mut self, vid: usize, supply: F)

Add supply

Examples found in repository

crates/library_checker/src/graph/assignment.rs (line 12)

pub fn assignment(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, a: [[i64; n]; n]);
    let mut ns = NetworkSimplex::<i64, i64>::new(n * 2);
    for (i, a) in a.iter().enumerate() {
        ns.add_supply(i, 1);
        ns.add_demand(i + n, 1);
        for (j, &a) in a.iter().enumerate() {
            ns.add_edge(i, j + n, 0, 1, a);
        }
    }
    let sol = ns.solve_minimize();
    if let Some(sol) = sol {
        iter_print!(writer, sol.cost);
        let p = (0..n * n)
            .filter(|&eid| sol.flows[eid] != 0)
            .map(|eid| eid % n);
        iter_print!(writer, @it p);
    } else {
        iter_print!(writer, "infeasible");
    }
}

pub fn add_demand_supply(&mut self, vid: usize, ds: F)

Add demand/supply (positive for supply, negative for demand)

Examples found in repository

crates/library_checker/src/graph/min_cost_b_flow.rs (line 12)

pub fn min_cost_b_flow(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, m, b: [i64; n], edges: [(usize, usize, i64, i64, i128); m]);
    let mut ns = NetworkSimplex::<i64, i128>::new(n);
    for (i, b) in b.into_iter().enumerate() {
        ns.add_demand_supply(i, b);
    }
    for (s, t, l, u, c) in edges {
        ns.add_edge(s, t, l, u, c);
    }
    let sol = ns.solve_minimize();
    if let Some(sol) = sol {
        iter_print!(writer, sol.cost);
        for i in 0..n {
            iter_print!(writer, sol.potentials[i]);
        }
        for i in 0..m {
            iter_print!(writer, sol.flows[i]);
        }
    } else {
        iter_print!(writer, "infeasible");
    }
}

pub fn add_edge(&mut self, from: usize, to: usize, lower: F, upper: F, cost: C)

Add edge with lower/upper capacity and cost

Examples found in repository

crates/library_checker/src/graph/assignment.rs (line 15)

pub fn assignment(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, a: [[i64; n]; n]);
    let mut ns = NetworkSimplex::<i64, i64>::new(n * 2);
    for (i, a) in a.iter().enumerate() {
        ns.add_supply(i, 1);
        ns.add_demand(i + n, 1);
        for (j, &a) in a.iter().enumerate() {
            ns.add_edge(i, j + n, 0, 1, a);
        }
    }
    let sol = ns.solve_minimize();
    if let Some(sol) = sol {
        iter_print!(writer, sol.cost);
        let p = (0..n * n)
            .filter(|&eid| sol.flows[eid] != 0)
            .map(|eid| eid % n);
        iter_print!(writer, @it p);
    } else {
        iter_print!(writer, "infeasible");
    }
}

crates/library_checker/src/graph/min_cost_b_flow.rs (line 15)

pub fn min_cost_b_flow(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, m, b: [i64; n], edges: [(usize, usize, i64, i64, i128); m]);
    let mut ns = NetworkSimplex::<i64, i128>::new(n);
    for (i, b) in b.into_iter().enumerate() {
        ns.add_demand_supply(i, b);
    }
    for (s, t, l, u, c) in edges {
        ns.add_edge(s, t, l, u, c);
    }
    let sol = ns.solve_minimize();
    if let Some(sol) = sol {
        iter_print!(writer, sol.cost);
        for i in 0..n {
            iter_print!(writer, sol.potentials[i]);
        }
        for i in 0..m {
            iter_print!(writer, sol.flows[i]);
        }
    } else {
        iter_print!(writer, "infeasible");
    }
}

pub fn set_bucket_size(&mut self, size: usize)

pub fn set_minor_limit(&mut self, limit: usize)

pub fn solve_minimize(self) -> Option<NetworkSimplexSolution<F, C>>

Examples found in repository

crates/library_checker/src/graph/assignment.rs (line 18)

pub fn assignment(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, a: [[i64; n]; n]);
    let mut ns = NetworkSimplex::<i64, i64>::new(n * 2);
    for (i, a) in a.iter().enumerate() {
        ns.add_supply(i, 1);
        ns.add_demand(i + n, 1);
        for (j, &a) in a.iter().enumerate() {
            ns.add_edge(i, j + n, 0, 1, a);
        }
    }
    let sol = ns.solve_minimize();
    if let Some(sol) = sol {
        iter_print!(writer, sol.cost);
        let p = (0..n * n)
            .filter(|&eid| sol.flows[eid] != 0)
            .map(|eid| eid % n);
        iter_print!(writer, @it p);
    } else {
        iter_print!(writer, "infeasible");
    }
}

crates/library_checker/src/graph/min_cost_b_flow.rs (line 17)

pub fn min_cost_b_flow(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, m, b: [i64; n], edges: [(usize, usize, i64, i64, i128); m]);
    let mut ns = NetworkSimplex::<i64, i128>::new(n);
    for (i, b) in b.into_iter().enumerate() {
        ns.add_demand_supply(i, b);
    }
    for (s, t, l, u, c) in edges {
        ns.add_edge(s, t, l, u, c);
    }
    let sol = ns.solve_minimize();
    if let Some(sol) = sol {
        iter_print!(writer, sol.cost);
        for i in 0..n {
            iter_print!(writer, sol.potentials[i]);
        }
        for i in 0..m {
            iter_print!(writer, sol.flows[i]);
        }
    } else {
        iter_print!(writer, "infeasible");
    }
}

Trait Implementations

impl<F: Clone, C: Clone> Clone for NetworkSimplex<F, C>

fn clone(&self) -> NetworkSimplex<F, C>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<F: Debug, C: Debug> Debug for NetworkSimplex<F, C>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.