++ed by:

1 non-PAUSE user.

and 1 contributors

# 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

``````    1310   level=0, singleton
19655  level=1, path-2
594    level=2, path-4
700    level=3
28549  level=4
31086  level=5
33581  level=6
33583  level=7``````

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.