dkh.graph.bipatitematching source code

1 /**
2 Unstable
3 */
4 
5 module dkh.graph.bipatitematching;
6 
7 struct BipatiteMatching {
8     import std.conv : to;
9     int L, R, count;
10     int[][] g;
11     int[] lmt, rmt;
12     int[] visited; int vc;
13     this(size_t L, size_t R) {
14         this.L = L.to!int; this.R = R.to!int;
15         g = new int[][L];
16         visited = new int[L];
17         lmt = new int[L]; lmt[] = -1;
18         rmt = new int[R]; rmt[] = -1;
19     }
20     bool dfs(int l) {
21         if (l == -1) return true;
22         if (visited[l] == vc) return false;
23         visited[l] = vc;
24         foreach (r; g[l]) {
25             if (dfs(rmt[r])) {
26                 lmt[l] = r;
27                 rmt[r] = l;
28                 return true;
29             }
30         }
31         return false;
32     }
33     void maximize() {
34         vc++;
35         foreach (i; 0..L) {
36             if (lmt[i] != -1) continue;
37             if (g[i].length == 0) continue;
38             if (dfs(i)) count++;
39         }
40     }
41     /// add edge(l, r)
42     void addEdge(size_t l, size_t r) {
43         g[l] ~= r.to!int;
44         maximize();
45     }
46     /// del edge(l, r)
47     void delEdge(size_t l, size_t r) {
48         import std.algorithm : remove;
49         g[l] = g[l].remove!(a => a == r.to!int);
50         if (rmt[r] == l.to!int) {
51             count--;
52             lmt[l] = rmt[r] = -1;
53             maximize();
54         }
55     }
56     /// cng left_l's edge
57     void cngLeftVertexEdge(size_t l, in int[] v) {
58         g[l] = v.dup;
59         vc++;
60         if (lmt[l] == -1) {
61             if (dfs(l.to!int)) count++;
62         } else {
63             count--;
64             int r = lmt[l];
65             lmt[l] = rmt[r] = -1;
66             maximize();
67         }
68     }
69 }
70 
71 ///
72 unittest {
73     auto bm = BipatiteMatching(3, 3);
74     bm.addEdge(0, 0);
75     bm.addEdge(0, 1);
76     bm.addEdge(1, 1);
77     bm.addEdge(2, 1);
78     assert(bm.count == 2); // example: (0, 0), (1, 1)
79     bm.addEdge(1, 2);
80     assert(bm.count == 3); // (0, 0), (1, 2), (2, 1)
81     bm.delEdge(2, 1);
82     assert(bm.count == 2); // example: (0, 0) (1, 2)
83 }