view release on metacpan or  search on metacpan

eg/components.pl  view on Meta::CPAN

# Prefer a freshly built blib/ (picks up both lib and the compiled .so),
# fall back to lib/ or the installed module.
BEGIN {
    my $blib = "$FindBin::Bin/../blib";
    if (-d "$blib/arch") { require blib; blib->import($blib) }
    else { unshift @INC, "$FindBin::Bin/../lib" }
}
use Data::DisjointSet::Shared;

# Connected components of an undirected graph via union-find. We have a fixed
# set of vertices (0 .. N-1) and a fixed edge list; unioning the endpoints of
# every edge collapses each connected component into one disjoint set. We then
# report how many components there are and the size of each.

my $N = 10;   # vertices 0 .. 9

# A fixed edge list producing three components:
#   {0,1,2,3}, {4,5}, {6,7,8,9}
my @edges = (
    [0, 1], [1, 2], [2, 3],   # component A
    [4, 5],                    # component B

xt/fork_dsu.t  view on Meta::CPAN

waitpid $_, 0 for @pids;

# K bands, each fully collapsed to one set -> exactly K disjoint sets remain.
is $d->num_sets, $kids,
   sprintf('cross-process: num_sets == %d (each of %d bands collapsed to one set)', $kids, $kids);

# Within-band connectivity holds; across-band does not.
my $within_bad = 0;
for my $k (0 .. $kids - 1) {
    my $base = $k * $band;
    $within_bad++ unless $d->connected($base, $base + $band - 1);   # band endpoints joined
    $within_bad++ unless $d->set_size($base) == $band;              # band set has 'band' members
}
is $within_bad, 0, 'cross-process: every band is fully connected with the expected size';

my $across_bad = 0;
for my $k (0 .. $kids - 2) {
    my $a = $k * $band;
    my $b = ($k + 1) * $band;
    $across_bad++ if $d->connected($a, $b);     # different bands stay disjoint
}