File Coverage

blib/lib/Graph/Maker/BinomialTree.pm

Criterion	Covered	Total	%
statement	6	8	75.0
branch			n/a
condition			n/a
subroutine	3	3	100.0
pod			n/a
total	9	11	81.8

# Copyright 2015, 2016, 2017 Kevin Ryde
#
# This file is part of Graph-Maker-Other.
#
# This file is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the Free
# Software Foundation; either version 3, or (at your option) any later
# version.
#
# This file is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
# or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
# for more details.
#
# You should have received a copy of the GNU General Public License along
# with Graph-Maker-Other.  See the file COPYING.  If not, see
# .

package Graph::Maker::BinomialTree;
use 5.004;
use strict;
use Graph::Maker;

use vars '$VERSION','@ISA';
$VERSION = 7;
@ISA = ('Graph::Maker');

# uncomment this to run the ### lines
# use Smart::Comments;


sub _default_graph_maker {
  require Graph;
  Graph->new(@_);
}

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

  my $N     = delete($params{'N'});
  my $order = delete($params{'order'});
  my $graph_maker = delete($params{'graph_maker'}) || \&_default_graph_maker;

  my $graph = $graph_maker->(%params);

  my $limit;
  if (! defined $N) {
    $limit = 2**$order - 1;
    $graph->set_graph_attribute (name => "Binomial Tree, order $order");
  } else {
    $limit = $N-1;
    if ($N <= 0) {
      $graph->set_graph_attribute (name => "Binomial Tree, empty");
    } else {
      $graph->set_graph_attribute (name => "Binomial Tree, 0 to $limit");
    }
  }

  ### $limit
  if ($limit >= 0) {
    $graph->add_vertex(0);
    my $directed = $graph->is_directed;

    foreach my $i (1 .. $limit) {
      my $parent = $i & ~($i ^ ($i-1));  # clear lowest 1-bit
      ### edge: "$parent down to $i"
      $graph->add_edge($parent, $i);
      if ($directed) { $graph->add_edge($i, $parent); }
    }
  }
  return $graph;
}

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

__END__