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", meaning one of
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 onetoone 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.
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
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.
/\
/\/ \ /\ 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 preorder 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, preorder
/ \ 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 inorder bit coding because left,1,right is merely 0101010 for every tree.
Depths
Option vertex_name_type => 'Ldepths'
is left depth of each vertex in preorder. Left depth is how many left steps down to the vertex. The example above is
0,1,1,2,0,1 Ldepths
In terms of balanced binary, Ldepths is at each 1bit 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 onetoone 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
/ \  \  preorder
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 inorder. 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.
In terms of ordered forest, inorder 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 inorder. 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).
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 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.
Vpar
Option vertex_name_type => 'vpar'
gives vertex parent array of the ordered forest in preorder. 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 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).
Option vertex_name_type => 'vpar_postorder'
is vertex parent array with forest vertices labelled in postorder. 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 of binary tree weights vector considered by Pallo ("Enumerating" below).
Each binary tree external vertex (left to right) is rightmost of a subtree (the subtree to its left). The top of that subtree 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 leftmost 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).
An equivalent definition is to take the internal vertices inorder 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 postorder (since binary tree inorder is forest postorder).
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 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.
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 131146.
> 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 xy can rotate to left, or a left edge can come from a right rotate, hence the graph is regular of degree N1.
num edges = (N1)/2*Catalan(N) or 0 if N=0
= binomial(2N1, N2)
= 0,0,1,5,21,84, ... (A002054)
degree N1 regular (indegree + outdegree)
In terms of balanced binary, rotation moves a 1 to before the shortest nonempty 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 ... furtherC y ... furtherC
  (leftwards) 
subtreeA furtherB > x ... furtherB

subtreeA
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 postorder sequence is unchanged. Pallo reaches the same as Tamari that the result is a lattice.
J. M. Pallo, "Enumerating, Ranking and Unranking Binary Trees", The Computer Journal, volume 29, number 2, 1986, pages 171175.
Taking Lweights
as coordinates allows the graph to be drawn as an N1 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 zigzag if Catalan(N1) 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, "RightArm Rotation Distance Between Binary Trees", Information Processing Letters, volume 87, number 4, 2003, pages 173177.
> 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 rightmost 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(N1) 0", and hence Catalan(N1) 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 nonzeros 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 337363. http://dx.doi.org/10.1007/s1108301393055
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 799810.
> 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 noninitial1 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(N1) 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 411415.
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(N1) = 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, Cempty 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 Cempty must check what is after. For N=3, Cempty is identical to rotate_last
tree, but bigger Cempty and Aempty 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.
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, nk1 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 nk2. The result is
num edges = binomial(2N2, N2)
= 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 Aempty 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 multistep block shift of
F. Chapoton, "Some Properties of a New Partial Order on Dyck Paths", September 2018. https://hal.archivesouvertes.fr/hal01878792, 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 nonmaximal 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(N1) = 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
= (N1)/2*Catalan(N) = 0,0,1,5,21,84, ... (A002054)
Split
Option rel_type => 'split'
is graph edge where split of a set of siblings. This is the Kreweras lattice,
G. Kreweras, "Sur les Partitions NonCroisées d'Un Cycle", Discrete Mathematics, volume 1, number 4, 1972, pages 333350.
> 101100 _ N => 3
/ v rel_type => "split"
101010 > 110010 > 111000
\ ^
> 110100 /
Kreweras considers the lattice in terms of noncrossing partitions of the integers 1..N. Noncrossing 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 preorder labelled forest. Noncrossing 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
\ \ \   \  preorder forests
2 3 5 6 9 2 6 9 (postorder 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 (pathN 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..c1 is a subforest 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,N2) = 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 various given in
Richard P. Stanley, "The Fibonacci Lattice", Fibonacci Quarterly, volume 13, number 3, October 1975, pages 215232, lattice J(S(k)) on page 222. https://fq.math.ca/133.html, https://fq.math.ca/Scanned/133/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 preorder 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*(N1)/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 = 
(2N3) * (2N5)^2 * (2N7)^3 * ... * 3^(N2) * 1^(N1)
= 1, 1, 1, 2, 16, 768, 292864, ... (A005118)
Filling
Option rel_type => 'filling'
is graph edges where balanced binary flips pairs 01 > 10 per
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.
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 is 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 preorder and rotate in the direction which is a lex increase of that preorder.
Lattice Refinement
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.
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
.
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 orGraph>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, 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.
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 onepass 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
House of Graphs entries for graphs here include
all rel_type
1310 N=0 and N=1 singleton
19655 N=2, path2
rotate
340 N=3, 5cycle
33547 N=4
33549 N=5
33551 N=6
rotate_rightarm = rotate_leftarm
286 N=3, path5
33615 N=4
33617 N=5
33619 N=6
rotate_first
286 N=3, path5
33563 N=4
33565 N=5
33567 N=6
rotate_last
286 N=3, path5
33569 N=4
33571 N=5
33573 N=6
rotate_Aempty = rotate_Cempty
286 N=3, path5
33607 N=4
33609 N=5
33611 N=6
rotate_Bempty
286 N=3, path5
33601 N=4
33603 N=5
33605 N=6
dexter
206 N=3, 4cycle and leaf
33621 N=4
33623 N=5
33625 N=6
flip
206 N=3, 4cycle and leaf
33589 N=4
33591 N=5
33593 N=6
filling
544 N=3, star5
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
http://oeis.org/A000108 (etc)
A000108 num vertices, Catalan numbers
rotate
A002054 num edges, (n1)/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(2N1, N2)
A009766 row widths, Catalan triangle
rotate_first
A141364 num edges, Catalan1
A009766 row widths, Catalan triangle
rotate_Bempty
A001791 num edges, binomial(2N2,N2)
A001006 num predecessorless, Motzkin numbers
A058987 num predecessorful, CatalanMotzkin
A001006 num successorful, Motzkin numbers
A058987 num successorless, CatalanMotzkin
dexter
A002054 num edges, (n1)/2*Catalan (same as rotate)
A000257 num intervals
split
A002694 num edges, binomial(2N,N2)
A001764 num intervals
A000272 num paths start to end (lattice maximal chains)
flip
A002054 num edges, count DU, binomial(2N1,N2)
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
Math::NumSeq::BalancedBinary, Math::NumSeq::Catalan
LICENSE
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/.