dkh.graph.bridge source code

1 module dkh.graph.bridge;
2 
3 import dkh.graph.dfstree;
4 
5 struct BridgeInfo {
6     bool[] isRoot;
7     int count; // group count
8     int[] id, root; // i to group, group root
9     this(int n) {
10         isRoot = new bool[n];
11         id = new int[n];
12     }
13 }
14 
15 BridgeInfo bridge(T)(T g) {
16     return bridge(g, dfsTree(g));
17 }
18 
19 BridgeInfo bridge(T)(T g, DFSTreeInfo info) {
20     import std.conv : to;
21     int n = g.length.to!int;    
22     auto br = BridgeInfo(n);
23     
24     with (br) with (info) {
25         foreach (p; vlis) {
26             isRoot[p] = (low[p] == ord[p]);
27             if (isRoot[p]) {
28                 id[p] = count++;
29                 root ~= ((par[p] == -1) ? -1 : id[par[p]]);
30             } else {
31                 id[p] = id[par[p]];
32             }
33         }
34     }
35     return br;
36 }
37 
38 unittest {
39     import std.algorithm, std.conv, std.stdio;
40     import std.random;
41     import std.typecons;
42     import dkh.datastructure.unionfind;
43 
44     alias E = Tuple!(int, "to");
45 
46     void f() {
47         //make graph
48         int n = uniform(1, 20);
49         int m = uniform(1, 100);
50         E[][] g = new E[][](n);
51         int[2][] edges;
52         auto qf = UnionFind(n);
53         foreach (i; 0..m) {
54             int x = uniform(0, n);
55             int y = uniform(0, n);
56             edges ~= [x, y];
57             g[x] ~= E(y); g[y] ~= E(x);
58             qf.merge(x, y);
59         }
60 
61         import std.conv;
62         //component count
63         int connect = (){
64             auto qf = UnionFind(n);
65             edges.each!(v => qf.merge(v[0], v[1]));
66             return qf.count.to!int;
67         }();
68 
69         auto br = bridge(g);
70         auto naive = UnionFind(n);
71         //nonbridge union
72         foreach (i; 0..m) {
73             int c = (){
74                 auto qf = UnionFind(n);
75                 edges.each!((j, v){if (i != j) qf.merge(v[0], v[1]);});
76                 return qf.count.to!int;
77             }();
78             if (connect == c) {
79                 //not bridge
80                 naive.merge(edges[i][0], edges[i][1]);
81             }
82         }
83         assert(br.count == naive.count);
84         foreach (i; 0..n) {
85             foreach (j; 0..n) {
86                 bool same1 = (br.id[i] == br.id[j]);
87                 bool same2 = naive.same(i, j);
88                 assert(same1 == same2);
89             }
90         }
91     }
92     import dkh.stopwatch;
93     auto ti = benchmark!f(500);
94     writeln("Bridge Random500: ", ti[0].toMsecs());
95 }