dkh.graph.namori source code

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