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.
3031 1415
level => 6  
2829 1213
 
2627 2223 1011 67
      
2425 2021 89 45
 
6263 4647 1819 23
    
6061 4445 1617 01
 
5859 5455 4243 3839
      
5657 5253 4041 3637
 
5051 3435
 
4849 3233
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 writeup for more
Vertices are numbered 0 to 2^level1 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.
01 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.
23
 level => 2
01
Level=3 has the first degree3 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.
67

45 level => 3

23

01
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
orGraph>new()
.Like
Graph::Maker::BalancedTree
, if the graph is directed (the default) then edges are added in both directions between nodes. Optionundirected => 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 (path2)
 level=2, https://hog.grinvin.org/ViewGraphInfo.action?id=594 (path4)
 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
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 459480, 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/.