dkh.graph.bridge source code

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