Ask Your Question

Generating a LabelledBinaryTree from its string representation

asked 2016-08-27 14:03:11 +0200

Peter Luschny gravatar image

updated 2016-08-29 14:58:35 +0200


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[., .], .]]" 

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2016-08-28 10:53:26 +0200

Maybeso83 gravatar image

updated 2016-08-28 20:04:44 +0200

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):
        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['


t = Permutation([1, 3, 2, 6, 5, 7, 4]).increasing_tree()
print t
s = '%s'%t
test = lbt_from_str(s)
print test
edit flag offensive delete link 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?

Peter Luschny gravatar imagePeter Luschny ( 2016-08-29 14:59:07 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools



Asked: 2016-08-27 14:03:11 +0200

Seen: 1,712 times

Last updated: Aug 29 '16