Changeset 677

Timestamp:

08/27/17 15:06:39 (7 years ago)

Author:

konrad

Message:

Fixed a bug with an incorrect order of assigning placement to nodes

File:

• mds-and-trees/tree-genealogy.py (modified) (2 diffs)

mds-and-trees/tree-genealogy.py

@@ -430 +430 @@
         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'])
@@ -444 +441 @@
         self.positions[0] = {'x':0, 'y':0, 'id':0}
 
-        nodes_to_visit = [0]
-        visited = [False] * len(self.tree.parents)
-        visited[0] = True
+        # order by maximum depth of the parent guarantees that co child is evaluated before its parent
+        visiting_order = [i for i in range(0, len(self.tree.parents))]
+        visiting_order = sorted(visiting_order, key=lambda q:
+                            0 if q == 0 else max([self.props["depth"][d] for d in self.tree.parents[q]]))
 
         node_counter = 0
         start_time = timelib.time()
 
-        while True:
-
+        # for each child of the current node
+        for child in visiting_order:
             node_counter += 1
+            # debug info - elapsed time
             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)})
+               print(str(node_counter) + " " + str(timelib.time()-start_time))
+               start_time = timelib.time()
+
+            # using normalized adepth
+            if self.props['adepth'][child] >= ignore_last/self.props['adepth_max']:
+
+                ypos = 0
+                if self.TIME == "BIRTHS":
+                    ypos = child
+                elif self.TIME == "GENERATIONAL":
+                    # one more than its parent (what if more than one parent?)
+                    ypos = max([self.positions[par]['y'] for par, v in self.tree.parents[child].items()])+1
+                elif self.TIME == "REAL":
+                    ypos = self.tree.time[child]
+
+                if len(self.tree.parents[child]) == 1:
+                # if current_node is the only parent
+                    parent = [par for par, v in self.tree.parents[child].items()][0]
+
+                    if self.JITTER:
+                        dissimilarity = random.gauss(0, 0.5)
                     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
+                        dissimilarity = 1
+                    add_node({'id':child, 'y':ypos, 'x':
+                             self.xmin_crowd(self.positions[parent]['x']-dissimilarity,
+                              self.positions[parent]['x']+dissimilarity, ypos)})
+                else:
+                    # position weighted by the degree of inheritence from each parent
+                    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})
+
 
     def compute_custom(self):