dkh.graph.hldecomp source code

1 /**
2 Unstable
3 */
4 module dkh.graph.hldecomp;
5 
6 import dkh.container.stackpayload;
7 
8 struct HLInfo {
9     int[2][] id; //vertex -> [line id, line pos]
10     int[][] lines; //line id -> line list(top to bottom)
11     int[2][] par; //line id -> [parent line id, parent line pos]
12     int[] lineDPS; //line id -> line depth
13     this(size_t n) {
14         id = new int[2][n];
15     }
16 }
17 
18 /// calc lca(a, b)
19 int calcLCA(in HLInfo hl, int a, int b) {
20     import std.algorithm : swap;
21     with (hl) {
22         int[2] xl = id[a];
23         int[2] yl = id[b];
24         if (lineDPS[xl[0]] < lineDPS[yl[0]]) swap(xl, yl);
25         while (lineDPS[xl[0]] > lineDPS[yl[0]]) {
26             xl = par[xl[0]];
27         }
28         while (xl[0] != yl[0]) {
29             xl = par[xl[0]];
30             yl = par[yl[0]];
31         }
32         if (xl[1] > yl[1]) swap(xl, yl);
33         return lines[xl[0]][xl[1]];
34     }
35 }
36 
37 HLInfo hlDecomposition(T)(in T g, int rt) {
38     auto n = g.length;
39     auto hl = HLInfo(n);
40     with (hl) {
41         int[] sz = new int[n];
42         int calcSZ(int p, int b) {
43             sz[p] = 1;
44             foreach (e; g[p]) {
45                 if (e.to == b) continue;
46                 sz[p] += calcSZ(e.to, p);
47             }
48             return sz[p];
49         }
50         calcSZ(rt, -1);
51         int idc = 0;
52         StackPayload!(int[2]) par_buf;
53         StackPayload!int line_buf, dps_buf;
54         void dfs(int p, int b, int height) {
55             line_buf ~= p;
56             id[p] = [idc, height];
57             int nx = -1, buf = -1;
58             foreach (e; g[p]) {
59                 if (e.to == b) continue;
60                 if (buf < sz[e.to]) {
61                     buf = sz[e.to];
62                     nx = e.to;
63                 }
64             }
65             if (nx == -1) {
66                 //make line
67                 lines ~= line_buf.data.dup;
68                 line_buf.clear;
69                 idc++;
70                 return;
71             }
72 
73             dfs(nx, p, height+1);
74             foreach (e; g[p]) {
75                 if (e.to == b || e.to == nx) continue;
76                 par_buf ~= id[p];
77                 dps_buf ~= dps_buf.data[id[p][0]] + 1;
78                 dfs(e.to, p, 0);
79             }
80         }
81         par_buf ~= [-1, -1];
82         dps_buf ~= 0;
83         dfs(rt, -1, 0);
84         par = par_buf.data;
85         lineDPS = dps_buf.data;
86     }
87     return hl;
88 }