/ 
Graph-Maker-Other-19
River stage zero No dependents
/ Graph::Maker::Catalans

NAME

Graph::Maker::Catalans - create Tamari lattice and other Catalan object graphs

SYNOPSIS

use Graph::Maker::Catalans;
$graph = Graph::Maker->new ('Catalans', N => 4);

DESCRIPTION

Graph::Maker::Catalans creates Graph.pm graphs where each vertex represents a "Catalan object", any one of

* balanced binary string (Dyck word) of length 2N
* binary tree of N internal vertices
* ordered forest of N vertices

num vertices = Catalan(N) = 1,1,2,5,14,42, ... (A000108)

Binary trees are rooted and each vertex has a left and right child subtree, each possibly empty. There are many more combinatorial objects counted by the Catalan numbers and in one-to-one correspondence. The present ones are where the graph relations here have direct interpretation.

The default graph is the Tamari lattice (associahedron, binary tree rotation graph, see "Rotate" below), with vertex names as balanced binary strings. But there are 12 relation types (10 up to isomorphism) and 13 vertex name types. The lattices are the algebra type of lattice (partially ordered set relations).

Vertex Names

Option vertex_name_type chooses the vertex name style. The edge relation rules are sometimes simpler or more complex in one or other type. In all cases the underlying object and relation is unchanged, just the vertex names differ.

Balanced Binary

Default vertex_name_type => 'balanced' is strings of N many 1s and N many 0s where the 1s and 0s nest like open and close parens.

    /\
 /\/  \  /\       mountain range, 1 up, 0 down
/      \/  \
110110001100      balanced binary
(()(()))(())      parens

The heights in the mountain range are like nesting levels of the parens. Balanced binary corresponds to a binary tree coded recursively, starting at the root,

1, left subtree, 0, right subtree         = balanced

This is pre-order traversal of the binary tree with 1 for a vertex, 0 for an empty child position (an "external"), and final 0 omitted.

           1                    binary tree, pre-order
       /       \                1 = "internal" vertex
    1             1             0 = "external" empty position
  /   \         /   \           last external omitted
0      1      1     (0)
      / \    / \                110110001100
     1   0  0   0
    / \
   0   0

Option vertex_name_type => 'balanced_postorder' is the tree coded by postorder traversal. Each external is a 1, each internal is a 0, except the very first 1 omitted. This is a recursive coding

left subtree, 1, right subtree, 0     = balanced_postorder

There is no in-order bit coding because left,1,right is merely 0101010 for every tree.

Depths

Option vertex_name_type => 'Ldepths' is left depth of each binary tree vertex in pre-order. Left depth is how many left steps down to the vertex. The example above is

0,1,1,2,0,1         Ldepths

Ldepths in terms of balanced binary is at each 1-bit count how many unclosed 1s precede there (excess of 1s over 0s). This is since each 1 is a vertex and the next edge is a left descent, and each 0 goes back up that left (and takes a right descent).

1 101 1 0001 100    balanced binary
0,1,1,2,   0,1      Ldepths

Ordered forests are in one-to-one correspondence with binary trees by the "natural correspondence". (See for example Knuth volume 1 section 2.3.2 for pictures and description.) Ldepths is vertex depth in the ordered forest.

binary left child  = ordered first child     \    natural
binary right child = ordered next sibling    / correspondence

     1                1       5
  /     \             | \     |           pre-order
 2       5            2  3    6           labelling
  \     /                |
   3   6                 4
  /
 4

binary tree         ordered forest

Option vertex_name_type => 'Ldepths_inorder' is the same Ldepths but vertices taken in-order. In terms of balanced binary, at each 0 count how many unclosed 0s are after it. Or equivalently, how many unclosed 1s precede and the 0 itself included as a closing.

In terms of ordered forest, in-order binary tree traversal is postorder forest traversal. So Ldepths_inorder is forest depths postorder.

Option vertex_name_type => 'Rdepths_inorder' is right depths of the binary tree traversed in-order. Right depth is how many right steps down. This is Makinen's "distance" representation. In terms of ordered forest, right depth is a horizontal position (how many preceding siblings, plus parent how many preceding siblings, etc).

Option Bdepths_inorder is all steps down, so Ldepths_inorder plus Rdepths_inorder.

Option vertex_name_type => 'Rdepths_postorder' is right depths of the binary tree traversed post-order.

The above have only one pre-order and one post-order. The omitted combinations are pre R,B and post L,B. They do not uniquely identify their tree object, ie. multiple trees have the same resulting vector.

Runs

Option vertex_name_type => 'run1s' is run lengths of 1s. At each 0 of balanced binary, count how many 1s immediately precede it (possibly zero). For example,

110 1110 0 0 10 0      balanced
  2,   3,0,0, 1,0      run1s

Sapounakis, Tasoulas, and Tsikouras, use this form for "Filling" below. They note run1s is a "dominating sequence" in the sense sum(terms 1..k) >= k (first term k=1). sum - k is Ldepths_inorder.

In terms of binary tree, each 0 is an external vertex and the number of 1s preceding is the number of left edges above it. So run1s is the length of the left-edges chain immediately above above each external (and omitting the right-most external which is always right so always 0).

Option vertex_name_type => 'run0s' is run lengths of 0s. At each 1 of balanced binary, count how many 0s immediately follow it (possibly none).

1 10 1 1 1000 10 0      balanced
0,1, 0,0,3,   2         run0s

run0s gives Ldepths differences. Each 1 is a binary tree vertex in preorder. If no 0s then the next vertex is below so depth +1, whereas each 0 is empty positions so next vertex higher.

run0s[i] = Ldepths[i]+1 - Ldepths[i+1]      depth decrease
             with an additional Ldepths[N+1] = 0

Vpar

Option vertex_name_type => 'vpar' gives the vertex parent array of the ordered forest in pre-order. Vertices are numbered 1 to N and each vpar entry is the parent vertex number, or 0 if no parent (a root). The first vertex is the first root, so vpar always starts with 0.

1       5
| \     |           vpar
2  3    6         0,1,1,3,0,5
   |
   4

Comparing forests lexicographically by vpar is the same as comparing lexicographically by Ldepths. So if an edge relation is a lex increase of Ldepths then it is also a lex increase of vpar (though the values in the arrays are not the same in general).

Option vertex_name_type => 'vpar_postorder' is vertex parent array with forest vertices labelled in post-order. The last vertex is the last root, so vpar_postorder always ends with 0.

4       6
| \     |        vpar_postorder
1  3    5         4,3,4,0,6,0
   |
   2

Weights

Option vertex_name_type => 'Lweights' gives a list of subtree sizes. This is the binary tree weights vector considered by Pallo ("Enumerating" below).

Each binary tree external vertex (left to right) is right-most of a sub-tree (the subtree to its left). The top of that sub-tree is found by going up until reaching a vertex (internal or external) which is a left child. The weight is the number of externals at and below there. An external which is already a left child is weight 1 (itself only). The first external is always a left child so Lweights start with 1. The last external is omitted (it would be N+1 always).

          1
      /       \              Lweights
   2            5           1,1,2,3, 1,2   (omit e7)
  / \          / \
e1   3        6   e7         Rweights
    / \      / \            3,1,1, 3,1,1   (omit e1)
   4   e4  e5   e6
  / \
e2   e3

Option vertex_name_type => 'Rweights' is similar. Each external vertex is left-most of a subtree (the subtree to its right). The subtree top is by going up until a right child vertex. The last external is always a right child so Rweights end with 1. The first external is omitted (it would always be N+1).

An equivalent definition is to take the internal vertices in-order and Lweight is the size of that vertex plus its left subtree (if any). Or Rweight is itself plus right subtree.

In terms of ordered forests, Lweight is the subtree size at and below each vertex in post-order (since binary tree in-order is forest post-order).

Comma

Option comma => "string" is the separator between quantities in the vertex names. The default is empty "" for balanced binary or "," comma for the others.

Terms are single digits for weights or vpar of N < 10, and depths of N <= 10. Omitting the comma by comma => '' is then unambiguous and might be preferred for compact viewing. Ambiguity at N=10 would be Catalan(10) = 16796 vertices which is big but possible.

Rotate

The default rel_type => 'rotate' is the Tamari lattice, conceived by Tamari as parenthesizations of N+1 objects and stepped by one application of the associative law, and hence also called an associahedron.

    Dov Tamari, "The Algebra of Bracketings and Their Enumeration", Nieuw Archief voor Wiskunde, Series 3, volume 10, 1962, pages 131-146.

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

In terms of binary trees, this is one "rotation", and hence also called a binary rotation graph (eg. Pallo). Rotation is the rearrangement commonly used for rebalancing a binary tree. (Or applying an associative law to operators in an expression parse tree.)

     x    (leftward)    y
    / \      -->       / \            binary tree "rotation",
   A   y              x   C          edge between vertices x,y
      / \            / \           A,B,C subtrees (possibly empty)
     B   C          A   B

1 A 0 1 B 0 C     1 1 A 0 B 0 C     A,B,C balanced substrings
  ^^^^^             ^^^^^              (possibly empty)

A right edge x-y can rotate to left, or a left edge can come from a right rotate, so each tree edge gives a graph edge and the graph is regular of degree N-1.

num edges = (N-1)/2*Catalan(N) or 0 if N=0
          = binomial(2N-1, N-2)
          = 0,0,1,5,21,84, ...   (A002054)
degree N-1 regular (in-degree + out-degree)

In terms of balanced binary, rotation moves a 1 to before the shortest non-empty balanced substring immediately preceding,

edge from    1aaaa0 1        where 1aaaa0 shortest balanced
      to     1 1aaaa0

Moving the 1 has the effect of shifting the 1A0 part up and right,

from      /\          to    /\  /\
     /\  /  \   -->        /  \/  \
  /\/  \/    \          /\/        \
  101100111000          101110011000
    ****1                 1****

Each 01 can rotate per the "from" form above, so number of successors is number of 01 pairs. Each 11 in the "to" form above can come from a rotate, so number of predecessors is number of 11 pairs.

In terms of ordered forest, rotation is a vertex move down to deeper level. A vertex y with preceding sibling x has that x and its subtree drop down to become the first child of y. y's other children B remain.

      x ... y ... further-C                   y ... further-C
      |     |                 (leftwards)     | \
subtree-A  further-B             -->          x .. further-B
                                              |
                                          subtree-A

In terms of Lweights, Pallo shows a rotate is one entry increasing by its smallest possible amount, which is adding the size of its immediately preceding sibling (drops to become first child). This is y gaining subtree size x under it. The post-order vertex sequence is unchanged. Pallo reaches the same as Tamari that this operation forms a lattice.

    J. M. Pallo, "Enumerating, Ranking and Unranking Binary Trees", The Computer Journal, volume 29, number 2, 1986, pages 171-175.

Taking Lweights as coordinates allows the graph to be drawn as an N-1 dimensional rectangular figure. The first Lweights entry is always 1 so can be ignored as a coordinate. Each edge is then forward along one axis. For N=4 in 3 dimensions the effect is good. Geyer draws N=4 and N=5 in this style. N=5 or more, in 2D projection at least, tends to become too busy to see much.

The undirected graph has a Hamiltonian path per Joan Lucas (simplified by Lucas, van Baronaigien, and Ruskey). And it has a Hamiltonian cycle per Wu and Wang (whose argument can be simplified by expanding as for a path and doing one zig-zag if Catalan(N-1) is odd).

The various rotate_... relation types below restrict to just some rotates so are edge subsets of full rotate.

Rotate Right or Left Arm

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

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

     -------> 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 ($graph->successorless_vertices) have no such returns to zero. They are "1 balanced(N-1) 0", and hence Catalan(N-1) many.

In terms of 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 "comb poset" of bracketings.

Option rel_type => '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 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.

Rotate First or Last

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

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

     -------> 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 (predecessorless) have 1 initial 1 and steps take them up to N 1s at the end (successorless). That end is unique, being all 1s at the start, 111000.

The number of vertices at each distance from the end a Catalan triangle row. The predecessorless are Catalan(N-1) which is the end of the triangle row.

Option rel_type => 'rotate_last' rotates at the last possible place only. The result is a tree ("rightmost") again per Pallo (above).

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

Rotate Empty

Option rel_type => 'rotate_Aempty' or 'rotate_Bempty' or 'rotate_Cempty' restrict to rotate where the respective "A", "B" or "C" part above is an empty subtree.

rotate_Aempty is in the manner of (believe),

    A. Bonnin and J.M. Pallo, "A Shortest Path Metric on Unlabelled Binary Trees", Pattern Recognition Letters, volume 13, 1992, pages 411-415.

In terms of balanced binary, the rotate "aaaa" part is empty so triplet 101 -> 110. Flip 01->10 is per "Flip" below, so the result here is edge intersection of rotate and flip, ie. those edges present in both.

edge from   101       rotate_Aempty
      to    110

     -------> 110010
    /                                  N => 3
101010                     111000      rel_type => "rotate_Aempty"
    \                        ^
     --> 101100 --> 110100 -/

Every 110 substring can be reached from a 101, so the only predecessorless is balanced binary without 110, which is 101010.

Every vertex with a 101 has a successor. This first 1 is a vertex without left but with right. Conversely without 101 is each 10 as 100 or at end of string. That means whenever absent left must also have absent right. This restriction is Motzkin trees so number of successorless

successorless = Motzkin(N-1) = 1,1,1,2,4,9,21,51,...  (A001006)

rotate_Cempty is empty C. This is isomorphic to empty A by considering binary trees in mirror image and rotate left edge to right.

In balanced binary, C-empty has 1 after the B subtree, so either 0 or end of string. Identifying places to rotate normally doesn't look at the length of B, but for C-empty must check what is after. For N=3, C-empty is identical to rotate_last tree, but bigger C-empty and A-empty are not trees.

edge from 1aaaa0 1bbbb0 [0 or end]     rotate_Cempty
      to  11aaaa0 bbbb0

rotate_Bempty is per Pallo ("Rotational" above) who calls it "central rotate" (and takes "y,B" together requiring them a single vertex).

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

In terms of Lweights, Pallo notes that B empty means the y vertex is weight 1 (nothing under) and the rotate increases it (when possible, and by smallest amount as usual for a rotate).

In balanced binary, B empty is a 0 after the rotate bit pattern, so rotate at each 010.

                      v-- must 0 after
edge from    1aaaa0 1 0                rotate_Bempty
      to     1 1aaaa0 0

The number of edges can be calculated by a recurrence summing over k vertices in the left subtree, n-k-1 in the right, multiplying rotates within the left by number of subtrees right, and vice versa, and new rotate at the root which is right subtree with empty left which is n-k-2. The result is

num edges = binomial(2N-2, N-2)
          = 0, 0, 1, 4, 15, 56, 210, 792, ...   (A001791)

Graph vertices without successor have nowhere an empty B. This means every tree vertex (y) with a right child also has a left child. This is the Motzkin restriction as per A-empty above. The rotate sends a tree to the corresponding form in mirror image, so vertices without predecessor are likewise. This mirror imaging also means the graph is isomorphic to its own edge reversal ($graph->transpose).

Dexter

Option rel_type => 'dexter' is a multi-step block shift of

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

Chapoton considers shifts (and rotates) going up and left, but here rotate is up and right and dexter here is taken the same. (The difference is whether to read left to right or right to left.) In terms of balanced binary,

from   (0 or start) 1aaaa0 111     one or more following 1s
 to                 111 1aaaa0

Dexter shift moves one or more of the 1s which are after 1aaaa0. This is one or more rotates at the same place.

The 1aaaa0 is restricted to be preceded by 0 or start of string, it cannot be preceded by 1. This means 1s are taken in a single bite. For example, three 1s are a step but not two 1s then further step remaining 1. When two are taken, the result is "11 1aaaa0 1" and 1aaaa0 is now preceded by a 1 so not eligible for a further shift.

Chapoton notes that all rotate_rightarm (see "Rotate Right or Left Arm" above) have the necessary 0 or start, so rotate_rightarm edges are a subset of dexter. When all the 1s are taken, the result is per split (see "Split" below), but split differs in also shifting across multiple blocks and it does not take non-maximal 1s.

In terms of binary trees, the restriction is rotate at an x which is a right child or the root. Multiple 1s are a chain of left edges down from y. The following example is two 1s y,z. The A subtree rotates to under z. Further rotate of 1A0 is disallowed because its 1 is x which is now a left child.

  t                     t
 / \     (leftwards)   / \
T   x      ------>    T   y              t   x     yz
   / \                   / \       from  1T0 1 A 0 11 B 0 C 0 D
  A   y                 z   D       to       1 11 A 0
     / \               / \
    z   D             x   C        x = right child (or root)
   / \               / \
  B  C              A   B

Successorless graph vertices are no block preceded by 0 and followed by 1. Per Chapoton, the number of these is the Motzkin numbers. The condition in the tree is any right edges must be under left child.

successorless = Motzkin(N-1) = 1,1,1,2,4,9,21,51,...  (A001006)

Predecessors are from each balanced binary 11. This is the 11 of "11aaaa0" in "to" above coming from a shift past the 1aaaa0. That shift is of the first 1, plus all preceding 1s. These 11 locations are the same as for rotate (each left edge), but coming from a different vertex when preceding 1s. The total number of edges is same, though dexter is not degree regular the way rotate is.

num edges = same as rotate
          = (N-1)/2*Catalan(N) = 0,0,1,5,21,84, ... (A002054)

Split

Option rel_type => 'split' is a graph edge where split of a set of siblings. This is the Kreweras lattice,

    G. Kreweras, "Sur les Partitions Non-Croisées d'Un Cycle", Discrete Mathematics, volume 1, number 4, 1972, pages 333-350.

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

Kreweras considers the lattice in terms of non-crossing partitions of the integers 1..N. A partition is integers 1..N put into one or more sets. Non-crossing means if sets have overlapping min to max ranges then one must be entirely within a gap between elements of the other, the way children fall between two siblings in a pre-order labelled forest. Non-crossing partitions are precisely the sets of siblings in ordered forests (with roots reckoned siblings of each other).

Graph edges are where one set in a partition splits into two sets to reach another partition. The set getting the first element remains. The other set is new and comprises consecutive elements of the original. They split out by dropping to deeper in the forest.

  1         8            1        8
  |\ \ \    |            |  \     |         pre-order forests
  2 3 5 6   9            2    6   9        (post-order similar)
    |   |                |\   |
    4   7                3 5  7
                         |
 siblings sets           4         split 2,3,5,6
[1,8] [2,3,5,6]                    by dropping 3,5 down
[4,7] [8] [9]                      [2,6] [3,5]

The graph start vertex is the ordered forest all singletons which is 1 set of siblings. A split gives 2 sets, and further split 3 sets, and so on until N sets which is every vertex alone in its siblings set (path-N down).

In balanced binary, split is a block of 1s moving to before one or more preceding balanced substrings.

edge from    1aa0 .. 1aa0 111       across one or more
      to     111 1aa0 .. 1aa0        preceding balanceds

The block of 1s is maximal, ie. all the 1s following a 0. This is all children moving down (moving only some would change the siblings below). Each 1aa0 is a further preceding sibling moving down with it to form the new sibling set.

The number of edges in the graph can be counted by some recurrences on forest N vertices, k roots, second root vertex c. Forest 2..c-1 is a sub-forest and remaining c..N has 1 fewer roots. In the balanced binary this is k many blocks and first size c. Multiplying count of splits in one part by number of the other part reaches

num edges = binomial(2N,N-2) = 0,1,6,28,120,495, ... (A002694)

Flip

Option rel_type => 'flip' is graph edge for a balanced binary flip 01 -> 10. This is the Stanley lattice, one of several given in

from 101100           /\  -->  /\/\          valley \/
 to  110100        /\/  \     /    \         flip up to /\ peak
      ^^

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

In terms of pre-order Ldepths, the step is where one entry increases by +1. Such an increase is possible (ie. goes to valid depths) when <= its preceding entry (and first entry depth 0 never increases).

These Ldepth increases mean the lattice is "graded" by total Ldepths (which is area under the mountain range). Ldepths run from start 0,0,0,0 to end 0,1,2,3 so path length start to end is sum of those terms which is triangular number N*(N-1)/2. Stanley leaves it as an exercise to show the number of different such paths (maximal chains) is, adapted to N numbering here,

                             binomial(N,2) !
max chains = --------------------------------------------------
           (2N-3) * (2N-5)^2 * (2N-7)^3 * ... * 3^(N-2) * 1^(N-1)

           = 1, 1, 1, 2, 16, 768, 292864, ...    (A005118)

Filling

Option rel_type => 'filling' is graph edges where balanced binary flips pairs 01 -> 10 per

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

edge from   ... 01 ... 01 ... 01 ...     all 01 pairs
      to    ... 10 ... 10 ... 10 ...

They show the starts ($graph->predecessorless_vertices) are balanced binary decomposable or containing 0011. Decomposable means can be broken into two balanced strings B1,B2, so there is some return to the zero line before the end. In N=3 shown above, starts are just the decomposables. The 0011 rule first applies in N=5 where 1110011000 is not decomposable but is a start because contains 0011.

Each vertex has just one filling destination so the result is a tree and ends at 11110000 which is the sole string with no 01s at all.

In terms of Ldepths, filling is +1 of all entries which are able to increase, meaning <= preceding entry. The places able to increase are determined before any increasing takes place.

Relation Direction

For a directed graph, edges are in the direction of the rules above. This is the default rel_direction => 'up'. Direction "down" is the opposite, the same as $graph->transpose. Direction "both" is edges both ways. An undirected graph has just one edge between vertices in all cases.

For balanced binary, the various rules are a lexicographic (and numeric) increase. The lattices go from global minimum 10101010 up to global maximum 11110000. Or in some relations other minima or maxima too.

balanced_postorder does some reversing so that the start becomes 11110000 and the end becomes 10101010. This is because vertex_name_type changes only the vertex name, not the object represented nor the relation rule. Direction "down" can be used if desired to put edges the other way. In the case of rotate, the rule in balanced_postorder and down becomes

edge from   0 1aaaa0       vertex_name_type => balanced_postorder
      to    1aaaa0 0       rel_direction => down

The 0 is a descent. Moving it to after the balanced following has the effect of shifting 1aaaa0 up and left. Various authors prefer this form, for example Bernardi and Bonichon. Balanced coding and rotate move opposite ways, so the choice is which one to prefer as the "bit first".

preorder  coding "1 left 0 right",  rotate "balanced 1"
postorder coding "left 1 right 0",  rotate "0 balanced"

The default here is to prefer pre-order and rotate in the direction which is a lex increase of that preorder.

Lattice Refinement

As noted above, split, rotate, and flip, all form lattices (partial ordered set algebras). They are successive refinements, meaning two elements comparable in one remain comparable in the next, and some new comparability added.

split --> rotate --> flip      lattice refinement

In directed graph terms, refinement means at a given vertex the reachable successors ($graph->all_successors($v)) expand so everything which was reachable remains so, and more becomes reachable too. The path length to reach something might increase. Reachable predecessors expand in the same way.

In terms of the relation rules on balanced binary, these refinements are simply that a split step can be built by one or more rotate, and a rotate can be built by one or more flip.

FUNCTIONS

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

The key/value parameters are

N            => integer, represented trees size
graph_maker  => subr(key=>value) constructor,
                 default Graph->new

rel_type     => string
  "rotate" (default),
  "rotate_first", "rotate_last",
  "rotate_Aempty", "rotate_Bempty", "rotate_Cempty",
  "rotate_rightarm", "rotate_leftarm"
  "dexter"
  "split",
  "flip", "filling"

rel_direction     => string "up" (default), "down", "both"

vertex_name_type  => string
  "balanced" (default), "balanced_postorder"
  "Ldepths", "Rdepths_postorder",
  "Ldepths_inorder","Rdepths_inorder","Bdepths_inorder",
  "Lweights", "Rweights",
  "vpar", "vpar_postorder"

comma          => string, default "," or empty ""

Other parameters are passed to the constructor, either the graph_maker coderef or Graph->new().

If the graph is directed (the default) then edges are only in the "successor" direction for the given rel_type.

FORMULAS

The current implementation uses arrays of balanced binary 0,1 internally, which is the default preorder balanced. These arrays are generated by iterating in the same way as Math::NumSeq::BalancedBinary (see docs there for notes). Generating by some recursion or even some Gray code stepping is possible (generating in any order is fine for the purposes here), but the iteration is simple enough.

A relation type examines and manipulates a balanced binary array to construct destinations. Conversions are made from the arrays to the chosen vertex_name_type. These conversions are one-pass over an array, possibly with a stack remembering pending output or depth. For conversions to postorder, in some cases it's helpful to go from end to start (of what is otherwise preorder).

HOUSE OF GRAPHS

House of Graphs entries for graphs here include

all rel_type
  1310   N=0 and N=1 singleton
  19655  N=2, path-2

rotate
  340    N=3, 5-cycle
  33547  N=4
  33549  N=5
  33551  N=6

rotate_rightarm = rotate_leftarm
  286    N=3, path-5
  33615  N=4
  33617  N=5
  33619  N=6

rotate_first
  286    N=3, path-5
  33563  N=4
  33565  N=5
  33567  N=6

rotate_last
  286    N=3, path-5
  33569  N=4
  33571  N=5
  33573  N=6

rotate_Aempty = rotate_Cempty
  286    N=3, path-5
  33607  N=4
  33609  N=5
  33611  N=6

rotate_Bempty
  286    N=3, path-5
  33601  N=4
  33603  N=5
  33605  N=6

dexter
  206    N=3, 4-cycle and leaf
  33621  N=4
  33623  N=5
  33625  N=6

flip
  206    N=3, 4-cycle and leaf
  33589  N=4
  33591  N=5
  33593  N=6

filling
  544    N=3, star-5
  33595  N=4
  33597  N=5
  33599  N=6

split
  264    N=3
  33557  N=4
  33559  N=5
  33561  N=6

OEIS

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

A000108    num vertices, Catalan numbers

rotate
  A002054    num edges, (n-1)/2*Catalan
  A000260    num intervals
  A027686    num paths start to end (lattice maximal chains)

rotate_rightarm = rotate_leftarm
  A002057    num edges, 4/(N+2) * binomial(2N-1, N-2)
  A009766    row widths, Catalan triangle

rotate_first
  A141364    num edges, Catalan-1
  A009766    row widths, Catalan triangle

rotate_Bempty
  A001791    num edges, binomial(2N-2,N-2)
  A001006    num predecessorless, Motzkin numbers
  A058987    num predecessorful, Catalan-Motzkin
  A001006    num successorful, Motzkin numbers
  A058987    num successorless, Catalan-Motzkin

dexter
  A002054    num edges, (n-1)/2*Catalan   (same as rotate)
  A000257    num intervals

split
  A002694    num edges, binomial(2N,N-2)
  A001764    num intervals
  A000272    num paths start to end (lattice maximal chains)

flip
  A002054    num edges, count DU, binomial(2N-1,N-2)
  A005700    num intervals
  A005118    num paths start to end (lattice maximal chains)

filling
  A086581    num predecessorful vertices, N>=2
  A071740    num predecessorless vertices, N>=2

In the above, "num intervals" means the number of pairs of vertices $u to $v where $v is reachable from $u. In a lattice, this means $u and $v are comparable ($u <= $v). $u reachable from $u itself is included (an empty path), so sum 1 + $graph->all_successors($u) over all $u.

SEE ALSO

Graph::Maker

Math::NumSeq::BalancedBinary, Math::NumSeq::Catalan

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

Copyright 2018, 2019, 2020, 2021 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/.