CUFP
FoxtrotUniform
snippet
<div class="Description"><p>Ever needed (or wanted) to generate a tree (in this case, a graph on n vertices with n-1 edges) at random? Dismayed that the obvious method (adding a 1-2 edge, then randomly picking a vertex to connect 3 to, then 4) doesn't produce all possible trees (1-3-2 simply can't be done)? Your prayers are answered! This code uses Prüfer sequences (for which Google generates <i>no</i> useful introductory hits) to describe trees... turns out you can rank the n<sup>n-2</sup> labelled trees, generate the Prüfer sequence corresponding to that rank, then reconstruct the tree from the sequence.</p>
<p>This code is pretty much a straight implementation of the pseudocode in [http://www.math.mtu.edu/~kreher/cages.html|Combinatorial Algorithms: Generation, Enumeration, and Search].</p></div>
<CODE>
use strict;
use POSIX qw(floor);
use Data::Dumper;
# rank_to_prufer(r, n)
# Generates the Prufer sequence for the n-vertex tree of rank
# r.
sub rank_to_prufer
{
my ($rank, $n) = @_;
my @prufer = ();
for(my $i = $n - 2; $i > 0; $i--) {
my $new = $rank % $n + 1;
unshift @prufer, $new;
$rank = POSIX::floor(($rank - $new + 1) / $n);
}
return @prufer;
}
# prufer_to_tree(seq)
# Generates the tree corresponding to the Prufer sequence seq
sub prufer_to_tree
{
my @prufer = @_;
my $n = scalar @prufer + 2;
my @edges = ();
my @degrees = (1) x $n;
push @prufer, 1;
for (0 .. $n - 3) {
my $i = $prufer[$_] - 1;
$degrees[$i]++;
}
for (0 .. $n - 2) {
my $x = $n-1;
while($degrees[$x] != 1) {$x--;}
my $y = $prufer[$_] - 1;
$degrees[$x]--;
$degrees[$y]--;
my @edge = ($x+1, $y+1);
push @edges, \@edge;
}
return @edges;
}
# example call -- generate a random 6-vertex tree
my @tree = &prufer_to_tree(&rank_to_prufer(rand(1296), 6));
</CODE>