++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors

# NAME

Graph::Maker::BinaryBeanstalk - create binary beanstalk graph

# SYNOPSIS

`````` use Graph::Maker::BinaryBeanstalk;
\$graph = Graph::Maker->new ('binary_beanstalk', height => 4);``````

# DESCRIPTION

`Graph::Maker::BinaryBeanstalk` creates `Graph.pm` graphs of the binary beanstalk per OEIS A179016 etc.

``````    12  13  14  15
\ /    \ /
10    11           height => 8
\  /
8   9
\ /
6   7
\ /
4   5
\ /
2   3
\ /
1
|
0``````

Vertices are integers starting at root 0. Vertex n has parent n-CountOneBits(n). For example 9 = 1001 binary has 2 1-bits so parent 9-2=7. For n>=1 each vertex has either 0 or 2 children, hence "binary" beanstalk.

After the root there are exactly 0 or 2 children. There are always 2 children since if a given even vertex c has parent c-CountOneBits(c)=n then the next vertex c+1 has same

``    parent(c+1) = (c+1) - (CountOneBits(c)+1)  = n``

There are no more than 2 children since the next even vertex c+2 has 1-bit count

``````    CountOneBits(c+2) <= CountOneBits(c) + 1
equality when c==0 mod 4, otherwise less``````

due to flipping run of 1-bits at second lowest bit position. So parent(c+2) >= c+2 - (CountOneBits(c)+1) = n+1, so not the same n parent of c.

This also means the parent n is always increasing, and therefore the vertices in a given row are contiguous integers. That's so of the single vertex row 1 and thereafter remains so by parent number increasing.

The vertices in a given row which have children are not always contiguous. The first gap occurs at depth 36 where the vertices with children are 116,117,119 skipping 118.

``````    120 121  122 123    124 125
\   /    \   /      \   /
116      117   118  119
\     /       \   /
112          113
\-----v------/``````

## Options

`height` specifies the height of the tree, as number of rows. Height 1 is the root alone, height 2 is two rows being are vertices 0 and 1, etc.

`N` specifies how many vertices, being vertex numbers 0 to N-1 inclusive.

If both `height` and `N` are given then the tree stops at whichever `height` or `N` comes first. Since vertex numbers in a row are contiguous, specifying height is equivalent to an N limit of the first vertex of the row after, so 1, 2, 4, 6, 8, etc (OEIS A213708).

# FUNCTIONS

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

The key/value parameters are

``````    height  =>  integer
N       =>  integer
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 both up and down between each parent and child. Option `undirected => 1` creates an undirected graph and for it there is a single edge from parent to child.

# HOUSE OF GRAPHS

House of Graphs entries for graphs here include

height=5, https://hog.grinvin.org/ViewGraphInfo.action?id=502

# OEIS

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

``````    A011371    parent vertex, being n-CountOneBits(n)
A213723    child vertex, smaller
A213724    child vertex, bigger

A071542    depth of vertex
A213706    depth of vertex, cumulative
A213708    first vertex in row
A173601    last vertex in row
A086876    row width (run lengths of depth)

A055938    leaf vertices
A005187    non-leaf vertices
A179016    trunk vertices
A213712    trunk increments, = count 1-bits of trunk vertex
A213719    trunk vertex predicate 0,1
A213729    trunk vertices mod 2
A213728    trunk vertices mod 2, flip 0<->1
A213732    depths of even trunk vertices
A213733    depths of odd trunk vertices
A213713    non-trunk vertices
A213717    non-trunk non-leaf vertices
A213731    0=leaf, 1=trunk, 2=non-trunk,non-leaf
A213730    start of non-trunk subtree
A213715    trunk position within non-leafs
A213716    non-trunk position within non-leafs
A213727    num vertices in subtree under n (inc self), or 0=trunk
A213726    num leafs in subtree under n (inc self), or 0=trunk
A257126    nth leaf - nth non-leaf
A257130    new high positions of nth leaf - nth non-leaf
A218254    paths to root 0
A213707    positions of root 0 in these paths

A218604    num vertices after trunk in row
A213714    how many non-leaf vertices precede n
A218608    depths where trunk is last in row
A218606    depths+1 where trunk is last in row
A257265    depth down to a leaf, minimum
A213725    depth down to a leaf, maximum in subtree

A218600    depth of n=2^k-1
A213709    depth levels from n=2^k-1 to n=2^(k+1)-1
A213711    how many n=2^k-1 blocks preceding given depth
A213722    num non-trunk,non-leaf v between 2^n <= v < 2^(n+1)``````