Description: | 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 This code is pretty much a straight implementation of the pseudocode in Combinatorial Algorithms: Generation, Enumeration, and Search. |

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));