Plane trees

Plane trees.

Generation of plane trees

This file contains generators for level sequences of

• rooted (free) trees

• (free) trees

• rooted plane trees

• plane trees

See [BeyHed80], [RichOdlMcKWri86] and [Nak02] for algorithms.

surface_dynamics.misc.plane_tree.admissible_plane_tree_iterator(a, verbose=False)

Plane tree for separatrix diagram of hyperelliptic strata. Return triple (t,n,l) where t is a tree, n its number of nodes and l its number of leaves.

A plane tree with n nodes and l leaves is a-admissible if it satisfies n <= a and 2n-l < a

EXAMPLES:

sage: from surface_dynamics.misc.plane_tree import admissible_plane_tree_iterator
sage: for t,n,l in admissible_plane_tree_iterator(5): print("%s\n%s %s" %(t,n,l))
[0, 1, 2, 2, 1, 0]
4 3
[0, 1, 2, 1, 0]
3 2
[0, 1, 1, 1, 0]
3 3
[0, 1, 1, 1, 1, 0]
4 4
[0, 1, 1, 1, 1, 1, 0]
5 5

surface_dynamics.misc.plane_tree.cmp_halves(t, i=None)

Compare the subtrees [2:i] and [i:].

Used in the case of a central edge in the tree.

surface_dynamics.misc.plane_tree.cmp_subtree(t1, d1, t2, d2)

surface_dynamics.misc.plane_tree.half_turn(t, i=None)

Half turn of canonical form of a tree t which has an odd diameter.

INPUT:

• s - position of 1 in t

• i - the guy of depth m-1 as an index in s

EXAMPLES:

sage: from surface_dynamics.misc.plane_tree import half_turn

sage: half_turn([0,1,2,2,2,1])
[0, 1, 2, 1, 1, 1]
sage: half_turn([0,1,2,1,1,1])
[0, 1, 2, 2, 2, 1]

sage: half_turn([0,1,2,3,2,1,1,2,1])
[0, 1, 2, 2, 3, 2, 1, 2, 1]
sage: half_turn([0,1,2,2,3,2,1,2,1])
[0, 1, 2, 3, 2, 1, 1, 2, 1]

surface_dynamics.misc.plane_tree.is_lyndon(t, s=None, d=None, verbose=False)

Returns Lyndon -> True periodic -> period otherwise -> False

ALGORITHM

Lothaire, Combinatorics on words

INPUT:

• t - the tree

• s - the positions of 1 in t (limit of subtrees)

• d - the depths of subtrees

EXAMPLES:

sage: from surface_dynamics.misc.plane_tree import is_lyndon

sage: is_lyndon([1,2,3,3,1,2])
True
sage: is_lyndon([1,2,3,2,3,4,1,2,1,2,3,4])
False

sage: is_lyndon([1,1,2,1,2])
False
sage: is_lyndon([1,2,1,1,2])
False
sage: is_lyndon([1,2,1,2,1])
True

sage: is_lyndon([1,1,2,3,2,1,2,3,2,1,2,3,2])
False
sage: is_lyndon([1,2,3,2,1,1,2,3,2,1,2,3,2])
False
sage: is_lyndon([1,2,3,2,1,2,3,2,1,1,2,3,2])
False
sage: is_lyndon([1,2,3,2,1,2,3,2,1,2,3,2,1])
True

sage: is_lyndon([1,2,1,2])
1

sage: is_lyndon([1,2,3,1,2,1,2,3,1,2]) # lyndon periodic
2
sage: is_lyndon([1,2,1,2,3,1,2,1,2,3]) # not lyndon periodic
False

surface_dynamics.misc.plane_tree.rooted_plane_tree_iterator(nmin, nmax=None, verbose=False)

Iterator through rooted plane trees with at least nmin and at most nmax vertices. If nmax is not furnished then it is automatically set to nmin.

The output are list which corresponds to level sequences. The algorithm, which corresponds to a depth first search in a tree of trees is due to Nakano [Nak02].

EXAMPLES:

sage: from surface_dynamics.misc.plane_tree import rooted_plane_tree_iterator

sage: for t in rooted_plane_tree_iterator(4): print(t)
[0, 1, 2, 3]
[0, 1, 2, 2]
[0, 1, 2, 1]
[0, 1, 1, 2]
[0, 1, 1, 1]
sage: for t in rooted_plane_tree_iterator(1,3): print(t)
[0]
[0, 1]
[0, 1, 2]
[0, 1, 1]

surface_dynamics.misc.plane_tree.rooted_tree_iterator(n, verbose=False)

Iterator through regular level sequences of rooted trees. (only works for n >= 3)

EXAMPLES:

sage: from surface_dynamics.misc.plane_tree import rooted_tree_iterator
sage: for t in rooted_tree_iterator(4): print(t)
[0, 1, 2, 3]
[0, 1, 2, 2]
[0, 1, 2, 1]
[0, 1, 1, 1]
sage: for t in rooted_tree_iterator(5): print(t)
[0, 1, 2, 3, 4]
[0, 1, 2, 3, 3]
[0, 1, 2, 3, 2]
[0, 1, 2, 3, 1]
[0, 1, 2, 2, 2]
[0, 1, 2, 2, 1]
[0, 1, 2, 1, 2]
[0, 1, 2, 1, 1]
[0, 1, 1, 1, 1]

sage: for t in rooted_tree_iterator(5,verbose=True): pass
  p =    4
  prev = [0, 1, 2, 3, 4]
  save = [0, 0, 0, 0, 0]
[0, 1, 2, 3, 4]
  p =    4
  prev = [0, 1, 2, 3, 4]
  save = [0, 0, 0, 0, 0]
[0, 1, 2, 3, 3]
  p =    4
  prev = [0, 1, 2, 3, 4]
  save = [0, 0, 0, 0, 0]
[0, 1, 2, 3, 2]
  p =    3
  prev = [0, 1, 2, 0, 4]
  save = [0, 0, 0, 0, 0]
[0, 1, 2, 3, 1]
  p =    4
  prev = [0, 1, 3, 0, 4]
  save = [0, 0, 0, 2, 0]
[0, 1, 2, 2, 2]
  p =    3
  prev = [0, 1, 2, 0, 4]
  save = [0, 0, 0, 2, 0]
[0, 1, 2, 2, 1]
  p =    4
  prev = [0, 3, 2, 0, 4]
  save = [0, 0, 0, 1, 0]
[0, 1, 2, 1, 2]
  p =    2
  prev = [0, 1, 0, 0, 4]
  save = [0, 0, 0, 1, 0]
[0, 1, 2, 1, 1]
  p =    0
  prev = [0, 0, 0, 0, 4]
  save = [0, 0, 0, 1, 0]
[0, 1, 1, 1, 1]

surface_dynamics.misc.plane_tree.unrooted_plane_tree_iterator(nmin, nmax=None, verbose=False, check=False)

Iterator through plane trees with at most nmax vertices. A representative of each equivalence class of rooted tree is returned. The order is decreasing among level sequences.

One can choose a canonical representative by choosing either the middle vertex as a root (and the maximal cyclic order among subtrees) or the middle edge as the left-most edge (and we have to check between two).

Sloane’s A002995 1, 1, 1, 1, 2, 3, 6, 14, 34, 95, 280, 854, 2694, 8714, 28640, 95640, 323396, 1105335, 3813798, 13269146

TODO:

one more restriction for go down: if the max depth is attained only at first position and there is not enough available vertices to go deeply enough.

EXAMPLES:

sage: from surface_dynamics.misc.plane_tree import unrooted_plane_tree_iterator
sage: for t in unrooted_plane_tree_iterator(4): print(t)
[0, 1, 2, 1]
[0, 1, 1, 1]
sage: for t in unrooted_plane_tree_iterator(5): print(t)
[0, 1, 2, 2, 1]
[0, 1, 2, 1, 2]
[0, 1, 1, 1, 1]
sage: for t in unrooted_plane_tree_iterator(6): print(t)
[0, 1, 2, 3, 1, 2]
[0, 1, 2, 2, 2, 1]
[0, 1, 2, 2, 1, 2]
[0, 1, 2, 2, 1, 1]
[0, 1, 2, 1, 2, 1]
[0, 1, 1, 1, 1, 1]

sage: for t in unrooted_plane_tree_iterator(1,5): print(t)
[0]
[0, 1]
[0, 1, 2, 2, 1]
[0, 1, 2, 1]
[0, 1, 2, 1, 2]
[0, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1, 1]

sage: [sum(1 for _ in unrooted_plane_tree_iterator(i)) for i in range(1,13)]
[1, 1, 1, 2, 3, 6, 14, 34, 95, 280, 854, 2694]