Graph::Maker::Regular - Creates a k-regular graph.

	use strict;
	use warnings;
        use Graph;
	use Graph::Maker;
	use Graph::Maker::Regular;

	my $g = new Graph::Maker('regular', N => 10, K => 2, undirected => 1);
	# work with the graph

package Graph::Maker::Regular;

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

our $VERSION = '0.01';

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

	my $n = delete($params{N}) || 0;
	my $k = delete($params{K}) || 0;
	$k = $n if $k > $n;
	croak "N*K (" . ($n*$k) . ") must be even\n" if ($n*$k) & 1;
	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(@_); };

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

	my @a = (1..$n);
	my %c;

	while(@a > 1)
	{
		my @e = random_uniform_integer(2, 0, @a-1);
		if($e[0] != $e[1] && !$g->has_edge(@a[@e]))
		{
			$g->add_edge(@a[@e]);
			$g->add_edge(reverse @a[@e]) unless $g->is_undirected();
			$c{$a[$e[0]]}++;
			$c{$a[$e[1]]}++;
			#print "\tAdded @a[@e]\t[@a]\n";
			if($c{$a[$e[0]]} >= $k)
			{
				#print "\tRemoving $c{$a[$e[0]]} $a[$e[0]]\n";
				splice(@a, $e[0], 1);
				$e[1]-- if $e[1] > $e[0];
			}
			splice(@a, $e[1], 1) if $c{$a[$e[1]]} >= $k;
			#print "\t\t\t[@a]\n";
		}
		else
		{
			#print "\twarnings...$a[$e[0]] $a[$e[1]]\n";
			my $b = 0;
			foreach my $u(@a)
			{
				last if $b;
				foreach my $v(@a)
				{
					do {$b = 1; last} if $u != $v && !$g->has_edge($u, $v);
				}
			}
			next if $b;
			croak "Could not form the requested graph...\n";
		}
	}

	croak "Could not form the requested graph...\n" if @a;

	return $g;
}

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

1;

__DATA__