NetworkSimplexSolver

competitive::graph::network_simplex

Struct NetworkSimplexSolver 

Source 
struct NetworkSimplexSolver<F, C> {
Show 13 fields
    n: usize,
    m: usize,
    edges: Vec<Edge<F, C>>,
    lowers: Vec<F>,
    dss: Vec<F>,
    bucket_size: usize,
    minor_limit: usize,
    potentials: Vec<C>,
    parents: Vec<Parent<F>>,
    depth: Vec<usize>,
    next: Vec<usize>,
    prev: Vec<usize>,
    candidates: Vec<usize>,

}

Fields§

§n: usize§m: usize§edges: Vec<Edge<F, C>>§lowers: Vec<F>§dss: Vec<F>§bucket_size: usize§minor_limit: usize§potentials: Vec<C>§parents: Vec<Parent<F>>§depth: Vec<usize>§next: Vec<usize>§prev: Vec<usize>§candidates: Vec<usize>

Implementations§

Source§

impl<F, C> NetworkSimplexSolver<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>,

Source

fn connect(&mut self, a: usize, b: usize)

Examples found in repository?
crates/competitive/src/graph/network_simplex.rs (line 245)
156    fn build(ns: NetworkSimplex<F, C>) -> Self {
157        let NetworkSimplex {
158            n,
159            mut edges,
160            lowers,
161            dss,
162            bucket_size,
163            minor_limit,
164        } = ns;
165
166        let m = edges.len();
167        let bucket_size =
168            bucket_size.unwrap_or_else(|| (((m as f64).sqrt() * 0.2) as usize).max(10));
169        let minor_limit =
170            minor_limit.unwrap_or_else(|| (((bucket_size as f64) * 0.1) as usize).max(3));
171
172        let mut potentials = vec![C::zero(); n + 1];
173        let mut parents = vec![
174            Parent {
175                par: 0,
176                eid: 0,
177                up: F::zero(),
178                down: F::zero(),
179            };
180            n
181        ];
182        let inf_cost = edges.iter().step_by(2).fold(C::one(), |acc, edge| {
183            acc + if edge.cost >= C::zero() {
184                edge.cost
185            } else {
186                -edge.cost
187            }
188        });
189        edges.reserve(m + n * 2);
190        let super_node = n;
191        for v in 0..n {
192            let eid = edges.len();
193            if dss[v] >= F::zero() {
194                edges.push(Edge {
195                    to: super_node,
196                    cap: F::zero(),
197                    cost: inf_cost,
198                });
199                edges.push(Edge {
200                    to: v,
201                    cap: dss[v],
202                    cost: -inf_cost,
203                });
204                potentials[v] = -inf_cost;
205            } else {
206                edges.push(Edge {
207                    to: super_node,
208                    cap: F::zero() - dss[v],
209                    cost: -inf_cost,
210                });
211                edges.push(Edge {
212                    to: v,
213                    cap: F::zero(),
214                    cost: inf_cost,
215                });
216                potentials[v] = inf_cost;
217            }
218            parents[v] = Parent {
219                par: super_node,
220                eid,
221                up: edges[eid].cap,
222                down: edges[eid ^ 1].cap,
223            };
224        }
225
226        let mut depth = vec![1; n + 1];
227        depth[super_node] = 0;
228
229        let mut this = NetworkSimplexSolver {
230            n,
231            m,
232            edges,
233            lowers,
234            dss,
235            bucket_size,
236            minor_limit,
237            parents,
238            depth,
239            next: vec![0; (n + 1) * 2],
240            prev: vec![0; (n + 1) * 2],
241            candidates: Vec::with_capacity(bucket_size),
242            potentials,
243        };
244        for v in 0..=n {
245            this.connect(v * 2, v * 2 + 1);
246        }
247        for v in 0..n {
248            this.connect(v * 2 + 1, this.next[super_node * 2]);
249            this.connect(super_node * 2, v * 2);
250        }
251        this
252    }
253
254    fn solve(mut self) -> Option<NetworkSimplexSolution<F, C>> {
255        let mut eid = 0usize;
256        loop {
257            for _ in 0..self.minor_limit {
258                if !self.minor() {
259                    break;
260                }
261            }
262            let mut best = C::zero();
263            let mut best_eid: Option<usize> = None;
264            self.candidates.clear();
265            for _ in 0..self.edges.len() {
266                if !self.edges[eid].cap.is_zero() {
267                    let clen = self.edges[eid].cost + self.potentials[self.edges[eid ^ 1].to]
268                        - self.potentials[self.edges[eid].to];
269                    if clen < C::zero() {
270                        if best_eid.is_none() || clen < best {
271                            best = clen;
272                            best_eid = Some(eid);
273                        }
274                        self.candidates.push(eid);
275                        if self.candidates.len() == self.bucket_size {
276                            break;
277                        }
278                    }
279                }
280                eid += 1;
281                if eid == self.edges.len() {
282                    eid = 0;
283                }
284            }
285            if self.candidates.is_empty() {
286                break;
287            }
288            if let Some(be) = best_eid {
289                self.push_flow(be);
290            }
291        }
292        for i in 0..self.n {
293            let eid = self.parents[i].eid;
294            self.edges[eid].cap = self.parents[i].up;
295            self.edges[eid ^ 1].cap = self.parents[i].down;
296        }
297        self.generate_solution()
298    }
299
300    fn minor(&mut self) -> bool {
301        if self.candidates.is_empty() {
302            return false;
303        }
304        let mut best = C::zero();
305        let mut best_eid: Option<usize> = None;
306        let mut i = 0usize;
307        while i < self.candidates.len() {
308            let eid = self.candidates[i];
309            if self.edges[eid].cap.is_zero() {
310                self.candidates.swap_remove(i);
311                continue;
312            }
313            let clen = self.edges[eid].cost + self.potentials[self.edges[eid ^ 1].to]
314                - self.potentials[self.edges[eid].to];
315            if clen >= C::zero() {
316                self.candidates.swap_remove(i);
317                continue;
318            }
319            if best_eid.is_none() || clen < best {
320                best = clen;
321                best_eid = Some(eid);
322            }
323            i += 1;
324        }
325        if let Some(best_eid) = best_eid {
326            self.push_flow(best_eid);
327            true
328        } else {
329            false
330        }
331    }
332
333    fn get_lca(
334        &self,
335        mut u: usize,
336        mut v: usize,
337        flow: &mut F,
338        del_u_side: &mut bool,
339        del_u: &mut usize,
340    ) -> usize {
341        if self.depth[u] >= self.depth[v] {
342            for _ in 0..self.depth[u] - self.depth[v] {
343                if self.parents[u].down < *flow {
344                    *flow = self.parents[u].down;
345                    *del_u = u;
346                    *del_u_side = true;
347                }
348                u = self.parents[u].par;
349            }
350        } else {
351            for _ in 0..self.depth[v] - self.depth[u] {
352                if self.parents[v].up <= *flow {
353                    *flow = self.parents[v].up;
354                    *del_u = v;
355                    *del_u_side = false;
356                }
357                v = self.parents[v].par;
358            }
359        }
360        while u != v {
361            if self.parents[u].down < *flow {
362                *flow = self.parents[u].down;
363                *del_u = u;
364                *del_u_side = true;
365            }
366            u = self.parents[u].par;
367            if self.parents[v].up <= *flow {
368                *flow = self.parents[v].up;
369                *del_u = v;
370                *del_u_side = false;
371            }
372            v = self.parents[v].par;
373        }
374        u
375    }
376
377    fn push_flow(&mut self, eid: usize) {
378        let u0 = self.edges[eid ^ 1].to;
379        let v0 = self.edges[eid].to;
380        let mut del_u = v0;
381        let mut flow = self.edges[eid].cap;
382        let mut del_u_side = true;
383        let lca = self.get_lca(u0, v0, &mut flow, &mut del_u_side, &mut del_u);
384        if !flow.is_zero() {
385            let mut u = u0;
386            let mut v = v0;
387            while u != lca {
388                self.parents[u].up += flow;
389                self.parents[u].down -= flow;
390                u = self.parents[u].par;
391            }
392            while v != lca {
393                self.parents[v].up -= flow;
394                self.parents[v].down += flow;
395                v = self.parents[v].par;
396            }
397        }
398        let mut u = u0;
399        let mut par = v0;
400        let mut p_caps = (self.edges[eid].cap - flow, self.edges[eid ^ 1].cap + flow);
401        let mut p_diff = -(self.edges[eid].cost + self.potentials[u0] - self.potentials[v0]);
402        if !del_u_side {
403            swap(&mut u, &mut par);
404            swap(&mut p_caps.0, &mut p_caps.1);
405            p_diff = -p_diff;
406        }
407        let mut par_eid = eid ^ if del_u_side { 0 } else { 1 };
408        while par != del_u {
409            let mut d = self.depth[par];
410            let mut idx = u * 2;
411            while idx != u * 2 + 1 {
412                if idx.is_multiple_of(2) {
413                    d += 1;
414                    self.potentials[idx / 2] += p_diff;
415                    self.depth[idx / 2] = d;
416                } else {
417                    d -= 1;
418                }
419                idx = self.next[idx];
420            }
421            self.connect(self.prev[u * 2], self.next[u * 2 + 1]);
422            self.connect(u * 2 + 1, self.next[par * 2]);
423            self.connect(par * 2, u * 2);
424            swap(&mut self.parents[u].eid, &mut par_eid);
425            par_eid ^= 1;
426            swap(&mut self.parents[u].up, &mut p_caps.0);
427            swap(&mut self.parents[u].down, &mut p_caps.1);
428            swap(&mut p_caps.0, &mut p_caps.1);
429            let next_u = self.parents[u].par;
430            self.parents[u].par = par;
431            par = u;
432            u = next_u;
433        }
434        self.edges[par_eid].cap = p_caps.0;
435        self.edges[par_eid ^ 1].cap = p_caps.1;
436    }
Source

fn build(ns: NetworkSimplex<F, C>) -> Self

Examples found in repository?
crates/competitive/src/graph/network_simplex.rs (line 92)
91    pub fn solve_minimize(self) -> Option<NetworkSimplexSolution<F, C>> {
92        NetworkSimplexSolver::build(self).solve()
93    }
Source

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

Examples found in repository?
crates/competitive/src/graph/network_simplex.rs (line 92)
91    pub fn solve_minimize(self) -> Option<NetworkSimplexSolution<F, C>> {
92        NetworkSimplexSolver::build(self).solve()
93    }
Source

fn minor(&mut self) -> bool

Examples found in repository?
crates/competitive/src/graph/network_simplex.rs (line 258)
254    fn solve(mut self) -> Option<NetworkSimplexSolution<F, C>> {
255        let mut eid = 0usize;
256        loop {
257            for _ in 0..self.minor_limit {
258                if !self.minor() {
259                    break;
260                }
261            }
262            let mut best = C::zero();
263            let mut best_eid: Option<usize> = None;
264            self.candidates.clear();
265            for _ in 0..self.edges.len() {
266                if !self.edges[eid].cap.is_zero() {
267                    let clen = self.edges[eid].cost + self.potentials[self.edges[eid ^ 1].to]
268                        - self.potentials[self.edges[eid].to];
269                    if clen < C::zero() {
270                        if best_eid.is_none() || clen < best {
271                            best = clen;
272                            best_eid = Some(eid);
273                        }
274                        self.candidates.push(eid);
275                        if self.candidates.len() == self.bucket_size {
276                            break;
277                        }
278                    }
279                }
280                eid += 1;
281                if eid == self.edges.len() {
282                    eid = 0;
283                }
284            }
285            if self.candidates.is_empty() {
286                break;
287            }
288            if let Some(be) = best_eid {
289                self.push_flow(be);
290            }
291        }
292        for i in 0..self.n {
293            let eid = self.parents[i].eid;
294            self.edges[eid].cap = self.parents[i].up;
295            self.edges[eid ^ 1].cap = self.parents[i].down;
296        }
297        self.generate_solution()
298    }
Source

fn get_lca( &self, u: usize, v: usize, flow: &mut F, del_u_side: &mut bool, del_u: &mut usize, ) -> usize

Examples found in repository?
crates/competitive/src/graph/network_simplex.rs (line 383)
377    fn push_flow(&mut self, eid: usize) {
378        let u0 = self.edges[eid ^ 1].to;
379        let v0 = self.edges[eid].to;
380        let mut del_u = v0;
381        let mut flow = self.edges[eid].cap;
382        let mut del_u_side = true;
383        let lca = self.get_lca(u0, v0, &mut flow, &mut del_u_side, &mut del_u);
384        if !flow.is_zero() {
385            let mut u = u0;
386            let mut v = v0;
387            while u != lca {
388                self.parents[u].up += flow;
389                self.parents[u].down -= flow;
390                u = self.parents[u].par;
391            }
392            while v != lca {
393                self.parents[v].up -= flow;
394                self.parents[v].down += flow;
395                v = self.parents[v].par;
396            }
397        }
398        let mut u = u0;
399        let mut par = v0;
400        let mut p_caps = (self.edges[eid].cap - flow, self.edges[eid ^ 1].cap + flow);
401        let mut p_diff = -(self.edges[eid].cost + self.potentials[u0] - self.potentials[v0]);
402        if !del_u_side {
403            swap(&mut u, &mut par);
404            swap(&mut p_caps.0, &mut p_caps.1);
405            p_diff = -p_diff;
406        }
407        let mut par_eid = eid ^ if del_u_side { 0 } else { 1 };
408        while par != del_u {
409            let mut d = self.depth[par];
410            let mut idx = u * 2;
411            while idx != u * 2 + 1 {
412                if idx.is_multiple_of(2) {
413                    d += 1;
414                    self.potentials[idx / 2] += p_diff;
415                    self.depth[idx / 2] = d;
416                } else {
417                    d -= 1;
418                }
419                idx = self.next[idx];
420            }
421            self.connect(self.prev[u * 2], self.next[u * 2 + 1]);
422            self.connect(u * 2 + 1, self.next[par * 2]);
423            self.connect(par * 2, u * 2);
424            swap(&mut self.parents[u].eid, &mut par_eid);
425            par_eid ^= 1;
426            swap(&mut self.parents[u].up, &mut p_caps.0);
427            swap(&mut self.parents[u].down, &mut p_caps.1);
428            swap(&mut p_caps.0, &mut p_caps.1);
429            let next_u = self.parents[u].par;
430            self.parents[u].par = par;
431            par = u;
432            u = next_u;
433        }
434        self.edges[par_eid].cap = p_caps.0;
435        self.edges[par_eid ^ 1].cap = p_caps.1;
436    }
Source

fn push_flow(&mut self, eid: usize)

Examples found in repository?
crates/competitive/src/graph/network_simplex.rs (line 289)
254    fn solve(mut self) -> Option<NetworkSimplexSolution<F, C>> {
255        let mut eid = 0usize;
256        loop {
257            for _ in 0..self.minor_limit {
258                if !self.minor() {
259                    break;
260                }
261            }
262            let mut best = C::zero();
263            let mut best_eid: Option<usize> = None;
264            self.candidates.clear();
265            for _ in 0..self.edges.len() {
266                if !self.edges[eid].cap.is_zero() {
267                    let clen = self.edges[eid].cost + self.potentials[self.edges[eid ^ 1].to]
268                        - self.potentials[self.edges[eid].to];
269                    if clen < C::zero() {
270                        if best_eid.is_none() || clen < best {
271                            best = clen;
272                            best_eid = Some(eid);
273                        }
274                        self.candidates.push(eid);
275                        if self.candidates.len() == self.bucket_size {
276                            break;
277                        }
278                    }
279                }
280                eid += 1;
281                if eid == self.edges.len() {
282                    eid = 0;
283                }
284            }
285            if self.candidates.is_empty() {
286                break;
287            }
288            if let Some(be) = best_eid {
289                self.push_flow(be);
290            }
291        }
292        for i in 0..self.n {
293            let eid = self.parents[i].eid;
294            self.edges[eid].cap = self.parents[i].up;
295            self.edges[eid ^ 1].cap = self.parents[i].down;
296        }
297        self.generate_solution()
298    }
299
300    fn minor(&mut self) -> bool {
301        if self.candidates.is_empty() {
302            return false;
303        }
304        let mut best = C::zero();
305        let mut best_eid: Option<usize> = None;
306        let mut i = 0usize;
307        while i < self.candidates.len() {
308            let eid = self.candidates[i];
309            if self.edges[eid].cap.is_zero() {
310                self.candidates.swap_remove(i);
311                continue;
312            }
313            let clen = self.edges[eid].cost + self.potentials[self.edges[eid ^ 1].to]
314                - self.potentials[self.edges[eid].to];
315            if clen >= C::zero() {
316                self.candidates.swap_remove(i);
317                continue;
318            }
319            if best_eid.is_none() || clen < best {
320                best = clen;
321                best_eid = Some(eid);
322            }
323            i += 1;
324        }
325        if let Some(best_eid) = best_eid {
326            self.push_flow(best_eid);
327            true
328        } else {
329            false
330        }
331    }
Source

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

Examples found in repository?
crates/competitive/src/graph/network_simplex.rs (line 297)
254    fn solve(mut self) -> Option<NetworkSimplexSolution<F, C>> {
255        let mut eid = 0usize;
256        loop {
257            for _ in 0..self.minor_limit {
258                if !self.minor() {
259                    break;
260                }
261            }
262            let mut best = C::zero();
263            let mut best_eid: Option<usize> = None;
264            self.candidates.clear();
265            for _ in 0..self.edges.len() {
266                if !self.edges[eid].cap.is_zero() {
267                    let clen = self.edges[eid].cost + self.potentials[self.edges[eid ^ 1].to]
268                        - self.potentials[self.edges[eid].to];
269                    if clen < C::zero() {
270                        if best_eid.is_none() || clen < best {
271                            best = clen;
272                            best_eid = Some(eid);
273                        }
274                        self.candidates.push(eid);
275                        if self.candidates.len() == self.bucket_size {
276                            break;
277                        }
278                    }
279                }
280                eid += 1;
281                if eid == self.edges.len() {
282                    eid = 0;
283                }
284            }
285            if self.candidates.is_empty() {
286                break;
287            }
288            if let Some(be) = best_eid {
289                self.push_flow(be);
290            }
291        }
292        for i in 0..self.n {
293            let eid = self.parents[i].eid;
294            self.edges[eid].cap = self.parents[i].up;
295            self.edges[eid ^ 1].cap = self.parents[i].down;
296        }
297        self.generate_solution()
298    }

Trait Implementations§

Source§

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

Source§

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<F, C> Freeze for NetworkSimplexSolver<F, C>

§

impl<F, C> RefUnwindSafe for NetworkSimplexSolver<F, C>
where F: RefUnwindSafe, C: RefUnwindSafe,

§

impl<F, C> Send for NetworkSimplexSolver<F, C>
where F: Send, C: Send,

§

impl<F, C> Sync for NetworkSimplexSolver<F, C>
where F: Sync, C: Sync,

§

impl<F, C> Unpin for NetworkSimplexSolver<F, C>
where F: Unpin, C: Unpin,

§

impl<F, C> UnwindSafe for NetworkSimplexSolver<F, C>
where F: UnwindSafe, C: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.