Struct NetworkSimplex 

pub struct NetworkSimplex<F, C> {
    n: usize,
    edges: Vec<Edge<F, C>>,
    lowers: Vec<F>,
    dss: Vec<F>,
    bucket_size: Option<usize>,
    minor_limit: Option<usize>,
}

Fields

n: usize

edges: Vec<Edge<F, C>>

lowers: Vec<F>

dss: Vec<F>

bucket_size: Option<usize>

minor_limit: Option<usize>

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/min_cost_b_flow.rs (line 8)

pub fn min_cost_b_flow(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m, b: [i64; iter n]);
    let mut ns = NetworkSimplex::<i64, i128>::new(n);
    for (i, b) in b.enumerate() {
        ns.add_demand_supply(i, b);
    }
    sc!(edges: [(usize, usize, i64, i64, i128); iter m]);
    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 {
        pp!(@lf sol.cost, @it sol.potentials, @it sol.flows);
    } else {
        pp!("infeasible");
    }
}

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

Add demand

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

Add supply

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 10)

pub fn min_cost_b_flow(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m, b: [i64; iter n]);
    let mut ns = NetworkSimplex::<i64, i128>::new(n);
    for (i, b) in b.enumerate() {
        ns.add_demand_supply(i, b);
    }
    sc!(edges: [(usize, usize, i64, i64, i128); iter m]);
    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 {
        pp!(@lf sol.cost, @it sol.potentials, @it sol.flows);
    } else {
        pp!("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/min_cost_b_flow.rs (line 14)

pub fn min_cost_b_flow(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m, b: [i64; iter n]);
    let mut ns = NetworkSimplex::<i64, i128>::new(n);
    for (i, b) in b.enumerate() {
        ns.add_demand_supply(i, b);
    }
    sc!(edges: [(usize, usize, i64, i64, i128); iter m]);
    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 {
        pp!(@lf sol.cost, @it sol.potentials, @it sol.flows);
    } else {
        pp!("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/min_cost_b_flow.rs (line 16)

pub fn min_cost_b_flow(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m, b: [i64; iter n]);
    let mut ns = NetworkSimplex::<i64, i128>::new(n);
    for (i, b) in b.enumerate() {
        ns.add_demand_supply(i, b);
    }
    sc!(edges: [(usize, usize, i64, i64, i128); iter m]);
    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 {
        pp!(@lf sol.cost, @it sol.potentials, @it sol.flows);
    } else {
        pp!("infeasible");
    }
}

Trait Implementations

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

fn clone(&self) -> Self

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.