++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors

# 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 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. One spine is the verticals 0,3,12,15,etc, the other is the North West stair-step 0,1,6,7,24,etc. The vertical and vertices branching off from it are N with an even length in binary. The NW and 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 graphs here 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=260 (path-8)
level=4, https://hog.grinvin.org/ViewGraphInfo.action?id=27042
level=5, https://hog.grinvin.org/ViewGraphInfo.action?id=27044
level=6, https://hog.grinvin.org/ViewGraphInfo.action?id=27046

# 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``````