dkh.graph.ariticulation source code

1 /**
2 Unstable
3 */
4 
5 module dkh.graph.ariticulation;
6 
7 import dkh.graph.dfstree;
8 
9 struct AriticulationInfo {
10     bool[] isArit; // is Ariticulation point
11     bool[] isDiv; // is Div when parent remove
12 };
13 
14 AriticulationInfo ariticulation(T)(T g) {
15     return ariticulation(g, dfsTree(g));
16 }
17 
18 AriticulationInfo ariticulation(T)(T g, DFSTreeInfo info) {
19     AriticulationInfo arit;
20     arit.isArit.length = g.length;
21     arit.isDiv.length = g.length;
22     foreach (p ; info.vlis) {
23         if (info.par[p] == -1) {
24             //root
25             arit.isArit[p] = (info.tr[p].length >= 2);
26             foreach (d; info.tr[p]) {
27                 arit.isDiv[d] = true;
28             }
29         } else {
30             arit.isArit[p] = false;
31             foreach (d; info.tr[p]) {
32                 if (info.low[d] >= info.ord[p]) {
33                     arit.isArit[p] = true;
34                     arit.isDiv[d] = true;
35                 }
36             }
37         }
38     }
39     return arit;
40 }
41 
42 unittest {
43     import std.algorithm : equal;
44     import std.typecons;
45     alias E = Tuple!(int, "to");
46     E[][] g = new E[][4];
47     g[0] ~= E(1); g[1] ~= E(0);
48     g[0] ~= E(2); g[2] ~= E(0);
49     g[1] ~= E(2); g[2] ~= E(1);
50     g[1] ~= E(3); g[3] ~= E(1);
51     auto ai = g.ariticulation;
52     import std.stdio;
53     writeln(dfsTree(g));
54     writeln(ai);
55     assert(equal(ai.isArit, [false, true, false, false]));
56 }