Ask Your Question
1

Generating a LabelledBinaryTree from its string representation

asked 2016-08-27 07:03:11 -0500

Peter Luschny gravatar image

updated 2016-08-29 07:58:35 -0500

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

1 answer

Sort by ยป oldest newest most voted
1

answered 2016-08-28 03:53:26 -0500

Maybeso83 gravatar image

updated 2016-08-28 13:04:44 -0500

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)
edit flag offensive delete link more

Comments

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 07:59:07 -0500 )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

2 followers

Stats

Asked: 2016-08-27 07:03:11 -0500

Seen: 77 times

Last updated: Aug 29 '16