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

NAME

Graph::Maker::TwindragonAreaTree - create twindragon area tree graph

SYNOPSIS

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

DESCRIPTION

Graph::Maker::TwindragonAreaTree creates a Graph.pm graph of a twindragon area tree.

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

Graph vertices are unit squares inside the twindragon curve. For a level=k curve there are 2^k vertices. Edges are between squares beside consecutive segments of the curve. Or equivalently if the curve is drawn with corners chamfered off to leave little gaps at corners then edges connect squares through those gaps. See the author's long mathematical write-up for more

Vertices are numbered 0 to 2^level-1 which are complex base i+1 point numbers corresponding to the unit squares in the twindragon. With this numbering the edges are between bit patterns

    xxx0  --- xxx1       horizontal, toggle low bit

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

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 1 = 01 binary and 2 = 10 binary. These are 01 with no trailing 0s connected to 10 with no trailing 1s.

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

Level=3 has the first degree-3 vertices. Vertex 2 = binary 010 is the left of a horizontal to 3=011 (toggle low bit), and the upper of a vertical edge down to 1=001, and the lower of a further vertical edge up to 5=101.

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

Vertices are always degree 1, 2 or 3. Vertex 0 can be considered as a 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 0100..00 in the first copy and 1011..11 in the second. In the level=6 example above this is vertices 47 and 16.

Coordinates

Vertex numbers can be converted to X,Y coordinates in complex base i+1 using Math::PlanePath::ComplexPlus.

    use Math::PlanePath::ComplexPlus;
    my $path = Math::PlanePath::ComplexPlus->new;
    my $graph = Graph::Maker->new ('twindragon_area_tree', level=>5);
    foreach my $edge ($graph->edges) {
      my ($v1,$v2) = @$edge;
      my ($x1,$y1) = $path->n_to_xy($v1);
      my ($x2,$y2) = $path->n_to_xy($v2);
      # draw an edge from ($x1,$y1) to ($x2,$y2) ...
    }

This is the layout of the level=6 sample above. Edges are unit lengths horizontal or vertical and do not cross. Of course there's many other layouts possible.

FUNCTIONS

$graph = Graph::Maker->new('twindragon_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 twindragon area trees include

level=0, https://hog.grinvin.org/ViewGraphInfo.action?id=1310 (single vertex)
level=1, https://hog.grinvin.org/ViewGraphInfo.action?id=19655 (path-2)
level=2, https://hog.grinvin.org/ViewGraphInfo.action?id=594 (path-4)
level=3, https://hog.grinvin.org/ViewGraphInfo.action?id=700
level=4, https://hog.grinvin.org/ViewGraphInfo.action?id=28549

SEE ALSO

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

Math::PlanePath::ComplexPlus

A level 10 twindragon area tree appears in Mandelbrot's "Fractal Geometry of Nature", second edition, 1983, page 67, called by Mandelbrot the "twindragon river". Some generated drawings of that level are at the author's page above.

A level 9 twindragon area tree is in McWorter and Tazelaar, "Creating Fractals", Byte Magazine, August 1987, pages 459-480, figure B.

LICENSE

Copyright 2015, 2016, 2017 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/.