Graph::Maker::Catalans - create Tamari lattice and other Catalan object graphs
use Graph::Maker::Catalans; $graph = Graph::Maker->new ('Catalans', N => 4);
Graph::Maker::Catalans creates Graph.pm graphs where each vertex represents a "Catalan object", meaning one of
Graph::Maker::Catalans
Graph.pm
balanced binary (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 combinatorial objects enumerated 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 11 vertex name types.
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.
vertex_name_type
The 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.
vertex_name_type => 'balanced'
/\ /\/ \ /\ 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
vertex_name_type => 'balanced_postorder'
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.
Option vertex_name_type => 'Ldepths' is left depth of each vertex in pre-order. Left depth is how many left steps down to the vertex. The example above is
vertex_name_type => 'Ldepths'
0,1,1,2,0,1 Ldepths
In terms of balanced binary, Ldepths is at each 1-bit 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 one-to-one 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, this is at each 0 how many unclosed 0s are after it. Or equivalently, how many unclosed 1s precede, with the 0 itself included as a closing.
vertex_name_type => 'Ldepths_inorder'
In terms of ordered forest, in-order binary tree traversal is postorder forest traversal. So Ldepths_inorder is forest depths postorder.
Ldepths_inorder
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 the "distance" representation by Makinen. In terms of ordered forest, right depth is a horizontal position (how many preceding siblings, plus parent how many preceding siblings, etc).
vertex_name_type => 'Rdepths_inorder'
Option Bdepths_inorder is all steps down, so Ldepths_inorder plus Rdepths_inorder.
Bdepths_inorder
Rdepths_inorder
Option vertex_name_type => 'Rdepths_postorder' is right depths of the binary tree traversed post-order.
vertex_name_type => 'Rdepths_postorder'
The above are only one pre and one post. The omitted pre R,B and post L,B do not uniquely identify their tree object, ie. multiple trees have the same resulting vector.
Option vertex_name_type => 'vpar' gives 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.
vertex_name_type => 'vpar'
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 when one of the edge relations is a lex increase of Ldepths it is also a lex increase of vpar (though the values in the arrays are not the same in general).
vpar
Ldepths
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.
vertex_name_type => 'vpar_postorder'
vpar_postorder
4 6 | \ | vpar_postorder 1 3 5 4,3,4,0,6,0 | 2
Option vertex_name_type => 'Lweights' gives a list of subtree sizes. This is the of binary tree weights vector considered by Pallo ("Enumerating" below).
vertex_name_type => 'Lweights'
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 always be N+1).
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 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).
vertex_name_type => 'Rweights'
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).
Option comma => "string" is the separator between quantities in the vertex names. The default is empty "" for balanced binary or "," comma for the others.
comma => "string"
Terms are single digits for weights and vpar N < 10 and depths N <= 10. Omitting the comma by comma => "" is then unambiguous and might be preferred for compact viewing. N=10 ambiguity would be at Catalan(10) = 16796 many vertices which is big but possible.
comma => ""
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.
rel_type => 'rotate'
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, hence 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 rotates as in the "from" above, so number of successors is number of 01 pairs. Each 11 as in the "to" 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 drop down to become child of y. y's other children B and further siblings C 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 sequence is unchanged. Pallo reaches the same as Tamari that the result is a lattice.
Lweights
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, but more, in 2D projection at least, tends to become too busy to see much. Geyer draws some in this style.
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_...
rotate
Option rel_type => 'rotate_rightarm' restricts to rotates of edges on the right arm of the binary tree, in the manner of
rel_type => 'rotate_rightarm'
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.
$graph->successorless_vertices
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.
Sebastian A. Csar, Rik Sengupta, and Warut Suksompong. "On a Subposet of the Tamari Lattice.", volume 31, number 3, October 2013, pages 337-363. http://dx.doi.org/10.1007/s11083-013-9305-5
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
rel_type => 'rotate_leftarm'
rotate_rightarm
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.
Option rel_type => 'rotate_first' restricts to rotate only at the first possible place. This result is a tree ("leftmost") per,
rel_type => 'rotate_first'
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 (the left arm vertices). Each first rotate moves the first non-initial-1 to become part of the initial 1s. The start vertices (predecessorless) have 1 initial 1 and steps take them to N 1s at the end (successorless).
The number of vertices at each distance from the end is the Catalan triangle. 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).
rel_type => 'rotate_last'
110010 -------_ v N => 3 101010 111000 rel_type => "rotate_last" \ ^ --> 101100 --> 110100 -/
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.
rel_type => 'rotate_Aempty'
'rotate_Bempty'
'rotate_Cempty'
rotate_Aempty is in the manner of (believe),
rotate_Aempty
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.
flip
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.
rotate_Cempty
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.
rotate_last
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).
rotate_Bempty
-------> 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.
edge from 1aaaa0 1 0 rotate_Bempty to 1 1aaaa0 0 ^-- must 0 after
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).
$graph->transpose
Option rel_type => 'dexter' is a multi-step block shift of
rel_type => 'dexter'
F. Chapoton, "Some Properties of a New Partial Order on Dyck Paths", September 2018. https://hal.archives-ouvertes.fr/hal-01878792, https://arxiv.org/abs/1809.10981
-------> 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.
dexter
split
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.
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)
Option rel_type => 'split' is graph edge where split of a set of siblings. This is the Kreweras lattice,
rel_type => 'split'
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. 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 siblings in a pre-order labelled forest. Non-crossing sets are all and only the sets of siblings of 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 consecutive elements and 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 starting vertex is 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 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 N vertices, k roots, second root vertex c. 2..c-1 is a sub-forest and c..N is 1 fewer roots. In the balanced binary this is k many blocks with 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)
Option rel_type => 'flip' is graph edge for a balanced binary flip 01 -> 10. This is the Stanley lattice, one of various given in
rel_type => 'flip'
Richard P. Stanley, "The Fibonacci Lattice", Fibonacci Quarterly, volume 13, number 3, October 1975, pages 215-232, lattice J(S(k)) on page 222. https://fq.math.ca/13-3.html, https://fq.math.ca/Scanned/13-3/stanley.pdf
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)
Option rel_type => 'filling' is graph edges where balanced binary flips pairs 01 -> 10 per
rel_type => 'filling'
A. Sapounakis, I. Tasoulas, P. Tsikouras, "On the Dominance Partial Ordering of Dyck Paths", Journal of Integer Sequences, volume 9, 2006, article 06.2.5. https://cs.uwaterloo.ca/journals/JIS/VOL9/Tsikouras/tsikouras67.html
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.
$graph->predecessorless_vertices
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.
filling
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.
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 is just one edge between vertices in all cases.
rel_direction => 'up'
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
balanced_postorder
down
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.
As variously 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 extra 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 possibly more reachable too. The path length to reach something may increase. Reachable predecessors expand in the same way.
$graph->all_successors($v)
In terms of the relation rules on balanced binary, these extensions 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.
$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().
graph_maker
Graph->new()
If the graph is directed (the default) then edges are only in the "successor" direction for the given rel_type.
rel_type
The current implementation uses arrays of balanced binary 0,1 internally, being the default preorder balanced. The arrays are generated iteratively in the same way as Math::NumSeq::BalancedBinary (see docs there for notes). Some recursion or even some Gray code stepping is possible (and which would be fine since no particular order is needed), but the iteration is simple enough.
balanced
A relation type examines and manipulates an array to construct destinations. Conversions are made from the arrays to the chosen vertex_name_type. These are one-pass over an array, possibly with a stack remembering pending output or depth. For postorder output in some cases it's helpful to go from end to start (of what is otherwise preorder).
House of Graphs entries for graphs here include
https://hog.grinvin.org/ViewGraphInfo.action?id=1310 etc
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
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this tree include
http://oeis.org/A000108 (etc)
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.
$u <= $v
1 + $graph->all_successors($u)
Graph::Maker
Math::NumSeq::BalancedBinary, Math::NumSeq::Catalan
Copyright 2018, 2019 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/.
To install Graph::Maker::Other, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Graph::Maker::Other
CPAN shell
perl -MCPAN -e shell install Graph::Maker::Other
For more information on module installation, please visit the detailed CPAN module installation guide.