dkh.graph.namori source code

1 /**
2 Unstable
3 */
4 module dkh.graph.namori;
5 
6 import dkh.graph.dfstree;
7 
8 struct NamoriInfo {
9     bool[] isCycle;
10     int[][] cycles;
11     int[] root;
12     this(int n) {
13         isCycle = new bool[n];
14         root = new int[n];
15     }
16 }
17 
18 Namori namori(T)(T g) {
19     import std.algorithm : find, each;
20     import std.range;
21     import std.conv : to;
22     int n = g.length.to!int;
23     auto info = dfsInfo(g);
24     auto nmr = NamoriInfo(n);
25     with (nmr) {
26         //find self loop
27         foreach (i; 0..n) {
28             if (g[i].find!(e => e.to == i).empty) continue;
29             isCycle[i] = true;
30             cycles ~= [i];
31         }
32         foreach (p; info.vlis) {
33             if (info.low[p] == info.ord[p]) continue;
34             if (g[p].length == info.tr[p].length+1) continue;
35             int[] v;
36             int nw = p;
37             while (info.ord[nw] != info.low[p]) {
38                 v ~= nw;
39                 nw = info.par[nw];
40             }
41             v ~= nw;
42             v.each!(i => isCycle[i] = true);
43             cycles ~= v;
44         }
45         bool[] used = new bool[n];
46         void dfs(int p, int b, int r) {
47             if (used[p]) return;
48             used[p] = true;
49             root[p] = r;
50             foreach (e; g[p]) {
51                 int d = e.to;
52                 if (d == b) continue;
53                 if (isCycle[d]) continue;
54                 dfs(d, p, r);
55             }
56         }
57         foreach (i; 0..n) {
58             if (!isCycle[i]) continue;
59             dfs(i, -1, i);
60         }
61     }
62     return nmr;
63 }
64 
65 NamoriInfo directedNamori(int[] g) {
66     import std.algorithm : find, each;
67     import std.range;
68     import std.conv : to;
69     int n = g.length.to!int;
70     auto nmr = NamoriInfo(n);
71     with (nmr) {
72         int[] used = new int[n]; used[] = -1;
73         foreach (i; 0..n) {
74             if (used[i] != -1) continue;
75             int j = i;
76             while (used[j] == -1) {
77                 used[j] = i;
78                 j = g[j];
79             }
80             if (used[j] != i) continue;
81             int k = j;
82             int[] cy = [];
83             while (true) {
84                 cy ~= k;
85                 isCycle[k] = true;
86                 if (g[k] == j) break;
87                 k = g[k];
88             }
89             cycles ~= cy;
90         }
91         int[] dp = new int[n]; dp[] = -1;
92         int dfs(int p) {
93             if (isCycle[p]) return p;
94             if (dp[p] != -1) return dp[p];
95             return dp[p] = dfs(g[p]);
96         }
97         foreach (i; 0..n) {
98             root[i] = dfs(i);
99         }
100     }
101     return nmr;
102 }