File Coverage

blib/lib/Graph/Maker/TwindragonAreaTree.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::TwindragonAreaTree;
use 5.004;
use strict;
use Graph::Maker;

use vars '$VERSION','@ISA';
$VERSION = 8;
@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 $level = delete($params{level}) || 0;
  my $graph_maker = delete($params{'graph_maker'}) || \&_default_graph_maker;
  ### $level

  my $graph = $graph_maker->(%params);
  $graph->set_graph_attribute(name => "Twindragon Area Tree $level");
  $graph->add_vertex(0);
  my $directed = $graph->is_directed;

 V: foreach my $v (0 .. 2**$level-1) {
    # ...1 edge to ...0
    if ($v & 1) {
      my $to = $v ^ 1;
      $graph->add_edge($v, $to);
      if ($directed) { $graph->add_edge($to, $v); }
    }

    #  ...10 11...11
    #        \-----/ zero or more low 1 bits
    # edge to
    #  ...01 00...00
    #
    my $bit = 1;
    for (my $pos = 1; ; $pos++) {
      $pos < $level or next V;
      $v & $bit or last;
      $bit <<= 1;
    }
    $bit <<= 1;
    if ($v & $bit) {
      my $to = $v-$bit+1;
      $graph->add_edge($v, $to);
      if ($directed) { $graph->add_edge($to, $v); }
    }
  }
  return $graph;
}

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