- Help with Python: Prufer array to tree array with graphics
- 22 Oct 2012 02:45:46 pm
- Last edited by 0rac343 on 26 Oct 2012 11:45:27 am; edited 1 time in total
So I was working on a python script to take a prufer array and generate an output nested array that contains the vertice pairings of the tree.
here is the current code:
Code:
And this should successfully generate a tree array when given any random prufer array.
But now I need to use the turtle function of python to draw the actual tree and possibly label them (?) And I really suck at making the turtles do anything.
tl;dr I need help drawing the trees generated by the above script
EDIT:
I have the graphics part down, now I need to write a script for taking a nested array that contains the vertice pairings of a tree to convert back to a prufer code array.
The input should be [outer vertex, inner vertex] and should be ordered ascending order with respect to the outer vertice in each nested unit. Any ideas?
here is the current code:
Code:
def prufer_to_tree(array):
tree_list = []
n = range(0, len(array)+2)
# the degree of each vertex is how many times it appears in the array
# since each node is numbered randomly from the original tree
# in the array sequence
deg = [1]*len(n)
for i in array: deg[i] += 1
# for each vertex labeled i in array, find the first vertex(ices)
# j with degree 1 and add the edge (j, i) (from vertex j to vertex i) to the tree
for i in array:
for j in n:
if deg[j] == 1:
tree_list.append((i,j))
# decrement the degrees of i and j
deg[i] -= 1
deg[j] -= 1
break
output = [x for x in n if deg[x] == 1]
tree_list.append((output[0],output[1]))
# Also remember that the output will have '0' in it
# This is not an error rather, it represents the first vertex
# Output will occur because python starts index arrays at '0' rather than '1'
# Output is nested list with
return tree_list
And this should successfully generate a tree array when given any random prufer array.
But now I need to use the turtle function of python to draw the actual tree and possibly label them (?) And I really suck at making the turtles do anything.
tl;dr I need help drawing the trees generated by the above script
EDIT:
I have the graphics part down, now I need to write a script for taking a nested array that contains the vertice pairings of a tree to convert back to a prufer code array.
The input should be [outer vertex, inner vertex] and should be ordered ascending order with respect to the outer vertice in each nested unit. Any ideas?
