# Generating a LabelledBinaryTree from its string representation

Consider

t = Permutation([1, 3, 2]).increasing_tree()
print t
print t.parent()


This gives

1[., 2[3[., .], .]]
Labelled binary trees


Conversely, I would like to generate a labelled binary tree from its string representation.

s = "1[., 2[3[., .], .]]"
LabelledBinaryTree(s)


This gives

ValueError: malformed string


How do I have to proceed?

EDIT: I will turn now my question into a feature request:

Make all trees reconstructable by their string representation!


This would be a great help for developing and testing one's code. Below Maybeso83 demonstrates how this can be done for labelled binary trees.

edit retag close merge delete

Sort by ยป oldest newest most voted

Ironically, the LabelledBinaryTree() command only lets you label the root. But you can apply a canonical labeling and then map those labels to the desired ones.

import re
words = re.compile('\w+')

# keep int labels as ints
def safeInt(word):
try:
return Integer(word)
except TypeError:
return word

# labelled binary tree from string
def lbt_from_str(lbstr):
blank = words.sub('', lbstr)
work = LabelledBinaryTree(blank).canonical_labelling()
wstr = '%s'%work
canon = [Integer(w) for w in words.findall(wstr)]
labels = [safeInt(w) for w in words.findall(lbstr)]
fixit = dict((canon[i], labels[i]) for i in range(len(canon)))
return work.map_labels(lambda z: fixit[z])
# end lbt_from_str


This doesn't check if the string has a valid structure, and it expects all nodes to have labels.

You could replace ' [' with 'None['

Testing:

t = Permutation([1, 3, 2, 6, 5, 7, 4]).increasing_tree()
print t
show(t)
s = '%s'%t
test = lbt_from_str(s)
print test
show(test)

more

Thank you Maybeso83, looks good to me! And I like the replacement "None[] -> ." in the string format. Perhaps you can add your solution to SageMath?

( 2016-08-29 07:59:07 -0500 )edit