Skip to main content

BlossomMatching

competitive::graph::general_weighted_matching

Struct BlossomMatching

struct BlossomMatching {Show 18 fields
    n: usize,
    endpoint: Vec<usize>,
    weight: Vec<i64>,
    neighbend: Vec<Vec<usize>>,
    mate: Vec<usize>,
    label: Vec<i32>,
    labelend: Vec<usize>,
    inblossom: Vec<usize>,
    blossomparent: Vec<usize>,
    blossomchilds: Vec<Vec<usize>>,
    blossombase: Vec<usize>,
    blossomendps: Vec<Vec<usize>>,
    bestedge: Vec<usize>,
    blossombestedges: Vec<Vec<usize>>,
    unusedblossoms: Vec<usize>,
    dualvar: Vec<i64>,
    allowedge: Vec<bool>,
    queue: Vec<usize>,
}

Fields§

§n: usize§endpoint: Vec<usize>§weight: Vec<i64>§neighbend: Vec<Vec<usize>>§mate: Vec<usize>§label: Vec<i32>§labelend: Vec<usize>§inblossom: Vec<usize>§blossomparent: Vec<usize>§blossomchilds: Vec<Vec<usize>>§blossombase: Vec<usize>§blossomendps: Vec<Vec<usize>>§bestedge: Vec<usize>§blossombestedges: Vec<Vec<usize>>§unusedblossoms: Vec<usize>§dualvar: Vec<i64>§allowedge: Vec<bool>§queue: Vec<usize>

Implementations§

impl BlossomMatching

fn new( n: usize, endpoint: Vec<usize>, weight: Vec<i64>, neighbend: Vec<Vec<usize>>, ) -> Self

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 82)

50    fn compute(&mut self) {
51        if self.matching_weight != NEG_INF {
52            return;
53        }
54        let n = self.size;
55        if n == 0 {
56            self.matching_weight = 0;
57            return;
58        }
59        let mut edges = Vec::new();
60        let mut weights = Vec::new();
61        let mut neighbend = vec![Vec::new(); n];
62        for i in 0..n {
63            for j in i + 1..n {
64                let w = self.weight[i][j];
65                if w == NEG_INF {
66                    continue;
67                }
68                let k = weights.len();
69                weights.push(w);
70                edges.push(i);
71                edges.push(j);
72                neighbend[i].push(2 * k + 1);
73                neighbend[j].push(2 * k);
74            }
75        }
76        let m = weights.len();
77        if m == 0 {
78            self.mate.fill(!0);
79            self.matching_weight = 0;
80            return;
81        }
82        let mut blossom = BlossomMatching::new(n, edges, weights, neighbend);
83        blossom.solve(false);
84        self.mate.fill(!0);
85        let mut total = 0i64;
86        for v in 0..n {
87            let u = blossom.mate[v];
88            if u != !0 && v < u {
89                self.mate[v] = u;
90                self.mate[u] = v;
91                total += self.weight[v][u];
92            }
93        }
94        self.matching_weight = total;
95    }

fn slack(&self, k: usize) -> i64

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 319)

244    fn add_blossom(&mut self, base: usize, k: usize) {
245        let mut v = self.endpoint[2 * k];
246        let mut w = self.endpoint[2 * k + 1];
247        let bb = self.inblossom[base];
248        let mut bv = self.inblossom[v];
249        let mut bw = self.inblossom[w];
250        let b = self.unusedblossoms.pop().unwrap();
251        self.blossombase[b] = base;
252        self.blossomparent[b] = !0;
253        self.blossomparent[bb] = b;
254        self.blossomchilds[b].clear();
255        self.blossomendps[b].clear();
256        let mut path: Vec<usize> = Vec::new();
257        let mut endps: Vec<usize> = Vec::new();
258        while bv != bb {
259            self.blossomparent[bv] = b;
260            path.push(bv);
261            endps.push(self.labelend[bv]);
262            v = self.endpoint[self.labelend[bv]];
263            bv = self.inblossom[v];
264        }
265        path.push(bb);
266        path.reverse();
267        self.blossomchilds[b] = path.clone();
268        endps.reverse();
269        endps.push(2 * k);
270        self.blossomendps[b] = endps.clone();
271        while bw != bb {
272            self.blossomparent[bw] = b;
273            path.push(bw);
274            self.blossomchilds[b] = path.clone();
275            endps.push(self.labelend[bw] ^ 1);
276            self.blossomendps[b] = endps.clone();
277            w = self.endpoint[self.labelend[bw]];
278            bw = self.inblossom[w];
279        }
280        self.label[b] = 1;
281        self.labelend[b] = self.labelend[bb];
282        self.dualvar[b] = 0;
283        let mut leaves = Vec::new();
284        self.blossom_leaves(b, &mut leaves);
285        for v in leaves {
286            if self.label[self.inblossom[v]] == 2 {
287                self.queue.push(v);
288            }
289            self.inblossom[v] = b;
290        }
291        let mut bestedgeto = vec![!0; 2 * self.n];
292        for &bv in &path {
293            let nblists: Vec<Vec<usize>> = if self.blossombestedges[bv].is_empty() {
294                let mut lists = Vec::new();
295                let mut leaves = Vec::new();
296                self.blossom_leaves(bv, &mut leaves);
297                for v in leaves {
298                    let mut list = Vec::new();
299                    let neigh = self.neighbend[v].clone();
300                    for p in neigh {
301                        list.push(p / 2);
302                    }
303                    lists.push(list);
304                }
305                lists
306            } else {
307                vec![self.blossombestedges[bv].clone()]
308            };
309            for nblist in nblists {
310                for k in nblist {
311                    let mut i = self.endpoint[2 * k];
312                    let mut j = self.endpoint[2 * k + 1];
313                    if self.inblossom[j] == b {
314                        std::mem::swap(&mut i, &mut j);
315                    }
316                    let bj = self.inblossom[j];
317                    if bj != b
318                        && self.label[bj] == 1
319                        && (bestedgeto[bj] == !0 || self.slack(k) < self.slack(bestedgeto[bj]))
320                    {
321                        bestedgeto[bj] = k;
322                    }
323                }
324            }
325            self.blossombestedges[bv].clear();
326            self.bestedge[bv] = !0;
327        }
328        self.blossombestedges[b].clear();
329        for k in bestedgeto {
330            if k != !0 {
331                self.blossombestedges[b].push(k);
332            }
333        }
334        self.bestedge[b] = !0;
335        for &k in &self.blossombestedges[b] {
336            if self.bestedge[b] == !0 || self.slack(k) < self.slack(self.bestedge[b]) {
337                self.bestedge[b] = k;
338            }
339        }
340    }
341
342    fn step_index(len: usize, j: usize, forward: bool) -> usize {
343        if forward {
344            let next = j + 1;
345            if next == len { 0 } else { next }
346        } else if j == 0 {
347            len - 1
348        } else {
349            j - 1
350        }
351    }
352
353    fn dec_index(len: usize, j: usize) -> usize {
354        if j == 0 { len - 1 } else { j - 1 }
355    }
356
357    fn expand_blossom(&mut self, b: usize, endstage: bool) {
358        let childs = self.blossomchilds[b].clone();
359        for s in childs {
360            self.blossomparent[s] = !0;
361            if s < self.n {
362                self.inblossom[s] = s;
363            } else if endstage && self.dualvar[s] == 0 {
364                self.expand_blossom(s, endstage);
365            } else {
366                let mut leaves = Vec::new();
367                self.blossom_leaves(s, &mut leaves);
368                for v in leaves {
369                    self.inblossom[v] = s;
370                }
371            }
372        }
373        if !endstage && self.label[b] == 2 {
374            let entrychild = {
375                let p = self.labelend[b];
376                let u = self.endpoint[p ^ 1];
377                self.inblossom[u]
378            };
379            let len = self.blossomchilds[b].len();
380            let mut j = self.blossomchilds[b]
381                .iter()
382                .position(|&x| x == entrychild)
383                .unwrap();
384            let forward = j % 2 == 1;
385            let endptrick = if forward { 0usize } else { 1usize };
386            let mut p = self.labelend[b];
387            while j != 0 {
388                let v1 = self.endpoint[p ^ 1];
389                self.label[v1] = 0;
390                let idx = if endptrick == 0 {
391                    j
392                } else {
393                    Self::dec_index(len, j)
394                };
395                let tmp = self.blossomendps[b][idx];
396                let v2 = self.endpoint[(tmp ^ endptrick) ^ 1];
397                self.label[v2] = 0;
398                self.assign_label(v1, 2, p);
399                let tmp = self.blossomendps[b][idx];
400                self.allowedge[tmp / 2] = true;
401                j = Self::step_index(len, j, forward);
402                let idx2 = if endptrick == 0 {
403                    j
404                } else {
405                    Self::dec_index(len, j)
406                };
407                let tmp2 = self.blossomendps[b][idx2];
408                p = tmp2 ^ endptrick;
409                self.allowedge[p / 2] = true;
410                j = Self::step_index(len, j, forward);
411            }
412            let bv = self.blossomchilds[b][j];
413            let v1 = self.endpoint[p ^ 1];
414            self.label[v1] = 2;
415            self.label[bv] = 2;
416            self.labelend[v1] = p;
417            self.labelend[bv] = p;
418            self.bestedge[bv] = !0;
419            j = Self::step_index(len, j, forward);
420            loop {
421                let tmpb = self.blossomchilds[b][j];
422                if tmpb == entrychild {
423                    break;
424                }
425                let bv = tmpb;
426                if self.label[bv] == 1 {
427                    j = Self::step_index(len, j, forward);
428                    continue;
429                }
430                let mut reached: Option<usize> = None;
431                let mut leaves = Vec::new();
432                self.blossom_leaves(bv, &mut leaves);
433                for v in leaves {
434                    if self.label[v] != 0 {
435                        reached = Some(v);
436                        break;
437                    }
438                }
439                if let Some(v) = reached {
440                    self.label[v] = 0;
441                    let base = self.blossombase[bv];
442                    let m = self.mate[base];
443                    self.label[self.endpoint[m]] = 0;
444                    self.assign_label(v, 2, self.labelend[v]);
445                }
446                j = Self::step_index(len, j, forward);
447            }
448        }
449        self.label[b] = -1;
450        self.labelend[b] = !0;
451        self.blossomchilds[b].clear();
452        self.blossomendps[b].clear();
453        self.blossombase[b] = !0;
454        self.blossombestedges[b].clear();
455        self.bestedge[b] = !0;
456        self.unusedblossoms.push(b);
457    }
458
459    fn augment_blossom(&mut self, b: usize, v: usize) {
460        let mut t = v;
461        while self.blossomparent[t] != b {
462            t = self.blossomparent[t];
463        }
464        if t >= self.n {
465            self.augment_blossom(t, v);
466        }
467        let len = self.blossomchilds[b].len();
468        let i = self.blossomchilds[b].iter().position(|&x| x == t).unwrap();
469        let mut j = i;
470        let forward = i % 2 == 1;
471        let endptrick = if forward { 0usize } else { 1usize };
472        while j != 0 {
473            j = Self::step_index(len, j, forward);
474            let t = self.blossomchilds[b][j];
475            let pidx = if endptrick == 0 {
476                j
477            } else {
478                Self::dec_index(len, j)
479            };
480            let p = self.blossomendps[b][pidx] ^ endptrick;
481            if t >= self.n {
482                self.augment_blossom(t, self.endpoint[p]);
483            }
484            j = Self::step_index(len, j, forward);
485            let t2 = self.blossomchilds[b][j];
486            if t2 >= self.n {
487                self.augment_blossom(t2, self.endpoint[p ^ 1]);
488            }
489            self.mate[self.endpoint[p]] = p ^ 1;
490            self.mate[self.endpoint[p ^ 1]] = p;
491        }
492        let mut new_child = vec![0usize; len];
493        for (idx, &val) in self.blossomchilds[b].iter().enumerate() {
494            let pos = (idx + len - i) % len;
495            new_child[pos] = val;
496        }
497        self.blossomchilds[b] = new_child;
498        let mut new_endps = vec![0usize; len];
499        for (idx, &val) in self.blossomendps[b].iter().enumerate() {
500            let pos = (idx + len - i) % len;
501            new_endps[pos] = val;
502        }
503        self.blossomendps[b] = new_endps;
504        self.blossombase[b] = self.blossombase[self.blossomchilds[b][0]];
505    }
506
507    fn augment_matching(&mut self, k: usize) {
508        let v = self.endpoint[2 * k];
509        let w = self.endpoint[2 * k + 1];
510        for (s, p) in [(v, 2 * k + 1), (w, 2 * k)] {
511            let mut s = s;
512            let mut p = p;
513            loop {
514                let bs = self.inblossom[s];
515                if bs >= self.n {
516                    self.augment_blossom(bs, s);
517                }
518                self.mate[s] = p;
519                if self.labelend[bs] == !0 {
520                    break;
521                }
522                let t = self.endpoint[self.labelend[bs]];
523                let bt = self.inblossom[t];
524                let s2 = self.endpoint[self.labelend[bt]];
525                let j = self.endpoint[self.labelend[bt] ^ 1];
526                if bt >= self.n {
527                    self.augment_blossom(bt, j);
528                }
529                self.mate[j] = self.labelend[bt];
530                p = self.labelend[bt] ^ 1;
531                s = s2;
532            }
533        }
534    }
535
536    fn solve(&mut self, maxcardinality: bool) {
537        for _ in 0..self.n {
538            self.label.fill(0);
539            self.bestedge.fill(!0);
540            for b in self.n..2 * self.n {
541                self.blossombestedges[b].clear();
542            }
543            self.allowedge.fill(false);
544            self.queue.clear();
545            for v in 0..self.n {
546                if self.mate[v] == !0 && self.label[self.inblossom[v]] == 0 {
547                    self.assign_label(v, 1, !0);
548                }
549            }
550            let mut augmented = false;
551            loop {
552                while let Some(v) = self.queue.pop() {
553                    if self.label[self.inblossom[v]] != 1 {
554                        continue;
555                    }
556                    let neigh = self.neighbend[v].clone();
557                    for p in neigh {
558                        let k = p / 2;
559                        let w = self.endpoint[p];
560                        if self.inblossom[v] == self.inblossom[w] {
561                            continue;
562                        }
563                        let mut kslack = 0i64;
564                        if !self.allowedge[k] {
565                            kslack = self.slack(k);
566                            if kslack <= 0 {
567                                self.allowedge[k] = true;
568                            }
569                        }
570                        if self.allowedge[k] {
571                            if self.label[self.inblossom[w]] == 0 {
572                                self.assign_label(w, 2, p ^ 1);
573                            } else if self.label[self.inblossom[w]] == 1 {
574                                let base = self.scan_blossom(v, w);
575                                if base != !0 {
576                                    self.add_blossom(base, k);
577                                } else {
578                                    self.augment_matching(k);
579                                    augmented = true;
580                                    break;
581                                }
582                            } else if self.label[w] == 0 {
583                                self.label[w] = 2;
584                                self.labelend[w] = p ^ 1;
585                            }
586                        } else if self.label[self.inblossom[w]] == 1 {
587                            let b = self.inblossom[v];
588                            if self.bestedge[b] == !0 || kslack < self.slack(self.bestedge[b]) {
589                                self.bestedge[b] = k;
590                            }
591                        } else if self.label[w] == 0
592                            && (self.bestedge[w] == !0 || kslack < self.slack(self.bestedge[w]))
593                        {
594                            self.bestedge[w] = k;
595                        }
596                    }
597                    if augmented {
598                        break;
599                    }
600                }
601                if augmented {
602                    break;
603                }
604                let mut deltatype = -1;
605                let mut delta = 0i64;
606                let mut deltaedge = !0;
607                let mut deltablossom = !0;
608                if !maxcardinality {
609                    deltatype = 1;
610                    delta = self.dualvar[0..self.n].iter().cloned().min().unwrap_or(0);
611                }
612                for v in 0..self.n {
613                    if self.label[self.inblossom[v]] == 0 && self.bestedge[v] != !0 {
614                        let d = self.slack(self.bestedge[v]);
615                        if deltatype == -1 || d < delta {
616                            delta = d;
617                            deltatype = 2;
618                            deltaedge = self.bestedge[v];
619                        }
620                    }
621                }
622                for b in 0..2 * self.n {
623                    if self.blossomparent[b] == !0 && self.label[b] == 1 && self.bestedge[b] != !0 {
624                        let kslack = self.slack(self.bestedge[b]);
625                        let d = kslack / 2;
626                        if deltatype == -1 || d < delta {
627                            delta = d;
628                            deltatype = 3;
629                            deltaedge = self.bestedge[b];
630                        }
631                    }
632                }
633                for b in self.n..2 * self.n {
634                    if self.blossombase[b] != !0
635                        && self.blossomparent[b] == !0
636                        && self.label[b] == 2
637                        && (deltatype == -1 || self.dualvar[b] < delta)
638                    {
639                        delta = self.dualvar[b];
640                        deltatype = 4;
641                        deltablossom = b;
642                    }
643                }
644                if deltatype == -1 {
645                    if maxcardinality {
646                        deltatype = 1;
647                        delta = 0.max(*self.dualvar[0..self.n].iter().min().unwrap_or(&0));
648                    } else {
649                        break;
650                    }
651                }
652                for v in 0..self.n {
653                    if self.label[self.inblossom[v]] == 1 {
654                        self.dualvar[v] -= delta;
655                    } else if self.label[self.inblossom[v]] == 2 {
656                        self.dualvar[v] += delta;
657                    }
658                }
659                for b in self.n..2 * self.n {
660                    if self.blossombase[b] != !0 && self.blossomparent[b] == !0 {
661                        if self.label[b] == 1 {
662                            self.dualvar[b] += delta;
663                        } else if self.label[b] == 2 {
664                            self.dualvar[b] -= delta;
665                        }
666                    }
667                }
668                if deltatype == 1 {
669                    break;
670                } else if deltatype == 2 {
671                    let k = deltaedge;
672                    self.allowedge[k] = true;
673                    let mut i = self.endpoint[2 * k];
674                    let mut j = self.endpoint[2 * k + 1];
675                    if self.label[self.inblossom[i]] == 0 {
676                        std::mem::swap(&mut i, &mut j);
677                    }
678                    self.queue.push(i);
679                } else if deltatype == 3 {
680                    let k = deltaedge;
681                    self.allowedge[k] = true;
682                    let i = self.endpoint[2 * k];
683                    self.queue.push(i);
684                } else if deltatype == 4 {
685                    self.expand_blossom(deltablossom, false);
686                }
687            }
688            if !augmented {
689                break;
690            }
691            for b in self.n..2 * self.n {
692                if self.blossomparent[b] == !0
693                    && self.blossombase[b] != !0
694                    && self.label[b] == 1
695                    && self.dualvar[b] == 0
696                {
697                    self.expand_blossom(b, true);
698                }
699            }
700        }
701        for v in 0..self.n {
702            if self.mate[v] != !0 {
703                self.mate[v] = self.endpoint[self.mate[v]];
704            }
705        }
706    }

fn blossom_leaves(&self, b: usize, out: &mut Vec<usize>)

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 185)

177    fn blossom_leaves(&self, b: usize, out: &mut Vec<usize>) {
178        if b < self.n {
179            out.push(b);
180        } else {
181            for &t in &self.blossomchilds[b] {
182                if t < self.n {
183                    out.push(t);
184                } else {
185                    self.blossom_leaves(t, out);
186                }
187            }
188        }
189    }
190
191    fn assign_label(&mut self, w: usize, t: i32, p: usize) {
192        let b = self.inblossom[w];
193        self.label[w] = t;
194        self.label[b] = t;
195        self.labelend[w] = p;
196        self.labelend[b] = p;
197        self.bestedge[w] = !0;
198        self.bestedge[b] = !0;
199        if t == 1 {
200            let mut leaves = Vec::new();
201            self.blossom_leaves(b, &mut leaves);
202            for v in leaves {
203                self.queue.push(v);
204            }
205        } else {
206            let base = self.blossombase[b];
207            let m = self.mate[base];
208            if m == !0 {
209                return;
210            }
211            let u = self.endpoint[m];
212            self.assign_label(u, 1, m ^ 1);
213        }
214    }
215
216    fn scan_blossom(&mut self, mut v: usize, mut w: usize) -> usize {
217        let mut path: Vec<usize> = Vec::new();
218        let mut base = !0;
219        while v != !0 || w != !0 {
220            let b = self.inblossom[v];
221            if (self.label[b] & 4) != 0 {
222                base = self.blossombase[b];
223                break;
224            }
225            path.push(b);
226            self.label[b] = 5;
227            if self.labelend[b] == !0 {
228                v = !0;
229            } else {
230                v = self.endpoint[self.labelend[b]];
231                let b2 = self.inblossom[v];
232                v = self.endpoint[self.labelend[b2]];
233            }
234            if w != !0 {
235                std::mem::swap(&mut v, &mut w);
236            }
237        }
238        for b in path {
239            self.label[b] = 1;
240        }
241        base
242    }
243
244    fn add_blossom(&mut self, base: usize, k: usize) {
245        let mut v = self.endpoint[2 * k];
246        let mut w = self.endpoint[2 * k + 1];
247        let bb = self.inblossom[base];
248        let mut bv = self.inblossom[v];
249        let mut bw = self.inblossom[w];
250        let b = self.unusedblossoms.pop().unwrap();
251        self.blossombase[b] = base;
252        self.blossomparent[b] = !0;
253        self.blossomparent[bb] = b;
254        self.blossomchilds[b].clear();
255        self.blossomendps[b].clear();
256        let mut path: Vec<usize> = Vec::new();
257        let mut endps: Vec<usize> = Vec::new();
258        while bv != bb {
259            self.blossomparent[bv] = b;
260            path.push(bv);
261            endps.push(self.labelend[bv]);
262            v = self.endpoint[self.labelend[bv]];
263            bv = self.inblossom[v];
264        }
265        path.push(bb);
266        path.reverse();
267        self.blossomchilds[b] = path.clone();
268        endps.reverse();
269        endps.push(2 * k);
270        self.blossomendps[b] = endps.clone();
271        while bw != bb {
272            self.blossomparent[bw] = b;
273            path.push(bw);
274            self.blossomchilds[b] = path.clone();
275            endps.push(self.labelend[bw] ^ 1);
276            self.blossomendps[b] = endps.clone();
277            w = self.endpoint[self.labelend[bw]];
278            bw = self.inblossom[w];
279        }
280        self.label[b] = 1;
281        self.labelend[b] = self.labelend[bb];
282        self.dualvar[b] = 0;
283        let mut leaves = Vec::new();
284        self.blossom_leaves(b, &mut leaves);
285        for v in leaves {
286            if self.label[self.inblossom[v]] == 2 {
287                self.queue.push(v);
288            }
289            self.inblossom[v] = b;
290        }
291        let mut bestedgeto = vec![!0; 2 * self.n];
292        for &bv in &path {
293            let nblists: Vec<Vec<usize>> = if self.blossombestedges[bv].is_empty() {
294                let mut lists = Vec::new();
295                let mut leaves = Vec::new();
296                self.blossom_leaves(bv, &mut leaves);
297                for v in leaves {
298                    let mut list = Vec::new();
299                    let neigh = self.neighbend[v].clone();
300                    for p in neigh {
301                        list.push(p / 2);
302                    }
303                    lists.push(list);
304                }
305                lists
306            } else {
307                vec![self.blossombestedges[bv].clone()]
308            };
309            for nblist in nblists {
310                for k in nblist {
311                    let mut i = self.endpoint[2 * k];
312                    let mut j = self.endpoint[2 * k + 1];
313                    if self.inblossom[j] == b {
314                        std::mem::swap(&mut i, &mut j);
315                    }
316                    let bj = self.inblossom[j];
317                    if bj != b
318                        && self.label[bj] == 1
319                        && (bestedgeto[bj] == !0 || self.slack(k) < self.slack(bestedgeto[bj]))
320                    {
321                        bestedgeto[bj] = k;
322                    }
323                }
324            }
325            self.blossombestedges[bv].clear();
326            self.bestedge[bv] = !0;
327        }
328        self.blossombestedges[b].clear();
329        for k in bestedgeto {
330            if k != !0 {
331                self.blossombestedges[b].push(k);
332            }
333        }
334        self.bestedge[b] = !0;
335        for &k in &self.blossombestedges[b] {
336            if self.bestedge[b] == !0 || self.slack(k) < self.slack(self.bestedge[b]) {
337                self.bestedge[b] = k;
338            }
339        }
340    }
341
342    fn step_index(len: usize, j: usize, forward: bool) -> usize {
343        if forward {
344            let next = j + 1;
345            if next == len { 0 } else { next }
346        } else if j == 0 {
347            len - 1
348        } else {
349            j - 1
350        }
351    }
352
353    fn dec_index(len: usize, j: usize) -> usize {
354        if j == 0 { len - 1 } else { j - 1 }
355    }
356
357    fn expand_blossom(&mut self, b: usize, endstage: bool) {
358        let childs = self.blossomchilds[b].clone();
359        for s in childs {
360            self.blossomparent[s] = !0;
361            if s < self.n {
362                self.inblossom[s] = s;
363            } else if endstage && self.dualvar[s] == 0 {
364                self.expand_blossom(s, endstage);
365            } else {
366                let mut leaves = Vec::new();
367                self.blossom_leaves(s, &mut leaves);
368                for v in leaves {
369                    self.inblossom[v] = s;
370                }
371            }
372        }
373        if !endstage && self.label[b] == 2 {
374            let entrychild = {
375                let p = self.labelend[b];
376                let u = self.endpoint[p ^ 1];
377                self.inblossom[u]
378            };
379            let len = self.blossomchilds[b].len();
380            let mut j = self.blossomchilds[b]
381                .iter()
382                .position(|&x| x == entrychild)
383                .unwrap();
384            let forward = j % 2 == 1;
385            let endptrick = if forward { 0usize } else { 1usize };
386            let mut p = self.labelend[b];
387            while j != 0 {
388                let v1 = self.endpoint[p ^ 1];
389                self.label[v1] = 0;
390                let idx = if endptrick == 0 {
391                    j
392                } else {
393                    Self::dec_index(len, j)
394                };
395                let tmp = self.blossomendps[b][idx];
396                let v2 = self.endpoint[(tmp ^ endptrick) ^ 1];
397                self.label[v2] = 0;
398                self.assign_label(v1, 2, p);
399                let tmp = self.blossomendps[b][idx];
400                self.allowedge[tmp / 2] = true;
401                j = Self::step_index(len, j, forward);
402                let idx2 = if endptrick == 0 {
403                    j
404                } else {
405                    Self::dec_index(len, j)
406                };
407                let tmp2 = self.blossomendps[b][idx2];
408                p = tmp2 ^ endptrick;
409                self.allowedge[p / 2] = true;
410                j = Self::step_index(len, j, forward);
411            }
412            let bv = self.blossomchilds[b][j];
413            let v1 = self.endpoint[p ^ 1];
414            self.label[v1] = 2;
415            self.label[bv] = 2;
416            self.labelend[v1] = p;
417            self.labelend[bv] = p;
418            self.bestedge[bv] = !0;
419            j = Self::step_index(len, j, forward);
420            loop {
421                let tmpb = self.blossomchilds[b][j];
422                if tmpb == entrychild {
423                    break;
424                }
425                let bv = tmpb;
426                if self.label[bv] == 1 {
427                    j = Self::step_index(len, j, forward);
428                    continue;
429                }
430                let mut reached: Option<usize> = None;
431                let mut leaves = Vec::new();
432                self.blossom_leaves(bv, &mut leaves);
433                for v in leaves {
434                    if self.label[v] != 0 {
435                        reached = Some(v);
436                        break;
437                    }
438                }
439                if let Some(v) = reached {
440                    self.label[v] = 0;
441                    let base = self.blossombase[bv];
442                    let m = self.mate[base];
443                    self.label[self.endpoint[m]] = 0;
444                    self.assign_label(v, 2, self.labelend[v]);
445                }
446                j = Self::step_index(len, j, forward);
447            }
448        }
449        self.label[b] = -1;
450        self.labelend[b] = !0;
451        self.blossomchilds[b].clear();
452        self.blossomendps[b].clear();
453        self.blossombase[b] = !0;
454        self.blossombestedges[b].clear();
455        self.bestedge[b] = !0;
456        self.unusedblossoms.push(b);
457    }

fn assign_label(&mut self, w: usize, t: i32, p: usize)

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 212)

191    fn assign_label(&mut self, w: usize, t: i32, p: usize) {
192        let b = self.inblossom[w];
193        self.label[w] = t;
194        self.label[b] = t;
195        self.labelend[w] = p;
196        self.labelend[b] = p;
197        self.bestedge[w] = !0;
198        self.bestedge[b] = !0;
199        if t == 1 {
200            let mut leaves = Vec::new();
201            self.blossom_leaves(b, &mut leaves);
202            for v in leaves {
203                self.queue.push(v);
204            }
205        } else {
206            let base = self.blossombase[b];
207            let m = self.mate[base];
208            if m == !0 {
209                return;
210            }
211            let u = self.endpoint[m];
212            self.assign_label(u, 1, m ^ 1);
213        }
214    }
215
216    fn scan_blossom(&mut self, mut v: usize, mut w: usize) -> usize {
217        let mut path: Vec<usize> = Vec::new();
218        let mut base = !0;
219        while v != !0 || w != !0 {
220            let b = self.inblossom[v];
221            if (self.label[b] & 4) != 0 {
222                base = self.blossombase[b];
223                break;
224            }
225            path.push(b);
226            self.label[b] = 5;
227            if self.labelend[b] == !0 {
228                v = !0;
229            } else {
230                v = self.endpoint[self.labelend[b]];
231                let b2 = self.inblossom[v];
232                v = self.endpoint[self.labelend[b2]];
233            }
234            if w != !0 {
235                std::mem::swap(&mut v, &mut w);
236            }
237        }
238        for b in path {
239            self.label[b] = 1;
240        }
241        base
242    }
243
244    fn add_blossom(&mut self, base: usize, k: usize) {
245        let mut v = self.endpoint[2 * k];
246        let mut w = self.endpoint[2 * k + 1];
247        let bb = self.inblossom[base];
248        let mut bv = self.inblossom[v];
249        let mut bw = self.inblossom[w];
250        let b = self.unusedblossoms.pop().unwrap();
251        self.blossombase[b] = base;
252        self.blossomparent[b] = !0;
253        self.blossomparent[bb] = b;
254        self.blossomchilds[b].clear();
255        self.blossomendps[b].clear();
256        let mut path: Vec<usize> = Vec::new();
257        let mut endps: Vec<usize> = Vec::new();
258        while bv != bb {
259            self.blossomparent[bv] = b;
260            path.push(bv);
261            endps.push(self.labelend[bv]);
262            v = self.endpoint[self.labelend[bv]];
263            bv = self.inblossom[v];
264        }
265        path.push(bb);
266        path.reverse();
267        self.blossomchilds[b] = path.clone();
268        endps.reverse();
269        endps.push(2 * k);
270        self.blossomendps[b] = endps.clone();
271        while bw != bb {
272            self.blossomparent[bw] = b;
273            path.push(bw);
274            self.blossomchilds[b] = path.clone();
275            endps.push(self.labelend[bw] ^ 1);
276            self.blossomendps[b] = endps.clone();
277            w = self.endpoint[self.labelend[bw]];
278            bw = self.inblossom[w];
279        }
280        self.label[b] = 1;
281        self.labelend[b] = self.labelend[bb];
282        self.dualvar[b] = 0;
283        let mut leaves = Vec::new();
284        self.blossom_leaves(b, &mut leaves);
285        for v in leaves {
286            if self.label[self.inblossom[v]] == 2 {
287                self.queue.push(v);
288            }
289            self.inblossom[v] = b;
290        }
291        let mut bestedgeto = vec![!0; 2 * self.n];
292        for &bv in &path {
293            let nblists: Vec<Vec<usize>> = if self.blossombestedges[bv].is_empty() {
294                let mut lists = Vec::new();
295                let mut leaves = Vec::new();
296                self.blossom_leaves(bv, &mut leaves);
297                for v in leaves {
298                    let mut list = Vec::new();
299                    let neigh = self.neighbend[v].clone();
300                    for p in neigh {
301                        list.push(p / 2);
302                    }
303                    lists.push(list);
304                }
305                lists
306            } else {
307                vec![self.blossombestedges[bv].clone()]
308            };
309            for nblist in nblists {
310                for k in nblist {
311                    let mut i = self.endpoint[2 * k];
312                    let mut j = self.endpoint[2 * k + 1];
313                    if self.inblossom[j] == b {
314                        std::mem::swap(&mut i, &mut j);
315                    }
316                    let bj = self.inblossom[j];
317                    if bj != b
318                        && self.label[bj] == 1
319                        && (bestedgeto[bj] == !0 || self.slack(k) < self.slack(bestedgeto[bj]))
320                    {
321                        bestedgeto[bj] = k;
322                    }
323                }
324            }
325            self.blossombestedges[bv].clear();
326            self.bestedge[bv] = !0;
327        }
328        self.blossombestedges[b].clear();
329        for k in bestedgeto {
330            if k != !0 {
331                self.blossombestedges[b].push(k);
332            }
333        }
334        self.bestedge[b] = !0;
335        for &k in &self.blossombestedges[b] {
336            if self.bestedge[b] == !0 || self.slack(k) < self.slack(self.bestedge[b]) {
337                self.bestedge[b] = k;
338            }
339        }
340    }
341
342    fn step_index(len: usize, j: usize, forward: bool) -> usize {
343        if forward {
344            let next = j + 1;
345            if next == len { 0 } else { next }
346        } else if j == 0 {
347            len - 1
348        } else {
349            j - 1
350        }
351    }
352
353    fn dec_index(len: usize, j: usize) -> usize {
354        if j == 0 { len - 1 } else { j - 1 }
355    }
356
357    fn expand_blossom(&mut self, b: usize, endstage: bool) {
358        let childs = self.blossomchilds[b].clone();
359        for s in childs {
360            self.blossomparent[s] = !0;
361            if s < self.n {
362                self.inblossom[s] = s;
363            } else if endstage && self.dualvar[s] == 0 {
364                self.expand_blossom(s, endstage);
365            } else {
366                let mut leaves = Vec::new();
367                self.blossom_leaves(s, &mut leaves);
368                for v in leaves {
369                    self.inblossom[v] = s;
370                }
371            }
372        }
373        if !endstage && self.label[b] == 2 {
374            let entrychild = {
375                let p = self.labelend[b];
376                let u = self.endpoint[p ^ 1];
377                self.inblossom[u]
378            };
379            let len = self.blossomchilds[b].len();
380            let mut j = self.blossomchilds[b]
381                .iter()
382                .position(|&x| x == entrychild)
383                .unwrap();
384            let forward = j % 2 == 1;
385            let endptrick = if forward { 0usize } else { 1usize };
386            let mut p = self.labelend[b];
387            while j != 0 {
388                let v1 = self.endpoint[p ^ 1];
389                self.label[v1] = 0;
390                let idx = if endptrick == 0 {
391                    j
392                } else {
393                    Self::dec_index(len, j)
394                };
395                let tmp = self.blossomendps[b][idx];
396                let v2 = self.endpoint[(tmp ^ endptrick) ^ 1];
397                self.label[v2] = 0;
398                self.assign_label(v1, 2, p);
399                let tmp = self.blossomendps[b][idx];
400                self.allowedge[tmp / 2] = true;
401                j = Self::step_index(len, j, forward);
402                let idx2 = if endptrick == 0 {
403                    j
404                } else {
405                    Self::dec_index(len, j)
406                };
407                let tmp2 = self.blossomendps[b][idx2];
408                p = tmp2 ^ endptrick;
409                self.allowedge[p / 2] = true;
410                j = Self::step_index(len, j, forward);
411            }
412            let bv = self.blossomchilds[b][j];
413            let v1 = self.endpoint[p ^ 1];
414            self.label[v1] = 2;
415            self.label[bv] = 2;
416            self.labelend[v1] = p;
417            self.labelend[bv] = p;
418            self.bestedge[bv] = !0;
419            j = Self::step_index(len, j, forward);
420            loop {
421                let tmpb = self.blossomchilds[b][j];
422                if tmpb == entrychild {
423                    break;
424                }
425                let bv = tmpb;
426                if self.label[bv] == 1 {
427                    j = Self::step_index(len, j, forward);
428                    continue;
429                }
430                let mut reached: Option<usize> = None;
431                let mut leaves = Vec::new();
432                self.blossom_leaves(bv, &mut leaves);
433                for v in leaves {
434                    if self.label[v] != 0 {
435                        reached = Some(v);
436                        break;
437                    }
438                }
439                if let Some(v) = reached {
440                    self.label[v] = 0;
441                    let base = self.blossombase[bv];
442                    let m = self.mate[base];
443                    self.label[self.endpoint[m]] = 0;
444                    self.assign_label(v, 2, self.labelend[v]);
445                }
446                j = Self::step_index(len, j, forward);
447            }
448        }
449        self.label[b] = -1;
450        self.labelend[b] = !0;
451        self.blossomchilds[b].clear();
452        self.blossomendps[b].clear();
453        self.blossombase[b] = !0;
454        self.blossombestedges[b].clear();
455        self.bestedge[b] = !0;
456        self.unusedblossoms.push(b);
457    }
458
459    fn augment_blossom(&mut self, b: usize, v: usize) {
460        let mut t = v;
461        while self.blossomparent[t] != b {
462            t = self.blossomparent[t];
463        }
464        if t >= self.n {
465            self.augment_blossom(t, v);
466        }
467        let len = self.blossomchilds[b].len();
468        let i = self.blossomchilds[b].iter().position(|&x| x == t).unwrap();
469        let mut j = i;
470        let forward = i % 2 == 1;
471        let endptrick = if forward { 0usize } else { 1usize };
472        while j != 0 {
473            j = Self::step_index(len, j, forward);
474            let t = self.blossomchilds[b][j];
475            let pidx = if endptrick == 0 {
476                j
477            } else {
478                Self::dec_index(len, j)
479            };
480            let p = self.blossomendps[b][pidx] ^ endptrick;
481            if t >= self.n {
482                self.augment_blossom(t, self.endpoint[p]);
483            }
484            j = Self::step_index(len, j, forward);
485            let t2 = self.blossomchilds[b][j];
486            if t2 >= self.n {
487                self.augment_blossom(t2, self.endpoint[p ^ 1]);
488            }
489            self.mate[self.endpoint[p]] = p ^ 1;
490            self.mate[self.endpoint[p ^ 1]] = p;
491        }
492        let mut new_child = vec![0usize; len];
493        for (idx, &val) in self.blossomchilds[b].iter().enumerate() {
494            let pos = (idx + len - i) % len;
495            new_child[pos] = val;
496        }
497        self.blossomchilds[b] = new_child;
498        let mut new_endps = vec![0usize; len];
499        for (idx, &val) in self.blossomendps[b].iter().enumerate() {
500            let pos = (idx + len - i) % len;
501            new_endps[pos] = val;
502        }
503        self.blossomendps[b] = new_endps;
504        self.blossombase[b] = self.blossombase[self.blossomchilds[b][0]];
505    }
506
507    fn augment_matching(&mut self, k: usize) {
508        let v = self.endpoint[2 * k];
509        let w = self.endpoint[2 * k + 1];
510        for (s, p) in [(v, 2 * k + 1), (w, 2 * k)] {
511            let mut s = s;
512            let mut p = p;
513            loop {
514                let bs = self.inblossom[s];
515                if bs >= self.n {
516                    self.augment_blossom(bs, s);
517                }
518                self.mate[s] = p;
519                if self.labelend[bs] == !0 {
520                    break;
521                }
522                let t = self.endpoint[self.labelend[bs]];
523                let bt = self.inblossom[t];
524                let s2 = self.endpoint[self.labelend[bt]];
525                let j = self.endpoint[self.labelend[bt] ^ 1];
526                if bt >= self.n {
527                    self.augment_blossom(bt, j);
528                }
529                self.mate[j] = self.labelend[bt];
530                p = self.labelend[bt] ^ 1;
531                s = s2;
532            }
533        }
534    }
535
536    fn solve(&mut self, maxcardinality: bool) {
537        for _ in 0..self.n {
538            self.label.fill(0);
539            self.bestedge.fill(!0);
540            for b in self.n..2 * self.n {
541                self.blossombestedges[b].clear();
542            }
543            self.allowedge.fill(false);
544            self.queue.clear();
545            for v in 0..self.n {
546                if self.mate[v] == !0 && self.label[self.inblossom[v]] == 0 {
547                    self.assign_label(v, 1, !0);
548                }
549            }
550            let mut augmented = false;
551            loop {
552                while let Some(v) = self.queue.pop() {
553                    if self.label[self.inblossom[v]] != 1 {
554                        continue;
555                    }
556                    let neigh = self.neighbend[v].clone();
557                    for p in neigh {
558                        let k = p / 2;
559                        let w = self.endpoint[p];
560                        if self.inblossom[v] == self.inblossom[w] {
561                            continue;
562                        }
563                        let mut kslack = 0i64;
564                        if !self.allowedge[k] {
565                            kslack = self.slack(k);
566                            if kslack <= 0 {
567                                self.allowedge[k] = true;
568                            }
569                        }
570                        if self.allowedge[k] {
571                            if self.label[self.inblossom[w]] == 0 {
572                                self.assign_label(w, 2, p ^ 1);
573                            } else if self.label[self.inblossom[w]] == 1 {
574                                let base = self.scan_blossom(v, w);
575                                if base != !0 {
576                                    self.add_blossom(base, k);
577                                } else {
578                                    self.augment_matching(k);
579                                    augmented = true;
580                                    break;
581                                }
582                            } else if self.label[w] == 0 {
583                                self.label[w] = 2;
584                                self.labelend[w] = p ^ 1;
585                            }
586                        } else if self.label[self.inblossom[w]] == 1 {
587                            let b = self.inblossom[v];
588                            if self.bestedge[b] == !0 || kslack < self.slack(self.bestedge[b]) {
589                                self.bestedge[b] = k;
590                            }
591                        } else if self.label[w] == 0
592                            && (self.bestedge[w] == !0 || kslack < self.slack(self.bestedge[w]))
593                        {
594                            self.bestedge[w] = k;
595                        }
596                    }
597                    if augmented {
598                        break;
599                    }
600                }
601                if augmented {
602                    break;
603                }
604                let mut deltatype = -1;
605                let mut delta = 0i64;
606                let mut deltaedge = !0;
607                let mut deltablossom = !0;
608                if !maxcardinality {
609                    deltatype = 1;
610                    delta = self.dualvar[0..self.n].iter().cloned().min().unwrap_or(0);
611                }
612                for v in 0..self.n {
613                    if self.label[self.inblossom[v]] == 0 && self.bestedge[v] != !0 {
614                        let d = self.slack(self.bestedge[v]);
615                        if deltatype == -1 || d < delta {
616                            delta = d;
617                            deltatype = 2;
618                            deltaedge = self.bestedge[v];
619                        }
620                    }
621                }
622                for b in 0..2 * self.n {
623                    if self.blossomparent[b] == !0 && self.label[b] == 1 && self.bestedge[b] != !0 {
624                        let kslack = self.slack(self.bestedge[b]);
625                        let d = kslack / 2;
626                        if deltatype == -1 || d < delta {
627                            delta = d;
628                            deltatype = 3;
629                            deltaedge = self.bestedge[b];
630                        }
631                    }
632                }
633                for b in self.n..2 * self.n {
634                    if self.blossombase[b] != !0
635                        && self.blossomparent[b] == !0
636                        && self.label[b] == 2
637                        && (deltatype == -1 || self.dualvar[b] < delta)
638                    {
639                        delta = self.dualvar[b];
640                        deltatype = 4;
641                        deltablossom = b;
642                    }
643                }
644                if deltatype == -1 {
645                    if maxcardinality {
646                        deltatype = 1;
647                        delta = 0.max(*self.dualvar[0..self.n].iter().min().unwrap_or(&0));
648                    } else {
649                        break;
650                    }
651                }
652                for v in 0..self.n {
653                    if self.label[self.inblossom[v]] == 1 {
654                        self.dualvar[v] -= delta;
655                    } else if self.label[self.inblossom[v]] == 2 {
656                        self.dualvar[v] += delta;
657                    }
658                }
659                for b in self.n..2 * self.n {
660                    if self.blossombase[b] != !0 && self.blossomparent[b] == !0 {
661                        if self.label[b] == 1 {
662                            self.dualvar[b] += delta;
663                        } else if self.label[b] == 2 {
664                            self.dualvar[b] -= delta;
665                        }
666                    }
667                }
668                if deltatype == 1 {
669                    break;
670                } else if deltatype == 2 {
671                    let k = deltaedge;
672                    self.allowedge[k] = true;
673                    let mut i = self.endpoint[2 * k];
674                    let mut j = self.endpoint[2 * k + 1];
675                    if self.label[self.inblossom[i]] == 0 {
676                        std::mem::swap(&mut i, &mut j);
677                    }
678                    self.queue.push(i);
679                } else if deltatype == 3 {
680                    let k = deltaedge;
681                    self.allowedge[k] = true;
682                    let i = self.endpoint[2 * k];
683                    self.queue.push(i);
684                } else if deltatype == 4 {
685                    self.expand_blossom(deltablossom, false);
686                }
687            }
688            if !augmented {
689                break;
690            }
691            for b in self.n..2 * self.n {
692                if self.blossomparent[b] == !0
693                    && self.blossombase[b] != !0
694                    && self.label[b] == 1
695                    && self.dualvar[b] == 0
696                {
697                    self.expand_blossom(b, true);
698                }
699            }
700        }
701        for v in 0..self.n {
702            if self.mate[v] != !0 {
703                self.mate[v] = self.endpoint[self.mate[v]];
704            }
705        }
706    }

fn scan_blossom(&mut self, v: usize, w: usize) -> usize

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 574)

536    fn solve(&mut self, maxcardinality: bool) {
537        for _ in 0..self.n {
538            self.label.fill(0);
539            self.bestedge.fill(!0);
540            for b in self.n..2 * self.n {
541                self.blossombestedges[b].clear();
542            }
543            self.allowedge.fill(false);
544            self.queue.clear();
545            for v in 0..self.n {
546                if self.mate[v] == !0 && self.label[self.inblossom[v]] == 0 {
547                    self.assign_label(v, 1, !0);
548                }
549            }
550            let mut augmented = false;
551            loop {
552                while let Some(v) = self.queue.pop() {
553                    if self.label[self.inblossom[v]] != 1 {
554                        continue;
555                    }
556                    let neigh = self.neighbend[v].clone();
557                    for p in neigh {
558                        let k = p / 2;
559                        let w = self.endpoint[p];
560                        if self.inblossom[v] == self.inblossom[w] {
561                            continue;
562                        }
563                        let mut kslack = 0i64;
564                        if !self.allowedge[k] {
565                            kslack = self.slack(k);
566                            if kslack <= 0 {
567                                self.allowedge[k] = true;
568                            }
569                        }
570                        if self.allowedge[k] {
571                            if self.label[self.inblossom[w]] == 0 {
572                                self.assign_label(w, 2, p ^ 1);
573                            } else if self.label[self.inblossom[w]] == 1 {
574                                let base = self.scan_blossom(v, w);
575                                if base != !0 {
576                                    self.add_blossom(base, k);
577                                } else {
578                                    self.augment_matching(k);
579                                    augmented = true;
580                                    break;
581                                }
582                            } else if self.label[w] == 0 {
583                                self.label[w] = 2;
584                                self.labelend[w] = p ^ 1;
585                            }
586                        } else if self.label[self.inblossom[w]] == 1 {
587                            let b = self.inblossom[v];
588                            if self.bestedge[b] == !0 || kslack < self.slack(self.bestedge[b]) {
589                                self.bestedge[b] = k;
590                            }
591                        } else if self.label[w] == 0
592                            && (self.bestedge[w] == !0 || kslack < self.slack(self.bestedge[w]))
593                        {
594                            self.bestedge[w] = k;
595                        }
596                    }
597                    if augmented {
598                        break;
599                    }
600                }
601                if augmented {
602                    break;
603                }
604                let mut deltatype = -1;
605                let mut delta = 0i64;
606                let mut deltaedge = !0;
607                let mut deltablossom = !0;
608                if !maxcardinality {
609                    deltatype = 1;
610                    delta = self.dualvar[0..self.n].iter().cloned().min().unwrap_or(0);
611                }
612                for v in 0..self.n {
613                    if self.label[self.inblossom[v]] == 0 && self.bestedge[v] != !0 {
614                        let d = self.slack(self.bestedge[v]);
615                        if deltatype == -1 || d < delta {
616                            delta = d;
617                            deltatype = 2;
618                            deltaedge = self.bestedge[v];
619                        }
620                    }
621                }
622                for b in 0..2 * self.n {
623                    if self.blossomparent[b] == !0 && self.label[b] == 1 && self.bestedge[b] != !0 {
624                        let kslack = self.slack(self.bestedge[b]);
625                        let d = kslack / 2;
626                        if deltatype == -1 || d < delta {
627                            delta = d;
628                            deltatype = 3;
629                            deltaedge = self.bestedge[b];
630                        }
631                    }
632                }
633                for b in self.n..2 * self.n {
634                    if self.blossombase[b] != !0
635                        && self.blossomparent[b] == !0
636                        && self.label[b] == 2
637                        && (deltatype == -1 || self.dualvar[b] < delta)
638                    {
639                        delta = self.dualvar[b];
640                        deltatype = 4;
641                        deltablossom = b;
642                    }
643                }
644                if deltatype == -1 {
645                    if maxcardinality {
646                        deltatype = 1;
647                        delta = 0.max(*self.dualvar[0..self.n].iter().min().unwrap_or(&0));
648                    } else {
649                        break;
650                    }
651                }
652                for v in 0..self.n {
653                    if self.label[self.inblossom[v]] == 1 {
654                        self.dualvar[v] -= delta;
655                    } else if self.label[self.inblossom[v]] == 2 {
656                        self.dualvar[v] += delta;
657                    }
658                }
659                for b in self.n..2 * self.n {
660                    if self.blossombase[b] != !0 && self.blossomparent[b] == !0 {
661                        if self.label[b] == 1 {
662                            self.dualvar[b] += delta;
663                        } else if self.label[b] == 2 {
664                            self.dualvar[b] -= delta;
665                        }
666                    }
667                }
668                if deltatype == 1 {
669                    break;
670                } else if deltatype == 2 {
671                    let k = deltaedge;
672                    self.allowedge[k] = true;
673                    let mut i = self.endpoint[2 * k];
674                    let mut j = self.endpoint[2 * k + 1];
675                    if self.label[self.inblossom[i]] == 0 {
676                        std::mem::swap(&mut i, &mut j);
677                    }
678                    self.queue.push(i);
679                } else if deltatype == 3 {
680                    let k = deltaedge;
681                    self.allowedge[k] = true;
682                    let i = self.endpoint[2 * k];
683                    self.queue.push(i);
684                } else if deltatype == 4 {
685                    self.expand_blossom(deltablossom, false);
686                }
687            }
688            if !augmented {
689                break;
690            }
691            for b in self.n..2 * self.n {
692                if self.blossomparent[b] == !0
693                    && self.blossombase[b] != !0
694                    && self.label[b] == 1
695                    && self.dualvar[b] == 0
696                {
697                    self.expand_blossom(b, true);
698                }
699            }
700        }
701        for v in 0..self.n {
702            if self.mate[v] != !0 {
703                self.mate[v] = self.endpoint[self.mate[v]];
704            }
705        }
706    }

fn add_blossom(&mut self, base: usize, k: usize)

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 576)

536    fn solve(&mut self, maxcardinality: bool) {
537        for _ in 0..self.n {
538            self.label.fill(0);
539            self.bestedge.fill(!0);
540            for b in self.n..2 * self.n {
541                self.blossombestedges[b].clear();
542            }
543            self.allowedge.fill(false);
544            self.queue.clear();
545            for v in 0..self.n {
546                if self.mate[v] == !0 && self.label[self.inblossom[v]] == 0 {
547                    self.assign_label(v, 1, !0);
548                }
549            }
550            let mut augmented = false;
551            loop {
552                while let Some(v) = self.queue.pop() {
553                    if self.label[self.inblossom[v]] != 1 {
554                        continue;
555                    }
556                    let neigh = self.neighbend[v].clone();
557                    for p in neigh {
558                        let k = p / 2;
559                        let w = self.endpoint[p];
560                        if self.inblossom[v] == self.inblossom[w] {
561                            continue;
562                        }
563                        let mut kslack = 0i64;
564                        if !self.allowedge[k] {
565                            kslack = self.slack(k);
566                            if kslack <= 0 {
567                                self.allowedge[k] = true;
568                            }
569                        }
570                        if self.allowedge[k] {
571                            if self.label[self.inblossom[w]] == 0 {
572                                self.assign_label(w, 2, p ^ 1);
573                            } else if self.label[self.inblossom[w]] == 1 {
574                                let base = self.scan_blossom(v, w);
575                                if base != !0 {
576                                    self.add_blossom(base, k);
577                                } else {
578                                    self.augment_matching(k);
579                                    augmented = true;
580                                    break;
581                                }
582                            } else if self.label[w] == 0 {
583                                self.label[w] = 2;
584                                self.labelend[w] = p ^ 1;
585                            }
586                        } else if self.label[self.inblossom[w]] == 1 {
587                            let b = self.inblossom[v];
588                            if self.bestedge[b] == !0 || kslack < self.slack(self.bestedge[b]) {
589                                self.bestedge[b] = k;
590                            }
591                        } else if self.label[w] == 0
592                            && (self.bestedge[w] == !0 || kslack < self.slack(self.bestedge[w]))
593                        {
594                            self.bestedge[w] = k;
595                        }
596                    }
597                    if augmented {
598                        break;
599                    }
600                }
601                if augmented {
602                    break;
603                }
604                let mut deltatype = -1;
605                let mut delta = 0i64;
606                let mut deltaedge = !0;
607                let mut deltablossom = !0;
608                if !maxcardinality {
609                    deltatype = 1;
610                    delta = self.dualvar[0..self.n].iter().cloned().min().unwrap_or(0);
611                }
612                for v in 0..self.n {
613                    if self.label[self.inblossom[v]] == 0 && self.bestedge[v] != !0 {
614                        let d = self.slack(self.bestedge[v]);
615                        if deltatype == -1 || d < delta {
616                            delta = d;
617                            deltatype = 2;
618                            deltaedge = self.bestedge[v];
619                        }
620                    }
621                }
622                for b in 0..2 * self.n {
623                    if self.blossomparent[b] == !0 && self.label[b] == 1 && self.bestedge[b] != !0 {
624                        let kslack = self.slack(self.bestedge[b]);
625                        let d = kslack / 2;
626                        if deltatype == -1 || d < delta {
627                            delta = d;
628                            deltatype = 3;
629                            deltaedge = self.bestedge[b];
630                        }
631                    }
632                }
633                for b in self.n..2 * self.n {
634                    if self.blossombase[b] != !0
635                        && self.blossomparent[b] == !0
636                        && self.label[b] == 2
637                        && (deltatype == -1 || self.dualvar[b] < delta)
638                    {
639                        delta = self.dualvar[b];
640                        deltatype = 4;
641                        deltablossom = b;
642                    }
643                }
644                if deltatype == -1 {
645                    if maxcardinality {
646                        deltatype = 1;
647                        delta = 0.max(*self.dualvar[0..self.n].iter().min().unwrap_or(&0));
648                    } else {
649                        break;
650                    }
651                }
652                for v in 0..self.n {
653                    if self.label[self.inblossom[v]] == 1 {
654                        self.dualvar[v] -= delta;
655                    } else if self.label[self.inblossom[v]] == 2 {
656                        self.dualvar[v] += delta;
657                    }
658                }
659                for b in self.n..2 * self.n {
660                    if self.blossombase[b] != !0 && self.blossomparent[b] == !0 {
661                        if self.label[b] == 1 {
662                            self.dualvar[b] += delta;
663                        } else if self.label[b] == 2 {
664                            self.dualvar[b] -= delta;
665                        }
666                    }
667                }
668                if deltatype == 1 {
669                    break;
670                } else if deltatype == 2 {
671                    let k = deltaedge;
672                    self.allowedge[k] = true;
673                    let mut i = self.endpoint[2 * k];
674                    let mut j = self.endpoint[2 * k + 1];
675                    if self.label[self.inblossom[i]] == 0 {
676                        std::mem::swap(&mut i, &mut j);
677                    }
678                    self.queue.push(i);
679                } else if deltatype == 3 {
680                    let k = deltaedge;
681                    self.allowedge[k] = true;
682                    let i = self.endpoint[2 * k];
683                    self.queue.push(i);
684                } else if deltatype == 4 {
685                    self.expand_blossom(deltablossom, false);
686                }
687            }
688            if !augmented {
689                break;
690            }
691            for b in self.n..2 * self.n {
692                if self.blossomparent[b] == !0
693                    && self.blossombase[b] != !0
694                    && self.label[b] == 1
695                    && self.dualvar[b] == 0
696                {
697                    self.expand_blossom(b, true);
698                }
699            }
700        }
701        for v in 0..self.n {
702            if self.mate[v] != !0 {
703                self.mate[v] = self.endpoint[self.mate[v]];
704            }
705        }
706    }

fn step_index(len: usize, j: usize, forward: bool) -> usize

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 401)

357    fn expand_blossom(&mut self, b: usize, endstage: bool) {
358        let childs = self.blossomchilds[b].clone();
359        for s in childs {
360            self.blossomparent[s] = !0;
361            if s < self.n {
362                self.inblossom[s] = s;
363            } else if endstage && self.dualvar[s] == 0 {
364                self.expand_blossom(s, endstage);
365            } else {
366                let mut leaves = Vec::new();
367                self.blossom_leaves(s, &mut leaves);
368                for v in leaves {
369                    self.inblossom[v] = s;
370                }
371            }
372        }
373        if !endstage && self.label[b] == 2 {
374            let entrychild = {
375                let p = self.labelend[b];
376                let u = self.endpoint[p ^ 1];
377                self.inblossom[u]
378            };
379            let len = self.blossomchilds[b].len();
380            let mut j = self.blossomchilds[b]
381                .iter()
382                .position(|&x| x == entrychild)
383                .unwrap();
384            let forward = j % 2 == 1;
385            let endptrick = if forward { 0usize } else { 1usize };
386            let mut p = self.labelend[b];
387            while j != 0 {
388                let v1 = self.endpoint[p ^ 1];
389                self.label[v1] = 0;
390                let idx = if endptrick == 0 {
391                    j
392                } else {
393                    Self::dec_index(len, j)
394                };
395                let tmp = self.blossomendps[b][idx];
396                let v2 = self.endpoint[(tmp ^ endptrick) ^ 1];
397                self.label[v2] = 0;
398                self.assign_label(v1, 2, p);
399                let tmp = self.blossomendps[b][idx];
400                self.allowedge[tmp / 2] = true;
401                j = Self::step_index(len, j, forward);
402                let idx2 = if endptrick == 0 {
403                    j
404                } else {
405                    Self::dec_index(len, j)
406                };
407                let tmp2 = self.blossomendps[b][idx2];
408                p = tmp2 ^ endptrick;
409                self.allowedge[p / 2] = true;
410                j = Self::step_index(len, j, forward);
411            }
412            let bv = self.blossomchilds[b][j];
413            let v1 = self.endpoint[p ^ 1];
414            self.label[v1] = 2;
415            self.label[bv] = 2;
416            self.labelend[v1] = p;
417            self.labelend[bv] = p;
418            self.bestedge[bv] = !0;
419            j = Self::step_index(len, j, forward);
420            loop {
421                let tmpb = self.blossomchilds[b][j];
422                if tmpb == entrychild {
423                    break;
424                }
425                let bv = tmpb;
426                if self.label[bv] == 1 {
427                    j = Self::step_index(len, j, forward);
428                    continue;
429                }
430                let mut reached: Option<usize> = None;
431                let mut leaves = Vec::new();
432                self.blossom_leaves(bv, &mut leaves);
433                for v in leaves {
434                    if self.label[v] != 0 {
435                        reached = Some(v);
436                        break;
437                    }
438                }
439                if let Some(v) = reached {
440                    self.label[v] = 0;
441                    let base = self.blossombase[bv];
442                    let m = self.mate[base];
443                    self.label[self.endpoint[m]] = 0;
444                    self.assign_label(v, 2, self.labelend[v]);
445                }
446                j = Self::step_index(len, j, forward);
447            }
448        }
449        self.label[b] = -1;
450        self.labelend[b] = !0;
451        self.blossomchilds[b].clear();
452        self.blossomendps[b].clear();
453        self.blossombase[b] = !0;
454        self.blossombestedges[b].clear();
455        self.bestedge[b] = !0;
456        self.unusedblossoms.push(b);
457    }
458
459    fn augment_blossom(&mut self, b: usize, v: usize) {
460        let mut t = v;
461        while self.blossomparent[t] != b {
462            t = self.blossomparent[t];
463        }
464        if t >= self.n {
465            self.augment_blossom(t, v);
466        }
467        let len = self.blossomchilds[b].len();
468        let i = self.blossomchilds[b].iter().position(|&x| x == t).unwrap();
469        let mut j = i;
470        let forward = i % 2 == 1;
471        let endptrick = if forward { 0usize } else { 1usize };
472        while j != 0 {
473            j = Self::step_index(len, j, forward);
474            let t = self.blossomchilds[b][j];
475            let pidx = if endptrick == 0 {
476                j
477            } else {
478                Self::dec_index(len, j)
479            };
480            let p = self.blossomendps[b][pidx] ^ endptrick;
481            if t >= self.n {
482                self.augment_blossom(t, self.endpoint[p]);
483            }
484            j = Self::step_index(len, j, forward);
485            let t2 = self.blossomchilds[b][j];
486            if t2 >= self.n {
487                self.augment_blossom(t2, self.endpoint[p ^ 1]);
488            }
489            self.mate[self.endpoint[p]] = p ^ 1;
490            self.mate[self.endpoint[p ^ 1]] = p;
491        }
492        let mut new_child = vec![0usize; len];
493        for (idx, &val) in self.blossomchilds[b].iter().enumerate() {
494            let pos = (idx + len - i) % len;
495            new_child[pos] = val;
496        }
497        self.blossomchilds[b] = new_child;
498        let mut new_endps = vec![0usize; len];
499        for (idx, &val) in self.blossomendps[b].iter().enumerate() {
500            let pos = (idx + len - i) % len;
501            new_endps[pos] = val;
502        }
503        self.blossomendps[b] = new_endps;
504        self.blossombase[b] = self.blossombase[self.blossomchilds[b][0]];
505    }

fn dec_index(len: usize, j: usize) -> usize

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 393)

357    fn expand_blossom(&mut self, b: usize, endstage: bool) {
358        let childs = self.blossomchilds[b].clone();
359        for s in childs {
360            self.blossomparent[s] = !0;
361            if s < self.n {
362                self.inblossom[s] = s;
363            } else if endstage && self.dualvar[s] == 0 {
364                self.expand_blossom(s, endstage);
365            } else {
366                let mut leaves = Vec::new();
367                self.blossom_leaves(s, &mut leaves);
368                for v in leaves {
369                    self.inblossom[v] = s;
370                }
371            }
372        }
373        if !endstage && self.label[b] == 2 {
374            let entrychild = {
375                let p = self.labelend[b];
376                let u = self.endpoint[p ^ 1];
377                self.inblossom[u]
378            };
379            let len = self.blossomchilds[b].len();
380            let mut j = self.blossomchilds[b]
381                .iter()
382                .position(|&x| x == entrychild)
383                .unwrap();
384            let forward = j % 2 == 1;
385            let endptrick = if forward { 0usize } else { 1usize };
386            let mut p = self.labelend[b];
387            while j != 0 {
388                let v1 = self.endpoint[p ^ 1];
389                self.label[v1] = 0;
390                let idx = if endptrick == 0 {
391                    j
392                } else {
393                    Self::dec_index(len, j)
394                };
395                let tmp = self.blossomendps[b][idx];
396                let v2 = self.endpoint[(tmp ^ endptrick) ^ 1];
397                self.label[v2] = 0;
398                self.assign_label(v1, 2, p);
399                let tmp = self.blossomendps[b][idx];
400                self.allowedge[tmp / 2] = true;
401                j = Self::step_index(len, j, forward);
402                let idx2 = if endptrick == 0 {
403                    j
404                } else {
405                    Self::dec_index(len, j)
406                };
407                let tmp2 = self.blossomendps[b][idx2];
408                p = tmp2 ^ endptrick;
409                self.allowedge[p / 2] = true;
410                j = Self::step_index(len, j, forward);
411            }
412            let bv = self.blossomchilds[b][j];
413            let v1 = self.endpoint[p ^ 1];
414            self.label[v1] = 2;
415            self.label[bv] = 2;
416            self.labelend[v1] = p;
417            self.labelend[bv] = p;
418            self.bestedge[bv] = !0;
419            j = Self::step_index(len, j, forward);
420            loop {
421                let tmpb = self.blossomchilds[b][j];
422                if tmpb == entrychild {
423                    break;
424                }
425                let bv = tmpb;
426                if self.label[bv] == 1 {
427                    j = Self::step_index(len, j, forward);
428                    continue;
429                }
430                let mut reached: Option<usize> = None;
431                let mut leaves = Vec::new();
432                self.blossom_leaves(bv, &mut leaves);
433                for v in leaves {
434                    if self.label[v] != 0 {
435                        reached = Some(v);
436                        break;
437                    }
438                }
439                if let Some(v) = reached {
440                    self.label[v] = 0;
441                    let base = self.blossombase[bv];
442                    let m = self.mate[base];
443                    self.label[self.endpoint[m]] = 0;
444                    self.assign_label(v, 2, self.labelend[v]);
445                }
446                j = Self::step_index(len, j, forward);
447            }
448        }
449        self.label[b] = -1;
450        self.labelend[b] = !0;
451        self.blossomchilds[b].clear();
452        self.blossomendps[b].clear();
453        self.blossombase[b] = !0;
454        self.blossombestedges[b].clear();
455        self.bestedge[b] = !0;
456        self.unusedblossoms.push(b);
457    }
458
459    fn augment_blossom(&mut self, b: usize, v: usize) {
460        let mut t = v;
461        while self.blossomparent[t] != b {
462            t = self.blossomparent[t];
463        }
464        if t >= self.n {
465            self.augment_blossom(t, v);
466        }
467        let len = self.blossomchilds[b].len();
468        let i = self.blossomchilds[b].iter().position(|&x| x == t).unwrap();
469        let mut j = i;
470        let forward = i % 2 == 1;
471        let endptrick = if forward { 0usize } else { 1usize };
472        while j != 0 {
473            j = Self::step_index(len, j, forward);
474            let t = self.blossomchilds[b][j];
475            let pidx = if endptrick == 0 {
476                j
477            } else {
478                Self::dec_index(len, j)
479            };
480            let p = self.blossomendps[b][pidx] ^ endptrick;
481            if t >= self.n {
482                self.augment_blossom(t, self.endpoint[p]);
483            }
484            j = Self::step_index(len, j, forward);
485            let t2 = self.blossomchilds[b][j];
486            if t2 >= self.n {
487                self.augment_blossom(t2, self.endpoint[p ^ 1]);
488            }
489            self.mate[self.endpoint[p]] = p ^ 1;
490            self.mate[self.endpoint[p ^ 1]] = p;
491        }
492        let mut new_child = vec![0usize; len];
493        for (idx, &val) in self.blossomchilds[b].iter().enumerate() {
494            let pos = (idx + len - i) % len;
495            new_child[pos] = val;
496        }
497        self.blossomchilds[b] = new_child;
498        let mut new_endps = vec![0usize; len];
499        for (idx, &val) in self.blossomendps[b].iter().enumerate() {
500            let pos = (idx + len - i) % len;
501            new_endps[pos] = val;
502        }
503        self.blossomendps[b] = new_endps;
504        self.blossombase[b] = self.blossombase[self.blossomchilds[b][0]];
505    }

fn expand_blossom(&mut self, b: usize, endstage: bool)

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 364)

357    fn expand_blossom(&mut self, b: usize, endstage: bool) {
358        let childs = self.blossomchilds[b].clone();
359        for s in childs {
360            self.blossomparent[s] = !0;
361            if s < self.n {
362                self.inblossom[s] = s;
363            } else if endstage && self.dualvar[s] == 0 {
364                self.expand_blossom(s, endstage);
365            } else {
366                let mut leaves = Vec::new();
367                self.blossom_leaves(s, &mut leaves);
368                for v in leaves {
369                    self.inblossom[v] = s;
370                }
371            }
372        }
373        if !endstage && self.label[b] == 2 {
374            let entrychild = {
375                let p = self.labelend[b];
376                let u = self.endpoint[p ^ 1];
377                self.inblossom[u]
378            };
379            let len = self.blossomchilds[b].len();
380            let mut j = self.blossomchilds[b]
381                .iter()
382                .position(|&x| x == entrychild)
383                .unwrap();
384            let forward = j % 2 == 1;
385            let endptrick = if forward { 0usize } else { 1usize };
386            let mut p = self.labelend[b];
387            while j != 0 {
388                let v1 = self.endpoint[p ^ 1];
389                self.label[v1] = 0;
390                let idx = if endptrick == 0 {
391                    j
392                } else {
393                    Self::dec_index(len, j)
394                };
395                let tmp = self.blossomendps[b][idx];
396                let v2 = self.endpoint[(tmp ^ endptrick) ^ 1];
397                self.label[v2] = 0;
398                self.assign_label(v1, 2, p);
399                let tmp = self.blossomendps[b][idx];
400                self.allowedge[tmp / 2] = true;
401                j = Self::step_index(len, j, forward);
402                let idx2 = if endptrick == 0 {
403                    j
404                } else {
405                    Self::dec_index(len, j)
406                };
407                let tmp2 = self.blossomendps[b][idx2];
408                p = tmp2 ^ endptrick;
409                self.allowedge[p / 2] = true;
410                j = Self::step_index(len, j, forward);
411            }
412            let bv = self.blossomchilds[b][j];
413            let v1 = self.endpoint[p ^ 1];
414            self.label[v1] = 2;
415            self.label[bv] = 2;
416            self.labelend[v1] = p;
417            self.labelend[bv] = p;
418            self.bestedge[bv] = !0;
419            j = Self::step_index(len, j, forward);
420            loop {
421                let tmpb = self.blossomchilds[b][j];
422                if tmpb == entrychild {
423                    break;
424                }
425                let bv = tmpb;
426                if self.label[bv] == 1 {
427                    j = Self::step_index(len, j, forward);
428                    continue;
429                }
430                let mut reached: Option<usize> = None;
431                let mut leaves = Vec::new();
432                self.blossom_leaves(bv, &mut leaves);
433                for v in leaves {
434                    if self.label[v] != 0 {
435                        reached = Some(v);
436                        break;
437                    }
438                }
439                if let Some(v) = reached {
440                    self.label[v] = 0;
441                    let base = self.blossombase[bv];
442                    let m = self.mate[base];
443                    self.label[self.endpoint[m]] = 0;
444                    self.assign_label(v, 2, self.labelend[v]);
445                }
446                j = Self::step_index(len, j, forward);
447            }
448        }
449        self.label[b] = -1;
450        self.labelend[b] = !0;
451        self.blossomchilds[b].clear();
452        self.blossomendps[b].clear();
453        self.blossombase[b] = !0;
454        self.blossombestedges[b].clear();
455        self.bestedge[b] = !0;
456        self.unusedblossoms.push(b);
457    }
458
459    fn augment_blossom(&mut self, b: usize, v: usize) {
460        let mut t = v;
461        while self.blossomparent[t] != b {
462            t = self.blossomparent[t];
463        }
464        if t >= self.n {
465            self.augment_blossom(t, v);
466        }
467        let len = self.blossomchilds[b].len();
468        let i = self.blossomchilds[b].iter().position(|&x| x == t).unwrap();
469        let mut j = i;
470        let forward = i % 2 == 1;
471        let endptrick = if forward { 0usize } else { 1usize };
472        while j != 0 {
473            j = Self::step_index(len, j, forward);
474            let t = self.blossomchilds[b][j];
475            let pidx = if endptrick == 0 {
476                j
477            } else {
478                Self::dec_index(len, j)
479            };
480            let p = self.blossomendps[b][pidx] ^ endptrick;
481            if t >= self.n {
482                self.augment_blossom(t, self.endpoint[p]);
483            }
484            j = Self::step_index(len, j, forward);
485            let t2 = self.blossomchilds[b][j];
486            if t2 >= self.n {
487                self.augment_blossom(t2, self.endpoint[p ^ 1]);
488            }
489            self.mate[self.endpoint[p]] = p ^ 1;
490            self.mate[self.endpoint[p ^ 1]] = p;
491        }
492        let mut new_child = vec![0usize; len];
493        for (idx, &val) in self.blossomchilds[b].iter().enumerate() {
494            let pos = (idx + len - i) % len;
495            new_child[pos] = val;
496        }
497        self.blossomchilds[b] = new_child;
498        let mut new_endps = vec![0usize; len];
499        for (idx, &val) in self.blossomendps[b].iter().enumerate() {
500            let pos = (idx + len - i) % len;
501            new_endps[pos] = val;
502        }
503        self.blossomendps[b] = new_endps;
504        self.blossombase[b] = self.blossombase[self.blossomchilds[b][0]];
505    }
506
507    fn augment_matching(&mut self, k: usize) {
508        let v = self.endpoint[2 * k];
509        let w = self.endpoint[2 * k + 1];
510        for (s, p) in [(v, 2 * k + 1), (w, 2 * k)] {
511            let mut s = s;
512            let mut p = p;
513            loop {
514                let bs = self.inblossom[s];
515                if bs >= self.n {
516                    self.augment_blossom(bs, s);
517                }
518                self.mate[s] = p;
519                if self.labelend[bs] == !0 {
520                    break;
521                }
522                let t = self.endpoint[self.labelend[bs]];
523                let bt = self.inblossom[t];
524                let s2 = self.endpoint[self.labelend[bt]];
525                let j = self.endpoint[self.labelend[bt] ^ 1];
526                if bt >= self.n {
527                    self.augment_blossom(bt, j);
528                }
529                self.mate[j] = self.labelend[bt];
530                p = self.labelend[bt] ^ 1;
531                s = s2;
532            }
533        }
534    }
535
536    fn solve(&mut self, maxcardinality: bool) {
537        for _ in 0..self.n {
538            self.label.fill(0);
539            self.bestedge.fill(!0);
540            for b in self.n..2 * self.n {
541                self.blossombestedges[b].clear();
542            }
543            self.allowedge.fill(false);
544            self.queue.clear();
545            for v in 0..self.n {
546                if self.mate[v] == !0 && self.label[self.inblossom[v]] == 0 {
547                    self.assign_label(v, 1, !0);
548                }
549            }
550            let mut augmented = false;
551            loop {
552                while let Some(v) = self.queue.pop() {
553                    if self.label[self.inblossom[v]] != 1 {
554                        continue;
555                    }
556                    let neigh = self.neighbend[v].clone();
557                    for p in neigh {
558                        let k = p / 2;
559                        let w = self.endpoint[p];
560                        if self.inblossom[v] == self.inblossom[w] {
561                            continue;
562                        }
563                        let mut kslack = 0i64;
564                        if !self.allowedge[k] {
565                            kslack = self.slack(k);
566                            if kslack <= 0 {
567                                self.allowedge[k] = true;
568                            }
569                        }
570                        if self.allowedge[k] {
571                            if self.label[self.inblossom[w]] == 0 {
572                                self.assign_label(w, 2, p ^ 1);
573                            } else if self.label[self.inblossom[w]] == 1 {
574                                let base = self.scan_blossom(v, w);
575                                if base != !0 {
576                                    self.add_blossom(base, k);
577                                } else {
578                                    self.augment_matching(k);
579                                    augmented = true;
580                                    break;
581                                }
582                            } else if self.label[w] == 0 {
583                                self.label[w] = 2;
584                                self.labelend[w] = p ^ 1;
585                            }
586                        } else if self.label[self.inblossom[w]] == 1 {
587                            let b = self.inblossom[v];
588                            if self.bestedge[b] == !0 || kslack < self.slack(self.bestedge[b]) {
589                                self.bestedge[b] = k;
590                            }
591                        } else if self.label[w] == 0
592                            && (self.bestedge[w] == !0 || kslack < self.slack(self.bestedge[w]))
593                        {
594                            self.bestedge[w] = k;
595                        }
596                    }
597                    if augmented {
598                        break;
599                    }
600                }
601                if augmented {
602                    break;
603                }
604                let mut deltatype = -1;
605                let mut delta = 0i64;
606                let mut deltaedge = !0;
607                let mut deltablossom = !0;
608                if !maxcardinality {
609                    deltatype = 1;
610                    delta = self.dualvar[0..self.n].iter().cloned().min().unwrap_or(0);
611                }
612                for v in 0..self.n {
613                    if self.label[self.inblossom[v]] == 0 && self.bestedge[v] != !0 {
614                        let d = self.slack(self.bestedge[v]);
615                        if deltatype == -1 || d < delta {
616                            delta = d;
617                            deltatype = 2;
618                            deltaedge = self.bestedge[v];
619                        }
620                    }
621                }
622                for b in 0..2 * self.n {
623                    if self.blossomparent[b] == !0 && self.label[b] == 1 && self.bestedge[b] != !0 {
624                        let kslack = self.slack(self.bestedge[b]);
625                        let d = kslack / 2;
626                        if deltatype == -1 || d < delta {
627                            delta = d;
628                            deltatype = 3;
629                            deltaedge = self.bestedge[b];
630                        }
631                    }
632                }
633                for b in self.n..2 * self.n {
634                    if self.blossombase[b] != !0
635                        && self.blossomparent[b] == !0
636                        && self.label[b] == 2
637                        && (deltatype == -1 || self.dualvar[b] < delta)
638                    {
639                        delta = self.dualvar[b];
640                        deltatype = 4;
641                        deltablossom = b;
642                    }
643                }
644                if deltatype == -1 {
645                    if maxcardinality {
646                        deltatype = 1;
647                        delta = 0.max(*self.dualvar[0..self.n].iter().min().unwrap_or(&0));
648                    } else {
649                        break;
650                    }
651                }
652                for v in 0..self.n {
653                    if self.label[self.inblossom[v]] == 1 {
654                        self.dualvar[v] -= delta;
655                    } else if self.label[self.inblossom[v]] == 2 {
656                        self.dualvar[v] += delta;
657                    }
658                }
659                for b in self.n..2 * self.n {
660                    if self.blossombase[b] != !0 && self.blossomparent[b] == !0 {
661                        if self.label[b] == 1 {
662                            self.dualvar[b] += delta;
663                        } else if self.label[b] == 2 {
664                            self.dualvar[b] -= delta;
665                        }
666                    }
667                }
668                if deltatype == 1 {
669                    break;
670                } else if deltatype == 2 {
671                    let k = deltaedge;
672                    self.allowedge[k] = true;
673                    let mut i = self.endpoint[2 * k];
674                    let mut j = self.endpoint[2 * k + 1];
675                    if self.label[self.inblossom[i]] == 0 {
676                        std::mem::swap(&mut i, &mut j);
677                    }
678                    self.queue.push(i);
679                } else if deltatype == 3 {
680                    let k = deltaedge;
681                    self.allowedge[k] = true;
682                    let i = self.endpoint[2 * k];
683                    self.queue.push(i);
684                } else if deltatype == 4 {
685                    self.expand_blossom(deltablossom, false);
686                }
687            }
688            if !augmented {
689                break;
690            }
691            for b in self.n..2 * self.n {
692                if self.blossomparent[b] == !0
693                    && self.blossombase[b] != !0
694                    && self.label[b] == 1
695                    && self.dualvar[b] == 0
696                {
697                    self.expand_blossom(b, true);
698                }
699            }
700        }
701        for v in 0..self.n {
702            if self.mate[v] != !0 {
703                self.mate[v] = self.endpoint[self.mate[v]];
704            }
705        }
706    }

fn augment_blossom(&mut self, b: usize, v: usize)

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 465)

459    fn augment_blossom(&mut self, b: usize, v: usize) {
460        let mut t = v;
461        while self.blossomparent[t] != b {
462            t = self.blossomparent[t];
463        }
464        if t >= self.n {
465            self.augment_blossom(t, v);
466        }
467        let len = self.blossomchilds[b].len();
468        let i = self.blossomchilds[b].iter().position(|&x| x == t).unwrap();
469        let mut j = i;
470        let forward = i % 2 == 1;
471        let endptrick = if forward { 0usize } else { 1usize };
472        while j != 0 {
473            j = Self::step_index(len, j, forward);
474            let t = self.blossomchilds[b][j];
475            let pidx = if endptrick == 0 {
476                j
477            } else {
478                Self::dec_index(len, j)
479            };
480            let p = self.blossomendps[b][pidx] ^ endptrick;
481            if t >= self.n {
482                self.augment_blossom(t, self.endpoint[p]);
483            }
484            j = Self::step_index(len, j, forward);
485            let t2 = self.blossomchilds[b][j];
486            if t2 >= self.n {
487                self.augment_blossom(t2, self.endpoint[p ^ 1]);
488            }
489            self.mate[self.endpoint[p]] = p ^ 1;
490            self.mate[self.endpoint[p ^ 1]] = p;
491        }
492        let mut new_child = vec![0usize; len];
493        for (idx, &val) in self.blossomchilds[b].iter().enumerate() {
494            let pos = (idx + len - i) % len;
495            new_child[pos] = val;
496        }
497        self.blossomchilds[b] = new_child;
498        let mut new_endps = vec![0usize; len];
499        for (idx, &val) in self.blossomendps[b].iter().enumerate() {
500            let pos = (idx + len - i) % len;
501            new_endps[pos] = val;
502        }
503        self.blossomendps[b] = new_endps;
504        self.blossombase[b] = self.blossombase[self.blossomchilds[b][0]];
505    }
506
507    fn augment_matching(&mut self, k: usize) {
508        let v = self.endpoint[2 * k];
509        let w = self.endpoint[2 * k + 1];
510        for (s, p) in [(v, 2 * k + 1), (w, 2 * k)] {
511            let mut s = s;
512            let mut p = p;
513            loop {
514                let bs = self.inblossom[s];
515                if bs >= self.n {
516                    self.augment_blossom(bs, s);
517                }
518                self.mate[s] = p;
519                if self.labelend[bs] == !0 {
520                    break;
521                }
522                let t = self.endpoint[self.labelend[bs]];
523                let bt = self.inblossom[t];
524                let s2 = self.endpoint[self.labelend[bt]];
525                let j = self.endpoint[self.labelend[bt] ^ 1];
526                if bt >= self.n {
527                    self.augment_blossom(bt, j);
528                }
529                self.mate[j] = self.labelend[bt];
530                p = self.labelend[bt] ^ 1;
531                s = s2;
532            }
533        }
534    }

fn augment_matching(&mut self, k: usize)

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 578)

536    fn solve(&mut self, maxcardinality: bool) {
537        for _ in 0..self.n {
538            self.label.fill(0);
539            self.bestedge.fill(!0);
540            for b in self.n..2 * self.n {
541                self.blossombestedges[b].clear();
542            }
543            self.allowedge.fill(false);
544            self.queue.clear();
545            for v in 0..self.n {
546                if self.mate[v] == !0 && self.label[self.inblossom[v]] == 0 {
547                    self.assign_label(v, 1, !0);
548                }
549            }
550            let mut augmented = false;
551            loop {
552                while let Some(v) = self.queue.pop() {
553                    if self.label[self.inblossom[v]] != 1 {
554                        continue;
555                    }
556                    let neigh = self.neighbend[v].clone();
557                    for p in neigh {
558                        let k = p / 2;
559                        let w = self.endpoint[p];
560                        if self.inblossom[v] == self.inblossom[w] {
561                            continue;
562                        }
563                        let mut kslack = 0i64;
564                        if !self.allowedge[k] {
565                            kslack = self.slack(k);
566                            if kslack <= 0 {
567                                self.allowedge[k] = true;
568                            }
569                        }
570                        if self.allowedge[k] {
571                            if self.label[self.inblossom[w]] == 0 {
572                                self.assign_label(w, 2, p ^ 1);
573                            } else if self.label[self.inblossom[w]] == 1 {
574                                let base = self.scan_blossom(v, w);
575                                if base != !0 {
576                                    self.add_blossom(base, k);
577                                } else {
578                                    self.augment_matching(k);
579                                    augmented = true;
580                                    break;
581                                }
582                            } else if self.label[w] == 0 {
583                                self.label[w] = 2;
584                                self.labelend[w] = p ^ 1;
585                            }
586                        } else if self.label[self.inblossom[w]] == 1 {
587                            let b = self.inblossom[v];
588                            if self.bestedge[b] == !0 || kslack < self.slack(self.bestedge[b]) {
589                                self.bestedge[b] = k;
590                            }
591                        } else if self.label[w] == 0
592                            && (self.bestedge[w] == !0 || kslack < self.slack(self.bestedge[w]))
593                        {
594                            self.bestedge[w] = k;
595                        }
596                    }
597                    if augmented {
598                        break;
599                    }
600                }
601                if augmented {
602                    break;
603                }
604                let mut deltatype = -1;
605                let mut delta = 0i64;
606                let mut deltaedge = !0;
607                let mut deltablossom = !0;
608                if !maxcardinality {
609                    deltatype = 1;
610                    delta = self.dualvar[0..self.n].iter().cloned().min().unwrap_or(0);
611                }
612                for v in 0..self.n {
613                    if self.label[self.inblossom[v]] == 0 && self.bestedge[v] != !0 {
614                        let d = self.slack(self.bestedge[v]);
615                        if deltatype == -1 || d < delta {
616                            delta = d;
617                            deltatype = 2;
618                            deltaedge = self.bestedge[v];
619                        }
620                    }
621                }
622                for b in 0..2 * self.n {
623                    if self.blossomparent[b] == !0 && self.label[b] == 1 && self.bestedge[b] != !0 {
624                        let kslack = self.slack(self.bestedge[b]);
625                        let d = kslack / 2;
626                        if deltatype == -1 || d < delta {
627                            delta = d;
628                            deltatype = 3;
629                            deltaedge = self.bestedge[b];
630                        }
631                    }
632                }
633                for b in self.n..2 * self.n {
634                    if self.blossombase[b] != !0
635                        && self.blossomparent[b] == !0
636                        && self.label[b] == 2
637                        && (deltatype == -1 || self.dualvar[b] < delta)
638                    {
639                        delta = self.dualvar[b];
640                        deltatype = 4;
641                        deltablossom = b;
642                    }
643                }
644                if deltatype == -1 {
645                    if maxcardinality {
646                        deltatype = 1;
647                        delta = 0.max(*self.dualvar[0..self.n].iter().min().unwrap_or(&0));
648                    } else {
649                        break;
650                    }
651                }
652                for v in 0..self.n {
653                    if self.label[self.inblossom[v]] == 1 {
654                        self.dualvar[v] -= delta;
655                    } else if self.label[self.inblossom[v]] == 2 {
656                        self.dualvar[v] += delta;
657                    }
658                }
659                for b in self.n..2 * self.n {
660                    if self.blossombase[b] != !0 && self.blossomparent[b] == !0 {
661                        if self.label[b] == 1 {
662                            self.dualvar[b] += delta;
663                        } else if self.label[b] == 2 {
664                            self.dualvar[b] -= delta;
665                        }
666                    }
667                }
668                if deltatype == 1 {
669                    break;
670                } else if deltatype == 2 {
671                    let k = deltaedge;
672                    self.allowedge[k] = true;
673                    let mut i = self.endpoint[2 * k];
674                    let mut j = self.endpoint[2 * k + 1];
675                    if self.label[self.inblossom[i]] == 0 {
676                        std::mem::swap(&mut i, &mut j);
677                    }
678                    self.queue.push(i);
679                } else if deltatype == 3 {
680                    let k = deltaedge;
681                    self.allowedge[k] = true;
682                    let i = self.endpoint[2 * k];
683                    self.queue.push(i);
684                } else if deltatype == 4 {
685                    self.expand_blossom(deltablossom, false);
686                }
687            }
688            if !augmented {
689                break;
690            }
691            for b in self.n..2 * self.n {
692                if self.blossomparent[b] == !0
693                    && self.blossombase[b] != !0
694                    && self.label[b] == 1
695                    && self.dualvar[b] == 0
696                {
697                    self.expand_blossom(b, true);
698                }
699            }
700        }
701        for v in 0..self.n {
702            if self.mate[v] != !0 {
703                self.mate[v] = self.endpoint[self.mate[v]];
704            }
705        }
706    }

fn solve(&mut self, maxcardinality: bool)

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 83)

50    fn compute(&mut self) {
51        if self.matching_weight != NEG_INF {
52            return;
53        }
54        let n = self.size;
55        if n == 0 {
56            self.matching_weight = 0;
57            return;
58        }
59        let mut edges = Vec::new();
60        let mut weights = Vec::new();
61        let mut neighbend = vec![Vec::new(); n];
62        for i in 0..n {
63            for j in i + 1..n {
64                let w = self.weight[i][j];
65                if w == NEG_INF {
66                    continue;
67                }
68                let k = weights.len();
69                weights.push(w);
70                edges.push(i);
71                edges.push(j);
72                neighbend[i].push(2 * k + 1);
73                neighbend[j].push(2 * k);
74            }
75        }
76        let m = weights.len();
77        if m == 0 {
78            self.mate.fill(!0);
79            self.matching_weight = 0;
80            return;
81        }
82        let mut blossom = BlossomMatching::new(n, edges, weights, neighbend);
83        blossom.solve(false);
84        self.mate.fill(!0);
85        let mut total = 0i64;
86        for v in 0..n {
87            let u = blossom.mate[v];
88            if u != !0 && v < u {
89                self.mate[v] = u;
90                self.mate[u] = v;
91                total += self.weight[v][u];
92            }
93        }
94        self.matching_weight = total;
95    }

Auto Trait Implementations§

impl Freeze for BlossomMatching

impl RefUnwindSafe for BlossomMatching

impl Send for BlossomMatching

impl Sync for BlossomMatching

impl Unpin for BlossomMatching

impl UnsafeUnpin for BlossomMatching

impl UnwindSafe for BlossomMatching

Blanket Implementations§

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

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more

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

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more

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

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

Mutably borrows from an owned value. Read more

impl<T> From<T> for T

fn from(t: T) -> T

Returns the argument unchanged.

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

fn into(self) -> U

Calls U::from(self).

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

impl<T> ToArrayVecScalar for T

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

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

type Error = Infallible

The type returned in the event of a conversion error.

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

Performs the conversion.

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

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

The type returned in the event of a conversion error.

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

Performs the conversion.