Roel Schroeven wrote:
>
> You'll have to modify your code so that it creates a tuple instead of a
> string.
It seems that doing it without using a string complicates matters, or at
least increases the line count. I tried it with a list, since you can't
build a tuple on the go since tuples are immutable, but that didn't work
out very well so I created a tree with nodes to store the branches:
class Tree(object):
class Node(object):
def __init__(self, linage, left=None, right=None):
self.linage = linage
self.left = left
self.right = right
def AsTuple(self):
if self.left and self.right:
return self.left.AsTuple(), self.right.AsTuple()
else:
return self.linage
def __init__(self, rootlinage):
self.rootnode = Tree.Node(rootlinage)
self.linagetonode = {rootlinage: self.rootnode}
def AddBranch(self, linage, newlinage):
node = self.linagetonode[linage]
left = Tree.Node(linage)
right = Tree.Node(newlinage)
node.left = left
node.right = right
self.linagetonode[linage] = left
self.linagetonode[newlinage] = right
def AsTuple(self):
return self.rootnode.AsTuple()
In this data structure the nodes are stored as a tree, but are also
accessible via the linage values. Branching is done by looking up the
node via the linage and creating appropriate left and right children.
Creating the tuple for printing the dendrogram can be done via simple
recursion.
I initialize the tree (both at the beginning and when restarting) by doing:
tree = Tree('0')
Branching becomes:
next_linage += 1
linages.append(next_linage)
print 'At ', time,' linage ', linages[i], 'evolved', next_linage
tree.AddBranch(str(linages[i]), str(next_linage))
num_linages += 1
if num_linages == 10: break
Printing the tree:
printDendrogram(tree.AsTuple())
The whole program:
# Thesis_ex_gen6.py
import random
# constants that control the simulation
MAX_LINAGES = 10
BRANCHING_PROBABILITY = 0.01
EXTINCTION_PROBABILITY = 0.01
def printDendrogram(T, sep=3):
"""Print dendrogram of a binary tree. Each tree node is
represented by a length-2 tuple.
routine written by David Eppstein from ActiveState Programers
Network Last Updated: 2002/07/13"""
def isPair(T):
return type(T) == tuple and len(T) == 2
def maxHeight(T):
if isPair(T):
h = max(maxHeight(T[0]), maxHeight(T[1]))
else:
h = len(str(T))
return h + sep
activeLevels = {}
def traverse(T, h, isFirst):
if isPair(T):
traverse(T[0], h-sep, 1)
s = [' ']*(h-sep)
s.append('|')
else:
s = list(str(T))
s.append(' ')
while len(s) < h:
s.append('-')
if (isFirst >= 0):
s.append('+')
if isFirst:
activeLevels[h] = 1
else:
del activeLevels[h]
A = list(activeLevels)
A.sort()
for L in A:
if len(s) < L:
while len(s) < L:
s.append(' ')
s.append('|')
print ''.join(s)
if isPair(T):
traverse(T[1], h-sep, 0)
traverse(T, maxHeight(T), -1)
if __name__ == '__main__':
for x in range(1):
print '\n','run ', x+1, '\n'
class Tree(object):
class Node(object):
def __init__(self, linage, left=None, right=None):
self.linage = linage
self.left = left
self.right = right
def AsTuple(self):
if self.left and self.right:
return self.left.AsTuple(), self.right.AsTuple()
else:
return self.linage
def __init__(self, rootlinage):
self.rootnode = Tree.Node(rootlinage)
self.linagetonode = {rootlinage: self.rootnode}
def AddBranch(self, linage, newlinage):
node = self.linagetonode[linage]
left = Tree.Node(linage)
right = Tree.Node(newlinage)
node.left = left
node.right = right
self.linagetonode[linage] = left
self.linagetonode[newlinage] = right
def AsTuple(self):
return self.rootnode.AsTuple()
next_linage = 0 # next counter initalized
linages = [0] # linages initalized
num_linages = 1 # total linage counter initalized
time = 0 # time initalized
tree = Tree('0')
while (len(linages) != 0) and (num_linages < MAX_LINAGES):
time += 1
"With BRANCHING_PROBABILITY creates a new linage and prints
information"
i = 0
while i < len(linages):
if random.random() < BRANCHING_PROBABILITY:
next_linage += 1
linages.append(next_linage)
print 'At ', time,' linage ', linages[i], 'evolved',
next_linage
tree.AddBranch(str(linages[i]), str(next_linage))
num_linages += 1
if num_linages == 10: break
i += 1
"With EXTINCTION_PROBABILITY kill a linage and print
information"
j = 0
while j < len(linages):
if random.random() < EXTINCTION_PROBABILITY:
print 'At ', time,' linage ', linages[j], 'died '
del linages[j]
if len(linages) == 0:
"restarts if fewer that 10 linages evolved"
print '\n restart \n'
next_linage = 0 # next counter initalized
linages = [0] # linages initalized
num_linages = 1 # total linage counter initalized
time = 0 # time initalized
tree = Tree('0')
j += 1
print tree.AsTuple()
printDendrogram(tree.AsTuple())
--
If I have been able to see further, it was only because I stood
on the shoulders of giants. -- Isaac Newton
Roel Schroeven
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
