view release on metacpan or  search on metacpan

lib/Graph/Maker/Catalans.pm  view on Meta::CPAN

# 7.2.1.6 algorithm L adapts to binary tree form.
#
# The graph has a Hamiltonian cycle per
#
# =over
#
# Ro-Yu Wu, Hung Lung Wang, "A Simple Proof for the Hamiltonian Property on
# Rotation Grpahs of Binary Trees" The 27th Workshop on Combinatorial
# Mathematics and Computation Theory
#
# =back
#
# Their approach starts from the Hamiltonian path, some of which is a base
# cycle, then show the rest are suitably cross linked to the cycle allowing
# them to be included (and a certain special case when N even).
#
# Another way is to extend an N-1 cycle to N cycle by new N up and down the
# same as for the path.  If length Catalan(N-1) is even then it ends back
# where it started.  If Catalan(N-1) is odd, which is N=2^k, then the first
# 11111 up and down to 11121 instead by zig-zag up for a single up (and
# reverse the rest suitably).

=pod

=head2 Rotate Right or Left Arm

Option C<rel_type =E<gt> 'rotate_rightarm'> restricts to rotates of edges on
the right arm of the binary tree, in the manner of

=over

J. M. Pallo, "Right-Arm Rotation Distance Between Binary Trees",
Information Processing Letters, volume 87, number 4, 2003, pages 173-177.

=cut

# doi: 10.1016/S0020-0190(03)00283-7

=pod

=back

         -------> 110010 -------_
        /                        v         N => 3
    101010                      111000     rel_type => "rotate_rightarm"
        \
         --> 101100 --> 110100

The resulting graph is "graded" in that it starts from all edges right arm
(101010), and each step reduces them by 1.  Counts of trees by right arm
length are a row of the Catalan triangle.

     T              rotate_rightarm
    / \
       *            only rotate edges
      / \           on the right-most arm
         *          extending down
        / \

In terms of balanced binary, right arm means rotate at "1aaaa0 1" where the
0 there is a return to the zero line.  The graph endpoints
(C<$graph-E<gt>successorless_vertices>) have no such returns to zero.  They
are "1 balanced(N-1) 0", and hence Catalan(N-1) many.

In terms of C<Ldepths>, right arm vertices have Ldepth=0 and the x,y
vertices of the rotate are consecutive Ldepth=0 (and other non-zeros in
between).  The rotate increases the depth of the second.

Csar, Sengupta, and Suksompong get various rightarm results too, as
X<comb poset>"comb poset" of bracketings.

=over

Sebastian A. Csar, Rik Sengupta, and Warut Suksompong. "On a Subposet of the
Tamari Lattice.", volume 31, number 3, October 2013, pages 337-363.
L<http://dx.doi.org/10.1007/s11083-013-9305-5>

=back

Option C<rel_type =E<gt> 'rotate_leftarm'> restricts to rotates which put a
new edge on the left arm, so rotate a right edge of a left arm vertex.  This
is isomorphic to C<rotate_rightarm> by considering binary trees in mirror
image.  In terms of balanced binary, left arm is a rotate at

    11..11 1aaaa0 1 ...          rotate_leftarm
    ^
    start of string initial run of 1s

The 1 of 1aaaa0 must be in the run of 1s at the start of the string.  It can
be anywhere in the run (including the very start of string), with aaaa
containing the rest of those 1s.

=cut

# In terms of C<bracketing_reduced>, each step adds a pair enclosing
# adjacent elements, either leaf term or parenthesized term.  The start is
# no parens so the first step encloses adjacent leaf terms (N positions).

=pod

=head2 Rotate First or Last

Option C<rel_type =E<gt> 'rotate_first'> restricts to rotate only at the
first possible place.  This result is a tree ("leftmost") per,

=over

J. M. Pallo, "Rotational Tree Structures on Binary Trees and
Triangulations", Acta Cybernetica, volume 17, 2006, pages 799-810.

=back

         -------> 110010 -------_
        /                        v         N => 3
    101010                      111000     rel_type => "rotate_first"
                                 ^
             101100 --> 110100 -/

Per Pallo, the resulting tree is "graded" by how many balanced binary
initial 1s, those being left arm.  Each first rotate moves the first
non-initial-1 to become part of the initial 1s.  The graph start vertices