dkh.graph.hldecomp source code

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