dkh.graph.bipatitematching source code

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