Graph::Maker::BalancedTree - Creates a balanced tree with specified fan out and height

	use strict;
	use warnings;
        use Graph;
	use Graph::Maker;
	use Graph::Maker::BalancedTree;

	my $g = new Graph::Maker('balanced_tree', fan_out => 3, height => 3);
	# work with the graph

package Graph::Maker::BalancedTree;

use strict;
use warnings;
use Carp qw/croak/;
use base qw/Graph::Maker/;
use Graph;

our $VERSION = '0.01';

sub init
{
	my ($self, %params) = @_;

	my $b = delete($params{fan_out});
	my $h = delete($params{height});
	my $gm = delete($params{graph_maker});
	croak "graph_maker must be a reference to a function that creates a Graph.\n" if $gm && ref($gm) ne 'CODE';
	$gm ||= sub { new Graph(@_); };

	croak "fan_out must be defined and at least 2\n" unless defined $b && $b >= 2;
	croak "h must be defined and positive\n" unless defined $h && $h >= 1;

	my $g = $gm->(%params);

	# First handle the root
	my $v = 2; # the vertex number
	my @newLeaves; # the set of new leaves
	for (1..$b)
	{
		push(@newLeaves, $v);
		$g->add_edge(1, $v);
		$g->add_edge($v, 1) unless $g->is_undirected();
		$v++;
	}

	# Now the rest
	for (2..$h-1)
	{
		my @leaves = @newLeaves;
		@newLeaves = ();
		foreach my $l(@leaves)
		{
			for (1..$b)
			{
				push(@newLeaves, $v);
				$g->add_edge($l, $v);
				$g->add_edge($v, $l) unless $g->is_undirected();
				$v++;
			}
		}
	}

	return $g;
}

Graph::Maker->add_factory_type( 'balanced_tree' => __PACKAGE__ );

1;


__DATA__