The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Graph-Maker-Other-19
River stage zero No dependents
1 ++
/ Graph::Maker::TwinAlternateAreaTree

NAME

Graph::Maker::TwinAlternateAreaTree - create twin alternate area tree graph

SYNOPSIS

 use Graph::Maker::TwinAlternateAreaTree;
 $graph = Graph::Maker->new ('twin_alternate_area_tree', level => 6);

DESCRIPTION

Graph::Maker::TwinAlternateAreaTree creates a Graph.pm graph of a twin alternate area tree.

                                63--62  59--58  47--46  43--42
                                 |   |   |       |   |   |
                            61--60  57--56  45--44  41--40
                                 |       |       |
                        55--54  51--50  39--38  35--34
                         |   |   |       |   |   |
                    53--52  49--48  37--36  33--32
                                 |
                31--30  27--26  15--14  11--10
                 |   |   |       |   |   |
            29--28  25--24  13--12   9---8         level => 6
                 |       |       |
        23--22  19--18   7---6   3---2
         |   |   |       |   |   |
    21--20  17--16   5---4   1---0

Graph vertices are unit squares inside a twin alternate curve formed by two alternate paperfolding curves back-to-back, or equivalently a cycle of four such curves. For level=k the twin alternate is four level k paperfolding curves. It has 2^k squares inside which are vertices. Edges are between squares with segments consecutive in the curve. Or equivalently if the curves are drawn with corners chamfered off to leave little gaps at corners then edges connect squares through those gaps. See the author's mathematical write-up for more

Vertices are numbered 0 to 2^level-1. These are Z-order point numbers corresponding to the unit squares in the twin alternate. The layout above is Y-X + Y*i, so Y coordinate unchanged and horizontally Y-X shear and negate.

With this vertex numbering, edges are between bit patterns

    xxx0  --- xxx1       horizontal, toggle low bit

    xxx 11 00..00
        \-------/        vertical, toggle low run + 2
            |            when respective bit pattern
        /-------\
    xxx 00 11..11

Level=0 is a single vertex 0 and no edges.

Level=1 is two vertices 0 and 1 and an edge between them by the horizontal toggle low bit rule.

            0---1          level => 1

Level=2 has the vertical rule connecting vertices 0 = 00 binary and 3 = 11 binary. These are 11 with no trailing 0s, connected to 00 with no trailing 1s.

                3---2
                |             level => 2
            1---0

Level=3 is also still a path. Its middle vertical is 1 = 001 connected to 6 = 110 so a low run of one bit before the 00 - 11.

        7---6   3---2
        |   |   |              level => 3
    5---4   1---0

Level=4 is the first not simply a path. The new edge is 3 = binary 0011 up to 12 = binary 1100.

               15--14  11--10
                |   |   |
           13--12   9---8      level => 4
                |
        7---6   3---2
        |   |   |
    5---4   1---0

Vertices are degree 1, 2 or 3. Vertex 0 can be considered as the root. Level k+1 is formed by taking level k and extending with a second copy of level k connected by a middle edge. This is between bit patterns 0011..11 in the first copy and 1100..00 in the second, per the level=4 above. In the big level=6 example above this is vertices 15 to 48.

Each level is the previous plus a copy of that previous attached at the biggest bit pattern edge. The effect is to make two spines continuing infinitely.

    vertical spine                0,3,12,15,...
    North West stair-step spine   0,1, 6, 7,24,...

The vertical spine and the vertices branching off from it are N with an even length in binary. The NW spine and the vertices branching off from it are N with an odd length in binary.

FUNCTIONS

$graph = Graph::Maker->new('twin_alternate_area_tree', key => value, ...)

The key/value parameters are

    level       => integer >= 0
    graph_maker => subr(key=>value) constructor, default Graph->new

Other parameters are passed to the constructor, either graph_maker or Graph->new().

Like Graph::Maker::BalancedTree, if the graph is directed (the default) then edges are added in both directions between nodes. Option undirected => 1 creates an undirected graph and for it there is a single edge between vertices.

HOUSE OF GRAPHS

House of Graphs entries for the trees here include

    1310    level=0, singleton
    19655   level=1, path-2
    594     level=2, path-4
    260     level=3, path-8
    27042   level=4
    27044   level=5
    27046   level=6
    33541   level=7

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this tree include

    A053599    diameter of level
    A077866    height of level
    A001196    vertices of vertical spine
    A053754    vertices of vertical spine and branches from it,
                 being N binary even length
    A053738    vertices of NW spine and branches from it,
                 being N binary odd length

SEE ALSO

Graph::Maker, Graph::Maker::TwindragonAreaTree, Graph::Maker::BalancedTree

Math::PlanePath::AlternatePaper

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

Copyright 2017, 2018, 2019, 2020, 2021 Kevin Ryde

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 This file. If not, see http://www.gnu.org/licenses/.