Index: mds-and-trees/tree-genealogy.py
===================================================================
--- mds-and-trees/tree-genealogy.py (revision 623)
+++ mds-and-trees/tree-genealogy.py (revision 624)
@@ -1,463 +1,657 @@
-# Draws a genealogical tree (generates a SVG file) based on parent-child relationship information.
-# Supports files generated by Framsticks experiments.
-
import json
+import math
import random
-import math
import argparse
-import time as ttime
-
-TIME = "" # BIRTHS / GENERATIONAL / REAL
-BALANCE = "" # MIN / DENSITY
-
-DOT_STYLE = "" # NONE / NORMAL / CLEAR
-
-JITTER = "" #
-
-# ------SVG---------
-svg_file = 0
-
-svg_line_style = 'stroke="rgb(90%,10%,16%)" stroke-width="1" stroke-opacity="0.7"'
-svg_mutation_line_style = 'stroke-width="1"'
-svg_crossover_line_style = 'stroke-width="1"'
-svg_spine_line_style = 'stroke="rgb(0%,90%,40%)" stroke-width="2" stroke-opacity="1"'
-svg_scale_line_style = 'stroke="black" stroke-width="0.5" stroke-opacity="1" stroke-dasharray="5, 5"'
-
-svg_dot_style = 'r="2" stroke="black" stroke-width="0.2" fill="red"'
-svg_clear_dot_style = 'r="2" stroke="black" stroke-width="0.4" fill="none"'
-svg_spine_dot_style = 'r="1" stroke="black" stroke-width="0.2" fill="rgb(50%,50%,100%)"'
-
-svg_scale_text_style = 'style="font-family: Arial; font-size: 12; fill: #000000;"'
-
-def hex_to_style(hex):
- default_style = ' stroke="black" stroke-opacity="0.5" '
-
- if hex[0] == "#":
- hex = hex[1:]
-
- if len(hex) == 6 or len(hex) == 8:
- try:
- int(hex, 16)
- except:
- print("Invalid characters in the color's hex #" + hex + "! Assuming black.")
- return default_style
- red = 100*int(hex[0:2], 16)/255
- green = 100*int(hex[2:4], 16)/255
- blue = 100*int(hex[4:6], 16)/255
- opacity = 0.5
- if len(hex) == 8:
- opacity = int(hex[6:8], 16)/255
- return ' stroke="rgb(' +str(red)+ '%,' +str(green)+ '%,' +str(blue)+ '%)" stroke-opacity="' +str(opacity)+ '" '
- else:
- print("Invalid number of digits in the color's hex #" + hex + "! Assuming black.")
- return default_style
-
-def svg_add_line(from_pos, to_pos, style=svg_line_style):
- svg_file.write('')
-
-def svg_add_text(text, pos, anchor, style=svg_scale_text_style):
- svg_file.write('' + text + '')
-
-def svg_add_dot(pos, style=svg_dot_style):
- svg_file.write('')
-
-def svg_generate_line_style(percent):
- # hotdog
- from_col = [100, 70, 0]
- to_col = [60, 0, 0]
- # lava
- # from_col = [100, 80, 0]
- # to_col = [100, 0, 0]
- # neon
- # from_col = [30, 200, 255]
- # to_col = [240, 0, 220]
-
- from_opa = 0.2
- to_opa = 1.0
- from_stroke = 1
- to_stroke = 3
-
- opa = from_opa*(1-percent) + to_opa*percent
- stroke = from_stroke*(1-percent) + to_stroke*percent
-
- percent = 1 - ((1-percent)**20)
-
- return 'stroke="rgb(' + str(from_col[0]*(1-percent) + to_col[0]*percent) + '%,' \
- + str(from_col[1]*(1-percent) + to_col[1]*percent) + '%,' \
- + str(from_col[2]*(1-percent) + to_col[2]*percent) + '%)" stroke-width="' + str(stroke) + '" stroke-opacity="' + str(opa) + '"'
-
-def svg_generate_dot_style(kind):
- kinds = ["red", "lawngreen", "royalblue", "magenta", "yellow", "cyan", "white", "black"]
-
- r = min(2500/len(nodes), 10)
-
- return 'fill="' + kinds[kind] + '" r="' + str(r) + '" stroke="black" stroke-width="' + str(r/10) + '" fill-opacity="1.0" ' \
- 'stroke-opacity="1.0"'
-
-# -------------------
-
-def load_data(dir):
- global firstnode, nodes, inv_nodes, time
- f = open(dir)
- loaded = 0
-
- for line in f:
- sline = line.split(' ', 1)
- if len(sline) == 2:
- if sline[0] == "[OFFSPRING]":
- creature = json.loads(sline[1])
- #print("B" +str(creature))
- if "FromIDs" in creature:
- if not creature["ID"] in nodes:
- nodes[creature["ID"]] = {}
+import bisect
+import time as timelib
+from PIL import Image, ImageDraw, ImageFont
+
+class LoadingError(Exception):
+ pass
+
+class Drawer:
+
+ def __init__(self, design, config_file, w=600, h=800, w_margin=10, h_margin=20):
+ self.design = design
+ self.width = w
+ self.height = h
+ self.w_margin = w_margin
+ self.h_margin = h_margin
+ self.w_no_margs = w - 2* w_margin
+ self.h_no_margs = h - 2* h_margin
+
+ self.colors = {
+ 'black' : {'r':0, 'g':0, 'b':0},
+ 'red' : {'r':100, 'g':0, 'b':0},
+ 'green' : {'r':0, 'g':100, 'b':0},
+ 'blue' : {'r':0, 'g':0, 'b':100},
+ 'yellow' : {'r':100, 'g':100, 'b':0},
+ 'magenta' : {'r':100, 'g':0, 'b':100},
+ 'cyan' : {'r':0, 'g':100, 'b':100},
+ 'orange': {'r':100, 'g':50, 'b':0},
+ 'purple': {'r':50, 'g':0, 'b':100}
+ }
+
+ self.settings = {
+ 'colors_of_kinds': ['red', 'green', 'blue', 'magenta', 'yellow', 'cyan', 'orange', 'purple'],
+ 'dots': {
+ 'color': {
+ 'meaning': 'depth',
+ 'start': 'purple',
+ 'end': 'green',
+ 'bias': 1
+ },
+ 'size': {
+ 'meaning': 'children',
+ 'start': 1,
+ 'end': 5,
+ 'bias': 0.5
+ },
+ 'opacity': {
+ 'meaning': 'children',
+ 'start': 0.3,
+ 'end': 0.8,
+ 'bias': 1
+ }
+ },
+ 'lines': {
+ 'color': {
+ 'meaning': 'adepth',
+ 'start': 'black',
+ 'end': 'red',
+ 'bias': 3
+ },
+ 'width': {
+ 'meaning': 'adepth',
+ 'start': 1,
+ 'end': 4,
+ 'bias': 3
+ },
+ 'opacity': {
+ 'meaning': 'adepth',
+ 'start': 0.1,
+ 'end': 0.8,
+ 'bias': 5
+ }
+ }
+ }
+
+ def merge(source, destination):
+ for key, value in source.items():
+ if isinstance(value, dict):
+ node = destination.setdefault(key, {})
+ merge(value, node)
+ else:
+ destination[key] = value
+
+ return destination
+
+ if config_file != "":
+ with open(config_file) as config:
+ c = json.load(config)
+ self.settings = merge(c, self.settings)
+ #print(json.dumps(self.settings, indent=4, sort_keys=True))
+
+ def draw_dots(self, file, min_width, max_width, max_height):
+ for i in range(len(self.design.positions)):
+ node = self.design.positions[i]
+ if 'x' not in node:
+ continue
+ dot_style = self.compute_dot_style(node=i)
+ self.add_dot(file, (self.w_margin+self.w_no_margs*(node['x']-min_width)/(max_width-min_width),
+ self.h_margin+self.h_no_margs*node['y']/max_height), dot_style)
+
+ def draw_lines(self, file, min_width, max_width, max_height):
+ for parent in range(len(self.design.positions)):
+ par_pos = self.design.positions[parent]
+ if not 'x' in par_pos:
+ continue
+ for child in self.design.tree.children[parent]:
+ chi_pos = self.design.positions[child]
+ if 'x' not in chi_pos:
+ continue
+ line_style = self.compute_line_style(parent, child)
+ self.add_line(file, (self.w_margin+self.w_no_margs*(par_pos['x']-min_width)/(max_width-min_width),
+ self.h_margin+self.h_no_margs*par_pos['y']/max_height),
+ (self.w_margin+self.w_no_margs*(chi_pos['x']-min_width)/(max_width-min_width),
+ self.h_margin+self.h_no_margs*chi_pos['y']/max_height), line_style)
+
+ def draw_scale(self, file, filename):
+ self.add_text(file, "Generated from " + filename.split("\\")[-1], (5, 15), "start")
+ self.add_dashed_line(file, (self.width*0.7, self.h_margin), (self.width, self.h_margin))
+
+ start_text = ""
+ end_text = ""
+ if self.design.TIME == "BIRTHS":
+ start_text = "Birth #0"
+ end_text = "Birth #" + str(len(self.design.positions)-1)
+ if self.design.TIME == "REAL":
+ start_text = "Time " + str(min(self.design.tree.time))
+ end_text = "Time " + str(max(self.design.tree.time))
+ if self.design.TIME == "GENERATIONAL":
+ start_text = "Depth " + str(self.design.props['adepth']['min'])
+ end_text = "Depth " + str(self.design.props['adepth']['max'])
+
+ self.add_text(file, start_text, (self.width, self.h_margin + 15), "end")
+ self.add_dashed_line(file, (self.width*0.7, self.height-self.h_margin), (self.width, self.height-self.h_margin))
+ self.add_text(file, end_text, (self.width, self.height-self.h_margin + 15), "end")
+
+ def compute_property(self, part, prop, node):
+ start = self.settings[part][prop]['start']
+ end = self.settings[part][prop]['end']
+ value = (self.design.props[self.settings[part][prop]['meaning']][node]
+ if self.settings[part][prop]['meaning'] in self.design.props else 0 )
+ bias = self.settings[part][prop]['bias']
+ if prop == "color":
+ return self.compute_color(start, end, value, bias)
+ else:
+ return self.compute_value(start, end, value, bias)
+
+ def compute_color(self, start, end, value, bias=1):
+ if isinstance(value, str):
+ value = int(value)
+ r = self.colors[self.settings['colors_of_kinds'][value]]['r']
+ g = self.colors[self.settings['colors_of_kinds'][value]]['g']
+ b = self.colors[self.settings['colors_of_kinds'][value]]['b']
+ else:
+ start_color = self.colors[start]
+ end_color = self.colors[end]
+ value = 1 - (1-value)**bias
+ r = start_color['r']*(1-value)+end_color['r']*value
+ g = start_color['g']*(1-value)+end_color['g']*value
+ b = start_color['b']*(1-value)+end_color['b']*value
+ return (r, g, b)
+
+ def compute_value(self, start, end, value, bias=1):
+ value = 1 - (1-value)**bias
+ return start*(1-value) + end*value
+
+class PngDrawer(Drawer):
+ def draw_design(self, filename, input_filename, scale="SIMPLE"):
+ print("Drawing...")
+
+ back = Image.new('RGBA', (self.width, self.height), (255,255,255,0))
+
+ min_width = min([x['x'] for x in self.design.positions if 'x' in x])
+ max_width = max([x['x'] for x in self.design.positions if 'x' in x])
+ max_height = max([x['y'] for x in self.design.positions if 'y' in x])
+
+ self.draw_lines(back, min_width, max_width, max_height)
+ self.draw_dots(back, min_width, max_width, max_height)
+
+ if scale == "SIMPLE":
+ self.draw_scale(back, input_filename)
+
+ back.show()
+ back.save(filename)
+
+ def add_dot(self, file, pos, style):
+ x, y = int(pos[0]), int(pos[1])
+ r = style['r']
+ offset = (int(x - r), int(y - r))
+ size = (2*int(r), 2*int(r))
+
+ c = style['color']
+
+ img = Image.new('RGBA', size)
+ ImageDraw.Draw(img).ellipse((1, 1, size[0]-1, size[1]-1),
+ (int(2.55*c[0]), int(2.55*c[1]), int(2.55*c[2]), int(255*style['opacity'])))
+ file.paste(img, offset, mask=img)
+
+ def add_line(self, file, from_pos, to_pos, style):
+ fx, fy, tx, ty = int(from_pos[0]), int(from_pos[1]), int(to_pos[0]), int(to_pos[1])
+ w = int(style['width'])
+
+ offset = (min(fx-w, tx-w), min(fy-w, ty-w))
+ size = (abs(fx-tx)+2*w, abs(fy-ty)+2*w)
+
+ c = style['color']
+
+ img = Image.new('RGBA', size)
+ ImageDraw.Draw(img).line((w, w, size[0]-w, size[1]-w) if (fx-tx)*(fy-ty)>0 else (size[0]-w, w, w, size[1]-w),
+ (int(2.55*c[0]), int(2.55*c[1]), int(2.55*c[2]), int(255*style['opacity'])), int(style['width']))
+ file.paste(img, offset, mask=img)
+
+ def add_dashed_line(self, file, from_pos, to_pos):
+ style = {'color': (0,0,0), 'width': 1, 'opacity': 1}
+ sublines = 50
+ # TODO could be faster: compute delta and only add delta each time (but currently we do not use it often)
+ for i in range(sublines):
+ from_pos_sub = (self.compute_value(from_pos[0], to_pos[0], 2*i/(2*sublines-1), 1),
+ self.compute_value(from_pos[1], to_pos[1], 2*i/(2*sublines-1), 1))
+ to_pos_sub = (self.compute_value(from_pos[0], to_pos[0], (2*i+1)/(2*sublines-1), 1),
+ self.compute_value(from_pos[1], to_pos[1], (2*i+1)/(2*sublines-1), 1))
+ self.add_line(file, from_pos_sub, to_pos_sub, style)
+
+ def add_text(self, file, text, pos, anchor, style=''):
+ font = ImageFont.truetype("Vera.ttf", 16)
+
+ img = Image.new('RGBA', (self.width, self.height))
+ draw = ImageDraw.Draw(img)
+ txtsize = draw.textsize(text, font=font)
+ pos = pos if anchor == "start" else (pos[0]-txtsize[0], pos[1]-txtsize[1])
+ draw.text(pos, text, (0,0,0), font=font)
+ file.paste(img, (0,0), mask=img)
+
+ def compute_line_style(self, parent, child):
+ return {'color': self.compute_property('lines', 'color', child),
+ 'width': self.compute_property('lines', 'width', child),
+ 'opacity': self.compute_property('lines', 'opacity', child)}
+
+ def compute_dot_style(self, node):
+ return {'color': self.compute_property('dots', 'color', node),
+ 'r': self.compute_property('dots', 'size', node),
+ 'opacity': self.compute_property('dots', 'opacity', node)}
+
+class SvgDrawer(Drawer):
+ def draw_design(self, filename, input_filename, scale="SIMPLE"):
+ print("Drawing...")
+ file = open(filename, "w")
+
+ min_width = min([x['x'] for x in self.design.positions if 'x' in x])
+ max_width = max([x['x'] for x in self.design.positions if 'x' in x])
+ max_height = max([x['y'] for x in self.design.positions if 'y' in x])
+
+ file.write('")
+ file.close()
+
+ def add_text(self, file, text, pos, anchor, style=''):
+ style = (style if style != '' else 'style="font-family: Arial; font-size: 12; fill: #000000;"')
+ file.write('' + text + '')
+
+ def add_dot(self, file, pos, style):
+ file.write('')
+
+ def add_line(self, file, from_pos, to_pos, style):
+ file.write('')
+
+ def add_dashed_line(self, file, from_pos, to_pos):
+ style = 'stroke="black" stroke-width="0.5" stroke-opacity="1" stroke-dasharray="5, 5"'
+ self.add_line(file, from_pos, to_pos, style)
+
+ def compute_line_style(self, parent, child):
+ return self.compute_stroke_color('lines', child) + ' ' \
+ + self.compute_stroke_width('lines', child) + ' ' \
+ + self.compute_stroke_opacity(child)
+
+ def compute_dot_style(self, node):
+ return self.compute_dot_size(node) + ' ' \
+ + self.compute_fill_opacity(node) + ' ' \
+ + self.compute_dot_fill(node)
+
+ def compute_stroke_color(self, part, node):
+ color = self.compute_property(part, 'color', node)
+ return 'stroke="rgb(' + str(color[0]) + '%,' + str(color[1]) + '%,' + str(color[2]) + '%)"'
+
+ def compute_stroke_width(self, part, node):
+ return 'stroke-width="' + str(self.compute_property(part, 'width', node)) + '"'
+
+ def compute_stroke_opacity(self, node):
+ return 'stroke-opacity="' + str(self.compute_property('lines', 'opacity', node)) + '"'
+
+ def compute_fill_opacity(self, node):
+ return 'fill-opacity="' + str(self.compute_property('dots', 'opacity', node)) + '"'
+
+ def compute_dot_size(self, node):
+ return 'r="' + str(self.compute_property('dots', 'size', node)) + '"'
+
+ def compute_dot_fill(self, node):
+ color = self.compute_property('dots', 'color', node)
+ return 'fill="rgb(' + str(color[0]) + '%,' + str(color[1]) + '%,' + str(color[2]) + '%)"'
+
+class Designer:
+
+ def __init__(self, tree, jitter=False, time="GENERATIONAL", balance="DENSITY"):
+ self.props = {}
+
+ self.tree = tree
+
+ self.TIME = time
+ self.JITTER = jitter
+
+ if balance == "RANDOM":
+ self.xmin_crowd = self.xmin_crowd_random
+ elif balance == "MIN":
+ self.xmin_crowd = self.xmin_crowd_min
+ elif balance == "DENSITY":
+ self.xmin_crowd = self.xmin_crowd_density
+ else:
+ raise ValueError("Error, the value of BALANCE does not match any expected value.")
+
+ def calculate_measures(self):
+ print("Calculating measures...")
+ self.compute_adepth()
+ self.compute_depth()
+ self.compute_children()
+ self.compute_kind()
+ self.compute_time()
+ self.compute_custom()
+
+ def xmin_crowd_random(self, x1, x2, y):
+ return (x1 if random.randrange(2) == 0 else x2)
+
+ def xmin_crowd_min(self, x1, x2, y):
+ x1_closest = 999999
+ x2_closest = 999999
+ miny = y-3
+ maxy = y+3
+ i = bisect.bisect_left(self.y_sorted, miny)
+ while True:
+ if len(self.positions_sorted) <= i or self.positions_sorted[i]['y'] > maxy:
+ break
+ pos = self.positions_sorted[i]
+
+ x1_closest = min(x1_closest, abs(x1-pos['x']))
+ x2_closest = min(x2_closest, abs(x2-pos['x']))
+
+ i += 1
+ return (x1 if x1_closest > x2_closest else x2)
+
+ def xmin_crowd_density(self, x1, x2, y):
+ x1_dist = 0
+ x2_dist = 0
+ miny = y-500
+ maxy = y+500
+ i_left = bisect.bisect_left(self.y_sorted, miny)
+ i_right = bisect.bisect_right(self.y_sorted, maxy)
+ # print("i " + str(i) + " len " + str(len(self.positions)))
+ #
+ # i = bisect.bisect_left(self.y_sorted, y)
+ # i_left = max(0, i - 25)
+ # i_right = min(len(self.y_sorted), i + 25)
+
+ def include_pos(pos):
+ nonlocal x1_dist, x2_dist
+
+ dysq = (pos['y']-y)**2
+ dx1 = pos['x']-x1
+ dx2 = pos['x']-x2
+
+ x1_dist += math.sqrt(dysq + dx1**2)
+ x2_dist += math.sqrt(dysq + dx2**2)
+
+ # optimized to draw from all the nodes, if less than 10 nodes in the range
+ if len(self.positions_sorted) > i_left:
+ if i_right - i_left < 10:
+ for j in range(i_left, i_right):
+ include_pos(self.positions_sorted[j])
+ else:
+ for j in range(10):
+ pos = self.positions_sorted[random.randrange(i_left, i_right)]
+ include_pos(pos)
+
+ return (x1 if x1_dist > x2_dist else x2)
+ #print(x1_dist, x2_dist)
+ #x1_dist = x1_dist**2
+ #x2_dist = x2_dist**2
+ #return x1 if x1_dist+x2_dist==0 else (x1*x1_dist + x2*x2_dist) / (x1_dist+x2_dist) + random.gauss(0, 0.01)
+ #return (x1 if random.randint(0, int(x1_dist+x2_dist)) < x1_dist else x2)
+
+ def calculate_node_positions(self, ignore_last=0):
+ print("Calculating positions...")
+
+ current_node = 0
+
+ def add_node(node):
+ nonlocal current_node
+ index = bisect.bisect_left(self.y_sorted, node['y'])
+ self.y_sorted.insert(index, node['y'])
+ self.positions_sorted.insert(index, node)
+ self.positions[node['id']] = node
+
+ self.positions_sorted = [{'x':0, 'y':0, 'id':0}]
+ self.y_sorted = [0]
+ self.positions = [{} for x in range(len(self.tree.parents))]
+ self.positions[0] = {'x':0, 'y':0, 'id':0}
+
+ nodes_to_visit = [0]
+ visited = [False] * len(self.tree.parents)
+ visited[0] = True
+
+ node_counter = 0
+ start_time = timelib.time()
+
+ while True:
+
+ node_counter += 1
+ if node_counter%1000 == 0:
+ print(str(node_counter) + " " + str(timelib.time()-start_time))
+ start_time = timelib.time()
+
+ current_node = nodes_to_visit[0]
+
+ for child in self.tree.children[current_node]:
+ if not visited[child] and self.props['adepth'][child] >= ignore_last/self.props['adepth_max']:
+ nodes_to_visit.append(child)
+ visited[child] = True
+
+ ypos = 0
+ if self.TIME == "BIRTHS":
+ ypos = child
+ elif self.TIME == "GENERATIONAL":
+ ypos = self.positions[current_node]['y']+1
+ elif self.TIME == "REAL":
+ ypos = self.tree.time[child]
+
+ if len(self.tree.parents[child]) == 1:
+ # if current_node is the only parent
+ if self.JITTER:
+ dissimilarity = random.gauss(0, 0.5)
+ else:
+ dissimilarity = 1
+ add_node({'id':child, 'y':ypos, 'x':
+ self.xmin_crowd(self.positions[current_node]['x']-dissimilarity,
+ self.positions[current_node]['x']+dissimilarity, ypos)})
+ else:
+ total_inheretance = sum([v for k, v in self.tree.parents[child].items()])
+ xpos = sum([self.positions[k]['x']*v/total_inheretance
+ for k, v in self.tree.parents[child].items()])
+ if self.JITTER:
+ add_node({'id':child, 'y':ypos, 'x':xpos + random.gauss(0, 0.1)})
+ else:
+ add_node({'id':child, 'y':ypos, 'x':xpos})
+
+ nodes_to_visit = nodes_to_visit[1:]
+ # if none left, we can stop
+ if len(nodes_to_visit) == 0:
+ print("done")
+ break
+
+ def compute_custom(self):
+ for prop in self.tree.props:
+ self.props[prop] = [None for x in range(len(self.tree.children))]
+
+ for i in range(len(self.props[prop])):
+ self.props[prop][i] = self.tree.props[prop][i]
+
+ self.normalize_prop(prop)
+
+ def compute_time(self):
+ # simple rewrite from the tree
+ self.props["time"] = [0 for x in range(len(self.tree.children))]
+
+ for i in range(len(self.props['time'])):
+ self.props['time'][i] = self.tree.time[i]
+
+ self.normalize_prop('time')
+
+ def compute_kind(self):
+ # simple rewrite from the tree
+ self.props["kind"] = [0 for x in range(len(self.tree.children))]
+
+ for i in range (len(self.props['kind'])):
+ self.props['kind'][i] = str(self.tree.kind[i])
+
+ def compute_depth(self):
+ self.props["depth"] = [999999999 for x in range(len(self.tree.children))]
+
+ nodes_to_visit = [0]
+ self.props["depth"][0] = 0
+ while True:
+ for child in self.tree.children[nodes_to_visit[0]]:
+ nodes_to_visit.append(child)
+ self.props["depth"][child] = min([self.props["depth"][d] for d in self.tree.parents[child]])+1
+ nodes_to_visit = nodes_to_visit[1:]
+ if len(nodes_to_visit) == 0:
+ break
+
+ self.normalize_prop('depth')
+
+ def compute_adepth(self):
+ self.props["adepth"] = [0 for x in range(len(self.tree.children))]
+
+ def compute_local_adepth(node):
+ my_adepth = 0
+ for c in self.tree.children[node]:
+ my_adepth = max(my_adepth, compute_local_adepth(c)+1)
+ self.props["adepth"][node] = my_adepth
+ return my_adepth
+
+ compute_local_adepth(0)
+ self.normalize_prop('adepth')
+
+ def compute_children(self):
+ self.props["children"] = [0 for x in range(len(self.tree.children))]
+ for i in range (len(self.props['children'])):
+ self.props['children'][i] = len(self.tree.children[i])
+
+ self.normalize_prop('children')
+
+ def normalize_prop(self, prop):
+ noneless = [v for v in self.props[prop] if type(v)==int or type(v)==float]
+ if len(noneless) > 0:
+ max_val = max(noneless)
+ min_val = min(noneless)
+ self.props[prop +'_max'] = max_val
+ self.props[prop +'_min'] = min_val
+ for i in range(len(self.props[prop])):
+ if self.props[prop][i] is not None:
+ self.props[prop][i] = (self.props[prop][i] - min_val) / max_val
+
+
+class TreeData:
+ simple_data = None
+
+ children = []
+ parents = []
+ time = []
+ kind = []
+
+ def __init__(self): #, simple_data=False):
+ #self.simple_data = simple_data
+ pass
+
+ def load(self, filename, max_nodes=0):
+ print("Loading...")
+
+ CLI_PREFIX = "Script.Message:"
+ default_props = ["Time", "FromIDs", "ID", "Operation", "Inherited"]
+
+ ids = {}
+ def get_id(id):
+ if not id in ids:
+ ids[id] = len(ids)
+ return ids[id]
+
+ file = open(filename)
+
+ # counting the number of expected nodes
+ nodes = 0
+ for line in file:
+ line_arr = line.split(' ', 1)
+ if len(line_arr) == 2:
+ if line_arr[0] == CLI_PREFIX:
+ line_arr = line_arr[1].split(' ', 1)
+ if line_arr[0] == "[OFFSPRING]":
+ nodes += 1
+
+ nodes = min(nodes, max_nodes if max_nodes != 0 else nodes)+1
+ self.parents = [{} for x in range(nodes)]
+ self.children = [[] for x in range(nodes)]
+ self.time = [0] * nodes
+ self.kind = [0] * nodes
+ self.props = {}
+
+ print(len(self.parents))
+
+ file.seek(0)
+ loaded_so_far = 0
+ lasttime = timelib.time()
+ for line in file:
+ line_arr = line.split(' ', 1)
+ if len(line_arr) == 2:
+ if line_arr[0] == CLI_PREFIX:
+ line_arr = line_arr[1].split(' ', 1)
+ if line_arr[0] == "[OFFSPRING]":
+ creature = json.loads(line_arr[1])
+ if "FromIDs" in creature:
+
+ # make sure that ID's of parents are lower than that of their children
+ for i in range(0, len(creature["FromIDs"])):
+ get_id(creature["FromIDs"][i])
+
+ creature_id = get_id(creature["ID"])
+
+ # debug
+ if loaded_so_far%1000 == 0:
+ #print(". " + str(creature_id) + " " + str(timelib.time() - lasttime))
+ lasttime = timelib.time()
+
# we assign to each parent its contribution to the genotype of the child
for i in range(0, len(creature["FromIDs"])):
+ parent_id = get_id(creature["FromIDs"][i])
inherited = 1 #(creature["Inherited"][i] if 'Inherited' in creature else 1) #ONLY FOR NOW
- nodes[creature["ID"]][creature["FromIDs"][i]] = inherited
+ self.parents[creature_id][parent_id] = inherited
+
+ if "Time" in creature:
+ self.time[creature_id] = creature["Time"]
+
+ if "Kind" in creature:
+ self.kind[creature_id] = creature["Kind"]
+
+ for prop in creature:
+ if prop not in default_props:
+ if prop not in self.props:
+ self.props[prop] = [None for i in range(nodes)]
+ self.props[prop][creature_id] = creature[prop]
+
+ loaded_so_far += 1
else:
- print("Duplicated entry for " + creature["ID"])
- quit()
-
- if not creature["FromIDs"][0] in nodes and firstnode == None:
- firstnode = creature["FromIDs"][0]
-
- if "Time" in creature:
- time[creature["ID"]] = creature["Time"]
-
- if "Kind" in creature:
- kind[creature["ID"]] = creature["Kind"]
-
- loaded += 1
- if loaded == max_nodes and max_nodes != 0:
- break
-
- for k, v in sorted(nodes.items()):
- for val in sorted(v):
- inv_nodes[val] = inv_nodes.get(val, [])
- inv_nodes[val].append(k)
-
- print(len(nodes))
-
-
-def load_simple_data(dir):
- global firstnode, nodes, inv_nodes
- f = open(dir)
- loaded = 0
-
- for line in f:
- sline = line.split()
- if len(sline) > 1:
- #if int(sline[0]) > 15000:
- # break
- if sline[0] == firstnode:
- continue
- nodes[sline[0]] = str(max(int(sline[1]), int(firstnode)))
- else:
- firstnode = sline[0]
-
- loaded += 1
- if loaded == max_nodes and max_nodes != 0:
- break
-
- for k, v in sorted(nodes.items()):
- inv_nodes[v] = inv_nodes.get(v, [])
- inv_nodes[v].append(k)
-
- #print(str(inv_nodes))
- #quit()
-
-def compute_depth(node):
- my_depth = 0
- if node in inv_nodes:
- for c in inv_nodes[node]:
- my_depth = max(my_depth, compute_depth(c)+1)
- depth[node] = my_depth
- return my_depth
-
-# ------------------------------------
-
-
-def xmin_crowd_random(x1, x2, y):
- return (x1 if random.randrange(2) == 0 else x2)
-
-def xmin_crowd_min(x1, x2, y):
- x1_closest = 999999
- x2_closest = 999999
- for pos in positions:
- pos = positions[pos]
- if pos[1] == y:
- x1_closest = min(x1_closest, abs(x1-pos[0]))
- x2_closest = min(x2_closest, abs(x2-pos[0]))
- return (x1 if x1_closest > x2_closest else x2)
-def xmin_crowd_density(x1, x2, y):
- x1_dist = 0
- x2_dist = 0
- ymin = y-10
- ymax = y+10
- for pos in positions:
- pos = positions[pos]
- if pos[1] > ymin or pos[1] < ymax:
- dysq = (pos[1]-y)**2
- dx1 = pos[0]-x1
- dx2 = pos[0]-x2
-
-
- x1_dist += math.sqrt(dysq + dx1**2)
- x2_dist += math.sqrt(dysq + dx2**2)
- return (x1 if x1_dist > x2_dist else x2)
-
-# ------------------------------------
-
-def prepos_children():
- global max_height, max_width, min_width, visited, TIME
-
- print("firstnode " + firstnode)
-
- if not bool(time):
- print("REAL time requested, but no real time data provided. Assuming BIRTHS time instead.")
- TIME = "BIRTHS"
-
- positions[firstnode] = [0, 0]
-
- xmin_crowd = None
- if BALANCE == "RANDOM":
- xmin_crowd =xmin_crowd_random
- elif BALANCE == "MIN":
- xmin_crowd = xmin_crowd_min
- elif BALANCE == "DENSITY":
- xmin_crowd = xmin_crowd_density
- else:
- raise ValueError("Error, the value of BALANCE does not match any expected value.")
-
- nodes_to_visit = [firstnode]
-
- node_counter = 0
- start_time = ttime.time()
-
- while True:
-
- node_counter += 1
- if node_counter%1000 == 0 :
- print(str(node_counter) + " " + str(ttime.time()-start_time))
- start_time = ttime.time()
-
- current_node = nodes_to_visit[0]
-
- if current_node in inv_nodes:
- for c in inv_nodes[current_node]:
- # we want to visit the node just once, after all of its parents
- if c not in nodes_to_visit:
- nodes_to_visit.append(c)
-
- cy = 0
- if TIME == "BIRTHS":
- if c[0] == "c":
- cy = int(c[1:])
- else:
- cy = int(c)
- elif TIME == "GENERATIONAL":
- cy = positions[current_node][1]+1
- elif TIME == "REAL":
- cy = time[c]
-
- if len(nodes[c]) == 1:
- dissimilarity = 0
- if JITTER == True:
- dissimilarity = random.gauss(0,1)
- else:
- dissimilarity = 1
- positions[c] = [xmin_crowd(positions[current_node][0]-dissimilarity, positions[current_node][0]+dissimilarity, cy), cy]
- else:
- vsum = sum([v for k, v in nodes[c].items()])
- cx = sum([positions[k][0]*v/vsum for k, v in nodes[c].items()])
-
- if JITTER == True:
- positions[c] = [cx + random.gauss(0, 0.1), cy]
- else:
- positions[c] = [cx, cy]
-
- nodes_to_visit = nodes_to_visit[1:]
- # if none left, we can stop
- if len(nodes_to_visit) == 0:
- break
-
-
- # prepos_children_reccurent(firstnode)
-
- for pos in positions:
- max_height = max(max_height, positions[pos][1])
- max_width = max(max_width, positions[pos][0])
- min_width = min(min_width, positions[pos][0])
-
-# ------------------------------------
-
-def all_parents_visited(node):
- apv = True
- for k, v in sorted(nodes[node].items()):
- if not k in visited:
- apv = False
- break
- return apv
-# ------------------------------------
-
-def draw_children():
- max_depth = 0
- for k, v in depth.items():
- max_depth = max(max_depth, v)
-
- nodes_to_visit = [firstnode]
- while True:
- current_node = nodes_to_visit[0]
-
- if current_node in inv_nodes:
- for c in inv_nodes[current_node]: # inv_node => p->c
-
- if not c in nodes_to_visit:
- nodes_to_visit.append(c)
-
- line_style = ""
- if COLORING == "NONE":
- line_style = svg_line_style
- elif COLORING == "TYPE":
- line_style = (svg_mutation_line_style if len(nodes[c]) == 1 else svg_crossover_line_style)
- else: # IMPORTANCE, default
- line_style = svg_generate_line_style(depth[c]/max_depth)
-
- svg_add_line( (w_margin+w_no_margs*(positions[current_node][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[current_node][1]/max_height),
- (w_margin+w_no_margs*(positions[c][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[c][1]/max_height), line_style)
-
- # we want to draw the node just once
- if DOT_STYLE == "NONE":
- continue
- elif DOT_STYLE == "TYPE":
- dot_style = svg_generate_dot_style(kind[current_node] if current_node in kind else 0) #type
- else: # NORMAL, default
- dot_style = svg_clear_dot_style #svg_generate_dot_style(depth[c]/max_depth)
- svg_add_dot( (w_margin+w_no_margs*(positions[current_node][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[current_node][1]/max_height), dot_style)
- #svg_add_text( str(depth[current_node]), (w_margin+w_no_margs*(positions[current_node][0]-min_width)/(max_width-min_width),
- # h_margin+h_no_margs*positions[current_node][1]/max_height), "end")
-
- # we remove the current node from the list
- nodes_to_visit = nodes_to_visit[1:]
- # if none left, we can stop
- if len(nodes_to_visit) == 0:
- break
-
-def draw_spine():
- nodes_to_visit = [firstnode]
- while True:
- current_node = nodes_to_visit[0]
-
- if current_node in inv_nodes:
- for c in inv_nodes[current_node]: # inv_node => p->c
- if depth[c] == depth[current_node] - 1:
- if not c in nodes_to_visit:
- nodes_to_visit.append(c)
- line_style = svg_spine_line_style
- svg_add_line( (w_margin+w_no_margs*(positions[current_node][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[current_node][1]/max_height),
- (w_margin+w_no_margs*(positions[c][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[c][1]/max_height), line_style)
-
- # we remove the current node from the list
- nodes_to_visit = nodes_to_visit[1:]
- # if none left, we can stop
- if len(nodes_to_visit) == 0:
- break
-
-def draw_skeleton():
- nodes_to_visit = [firstnode]
- while True:
- current_node = nodes_to_visit[0]
-
- if current_node in inv_nodes:
- for c in inv_nodes[current_node]: # inv_node => p->c
- if depth[c] >= min_skeleton_depth:
- if not c in nodes_to_visit:
- nodes_to_visit.append(c)
- line_style = svg_spine_line_style
- svg_add_line( (w_margin+w_no_margs*(positions[current_node][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[current_node][1]/max_height),
- (w_margin+w_no_margs*(positions[c][0]-min_width)/(max_width-min_width), h_margin+h_no_margs*positions[c][1]/max_height), line_style)
-
- # we remove the current node from the list
- nodes_to_visit = nodes_to_visit[1:]
- # if none left, we can stop
- if len(nodes_to_visit) == 0:
- break
-
-# ------------------------------------
-
-def draw_scale(filename ,type):
-
- svg_add_text("Generated from " + filename.split("\\")[-1], (5, 15), "start")
-
- svg_add_line( (w*0.7, h_margin), (w, h_margin), svg_scale_line_style)
- start_text = ""
- if TIME == "BIRTHS":
- start_text = "Birth #" + str(min([int(k[1:]) for k, v in nodes.items()]))
- if TIME == "REAL":
- start_text = "Time " + str(min([v for k, v in time.items()]))
- if TIME == "GENERATIONAL":
- start_text = "Depth " + str(min([v for k, v in depth.items()]))
- svg_add_text( start_text, (w, h_margin + 15), "end")
-
- svg_add_line( (w*0.7, h-h_margin), (w, h-h_margin), svg_scale_line_style)
- end_text = ""
- if TIME == "BIRTHS":
- end_text = "Birth #" + str(max([int(k[1:]) for k, v in nodes.items()]))
- if TIME == "REAL":
- end_text = "Time " + str(max([v for k, v in time.items()]))
- if TIME == "GENERATIONAL":
- end_text = "Depth " + str(max([v for k, v in depth.items()]))
- svg_add_text( end_text, (w, h-h_margin + 15), "end")
-
-
-##################################################### main #####################################################
-
-args = 0
-
-h = 800
-w = 600
-h_margin = 20
-w_margin = 10
-h_no_margs = h - 2* h_margin
-w_no_margs = w - 2* w_margin
-
-max_height = 0
-max_width = 0
-min_width = 9999999999
-
-min_skeleton_depth = 0
-max_nodes = 0
-
-firstnode = None
-nodes = {}
-inv_nodes = {}
-positions = {}
-visited= {}
+ raise LoadingError("[OFFSPRING] misses the 'FromIDs' field!")
+
+ if loaded_so_far >= max_nodes and max_nodes != 0:
+ break
+
+ for k in range(len(self.parents)):
+ v = self.parents[k]
+ for val in self.parents[k]:
+ self.children[val].append(k)
+
depth = {}
-time = {}
kind = {}
def main():
- global svg_file, min_skeleton_depth, max_nodes, args, \
- TIME, BALANCE, DOT_STYLE, COLORING, JITTER, \
- svg_mutation_line_style, svg_crossover_line_style
-
- parser = argparse.ArgumentParser(description='Draws a genealogical tree (generates a SVG file) based on parent-child relationship information from a text file. Supports files generated by Framsticks experiments.')
+
+ parser = argparse.ArgumentParser(description='Draws a genealogical tree (generates a SVG file) based on parent-child relationship '
+ 'information from a text file. Supports files generated by Framsticks experiments.')
parser.add_argument('-i', '--in', dest='input', required=True, help='input file name with stuctured evolutionary data')
- parser.add_argument('-o', '--out', dest='output', required=True, help='output file name for the evolutionary tree (SVG format)')
- draw_tree_parser = parser.add_mutually_exclusive_group(required=False)
- draw_tree_parser.add_argument('--draw-tree', dest='draw_tree', action='store_true', help='whether drawing the full tree should be skipped')
- draw_tree_parser.add_argument('--no-draw-tree', dest='draw_tree', action='store_false')
-
- draw_skeleton_parser = parser.add_mutually_exclusive_group(required=False)
- draw_skeleton_parser.add_argument('--draw-skeleton', dest='draw_skeleton', action='store_true', help='whether the skeleton of the tree should be drawn')
- draw_skeleton_parser.add_argument('--no-draw-skeleton', dest='draw_skeleton', action='store_false')
-
- draw_spine_parser = parser.add_mutually_exclusive_group(required=False)
- draw_spine_parser.add_argument('--draw-spine', dest='draw_spine', action='store_true', help='whether the spine of the tree should be drawn')
- draw_spine_parser.add_argument('--no-draw-spine', dest='draw_spine', action='store_false')
+ parser.add_argument('-o', '--out', dest='output', required=True, help='output file name for the evolutionary tree (SVG/PNG/JPG/BMP)')
+ parser.add_argument('-c', '--config', dest='config', default="", help='config file name ')
#TODO: better names for those parameters
+ parser.add_argument('-W', '--width', default=600, type=int, dest='width', help='width of the output image (600 by default)')
+ parser.add_argument('-H', '--height', default=800, type=int, dest='height', help='heigt of the output image (800 by default)')
+
parser.add_argument('-t', '--time', default='GENERATIONAL', dest='time', help='values on vertical axis (BIRTHS/GENERATIONAL(d)/REAL); '
'BIRTHS: time measured as the number of births since the beginning; '
@@ -465,19 +659,9 @@
'REAL: real time of the simulation')
parser.add_argument('-b', '--balance', default='DENSITY', dest='balance', help='method of placing nodes in the tree (RANDOM/MIN/DENSITY(d))')
- parser.add_argument('-s', '--scale', default='NONE', dest='scale', help='type of timescale added to the tree (NONE(d)/SIMPLE)')
- parser.add_argument('-c', '--coloring', default='IMPORTANCE', dest="coloring", help='method of coloring the tree (NONE/IMPORTANCE(d)/TYPE)')
- parser.add_argument('-d', '--dots', default='TYPE', dest='dots', help='method of drawing dots (individuals) (NONE/NORMAL/TYPE(d))')
+ parser.add_argument('-s', '--scale', default='SIMPLE', dest='scale', help='type of timescale added to the tree (NONE(d)/SIMPLE)')
parser.add_argument('-j', '--jitter', dest="jitter", action='store_true', help='draw horizontal positions of children from the normal distribution')
-
- parser.add_argument('--color-mut', default="#000000", dest="color_mut", help='color of clone/mutation lines in rgba (e.g. #FF60B240) for TYPE coloring')
- parser.add_argument('--color-cross', default="#660198", dest="color_cross", help='color of crossover lines in rgba (e.g. #FF60B240) for TYPE coloring')
-
- parser.add_argument('--min-skeleton-depth', type=int, default=2, dest='min_skeleton_depth', help='minimal distance from the leafs for the nodes in the skeleton')
+ parser.add_argument('-p', '--skip', dest="skip", type=int, default=0, help='skip last P levels of the tree (0 by default)')
+ parser.add_argument('-x', '--max-nodes', type=int, default=0, dest='max_nodes', help='maximum number of nodes drawn (starting from the first one)')
parser.add_argument('--seed', type=int, dest='seed', help='seed for the random number generator (-1 for random)')
-
- parser.add_argument('--simple-data', type=bool, dest='simple_data', help='input data are given in a simple format (#child #parent)')
-
-
- parser.add_argument('-x', '--max-nodes', type=int, default=0, dest='max_nodes', help='maximum number of nodes drawn (starting from the first one)')
parser.set_defaults(draw_tree=True)
@@ -491,23 +675,13 @@
TIME = args.time.upper()
BALANCE = args.balance.upper()
- DOT_STYLE = args.dots.upper()
- COLORING = args.coloring.upper()
SCALE = args.scale.upper()
JITTER = args.jitter
if not TIME in ['BIRTHS', 'GENERATIONAL', 'REAL']\
or not BALANCE in ['RANDOM', 'MIN', 'DENSITY']\
- or not DOT_STYLE in ['NONE', 'NORMAL', 'TYPE']\
- or not COLORING in ['NONE', 'IMPORTANCE', 'TYPE']\
or not SCALE in ['NONE', 'SIMPLE']:
print("Incorrect value of one of the parameters! Closing the program.") #TODO don't be lazy, figure out which parameter is wrong...
return
-
- svg_mutation_line_style += hex_to_style(args.color_mut)
- svg_crossover_line_style += hex_to_style(args.color_cross)
-
dir = args.input
- min_skeleton_depth = args.min_skeleton_depth
- max_nodes = args.max_nodes
seed = args.seed
if seed == -1:
@@ -516,28 +690,17 @@
print("seed:", seed)
- if args.simple_data:
- load_simple_data(dir)
+ tree = TreeData()
+ tree.load(dir, max_nodes=args.max_nodes)
+
+ designer = Designer(tree, jitter=JITTER, time=TIME, balance=BALANCE)
+ designer.calculate_measures()
+ designer.calculate_node_positions(ignore_last=args.skip)
+
+ if args.output.endswith(".svg"):
+ drawer = SvgDrawer(designer, args.config, w=args.width, h=args.height)
else:
- load_data(dir)
-
- compute_depth(firstnode)
-
- svg_file = open(args.output, "w")
- svg_file.write('")
- svg_file.close()
+ drawer = PngDrawer(designer, args.config, w=args.width, h=args.height)
+ drawer.draw_design(args.output, args.input, scale=SCALE)
+
main()
Index: mds-and-trees/tree.conf
===================================================================
--- mds-and-trees/tree.conf (revision 624)
+++ mds-and-trees/tree.conf (revision 624)
@@ -0,0 +1,44 @@
+{
+ "_comment": "Example of the config file, none of the fields is required. Built-in 'meanings' are: adepth, depth, children, kind, time. Any additional custom properties can be used, as long as their values are given in [OFFSPRING] entries. 'Bias' changes the scale to non-linear one: values > 1 result in concave, while values < 1 in convex mapping of the values. 'Kind' is applicable only for the 'color' property and uses the 'colors_for_kinds' list instead of 'start', 'end' and 'bias' fields.",
+ "colors_of_kinds": ["red", "green", "blue", "magenta", "yellow", "cyan", "orange", "purple"],
+ "dots": {
+ "color": {
+ "meaning": "time",
+ "start": "orange",
+ "end": "blue",
+ "bias": 1
+ },
+ "size": {
+ "meaning": "depth",
+ "start": 2,
+ "end": 5,
+ "bias": 1
+ },
+ "opacity": {
+ "meaning": "children",
+ "start": 0.3,
+ "end": 1,
+ "bias": 1
+ }
+ },
+ "lines": {
+ "color": {
+ "meaning": "adepth",
+ "start": "black",
+ "end": "red",
+ "bias": 3
+ },
+ "width": {
+ "meaning": "adepth",
+ "start": 1,
+ "end": 4,
+ "bias": 3
+ },
+ "opacity": {
+ "meaning": "adepth",
+ "start": 0.1,
+ "end": 0.8,
+ "bias": 5
+ }
+ }
+}