findMaximallyConnectedComponents

1 import std.algorithm : equal;
2 import std.range : only;
3 
4 alias modEqv(size_t m) = (a, b) => (a % m) == (b % m);
5 alias clusterByThreshold(size_t t) = (a, b) => (a < t) == (b < t);
6 
7 assert(equal(
8     findMaximallyConnectedComponents!(modEqv!5)(15),
9     only(
10         NaturalNumberSet.create(0, 5, 10),
11         NaturalNumberSet.create(1, 6, 11),
12         NaturalNumberSet.create(2, 7, 12),
13         NaturalNumberSet.create(3, 8, 13),
14         NaturalNumberSet.create(4, 9, 14),
15     ),
16 ));
17 assert(equal(
18     findMaximallyConnectedComponents!(modEqv!3)(15),
19     only(
20         NaturalNumberSet.create(0, 3, 6, 9, 12),
21         NaturalNumberSet.create(1, 4, 7, 10, 13),
22         NaturalNumberSet.create(2, 5, 8, 11, 14),
23     ),
24 ));
25 assert(equal(
26     findMaximallyConnectedComponents!(clusterByThreshold!10)(15),
27     only(
28         NaturalNumberSet.create(0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
29         NaturalNumberSet.create(10, 11, 12, 13, 14),
30     ),
31 ));

1 import std.algorithm : equal;
2 import std.range : only;
3 
4 auto connectivity = [
5     [false, false, false, true ],
6     [false, false, true , false],
7     [false, true , false, false],
8     [true , false, false, false],
9 ];
10 alias isConnected = (i, j) => connectivity[i][j];
11 
12 assert(equal(
13     findMaximallyConnectedComponents!isConnected(4),
14     only(
15         NaturalNumberSet.create(0, 3),
16         NaturalNumberSet.create(1, 2),
17     ),
18 ));