Changeset 677 for mds-and-trees


Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • mds-and-trees/tree-genealogy.py

    r633 r677  
    430430        print("Calculating positions...")
    431431
    432         current_node = 0
    433 
    434432        def add_node(node):
    435             nonlocal current_node
    436433            index = bisect.bisect_left(self.y_sorted, node['y'])
    437434            self.y_sorted.insert(index, node['y'])
     
    444441        self.positions[0] = {'x':0, 'y':0, 'id':0}
    445442
    446         nodes_to_visit = [0]
    447         visited = [False] * len(self.tree.parents)
    448         visited[0] = True
     443        # order by maximum depth of the parent guarantees that co child is evaluated before its parent
     444        visiting_order = [i for i in range(0, len(self.tree.parents))]
     445        visiting_order = sorted(visiting_order, key=lambda q:
     446                            0 if q == 0 else max([self.props["depth"][d] for d in self.tree.parents[q]]))
    449447
    450448        node_counter = 0
    451449        start_time = timelib.time()
    452450
    453         while True:
    454 
     451        # for each child of the current node
     452        for child in visiting_order:
    455453            node_counter += 1
     454            # debug info - elapsed time
    456455            if node_counter%1000 == 0:
    457                 print(str(node_counter) + " " + str(timelib.time()-start_time))
    458                 start_time = timelib.time()
    459 
    460             current_node = nodes_to_visit[0]
    461 
    462             for child in self.tree.children[current_node]:
    463                 if not visited[child] and self.props['adepth'][child] >= ignore_last/self.props['adepth_max']:
    464                     nodes_to_visit.append(child)
    465                     visited[child] = True
    466 
    467                     ypos = 0
    468                     if self.TIME == "BIRTHS":
    469                         ypos = child
    470                     elif self.TIME == "GENERATIONAL":
    471                         ypos = self.positions[current_node]['y']+1
    472                     elif self.TIME == "REAL":
    473                         ypos = self.tree.time[child]
    474 
    475                     if len(self.tree.parents[child]) == 1:
    476                     # if current_node is the only parent
    477                         if self.JITTER:
    478                             dissimilarity = random.gauss(0, 0.5)
    479                         else:
    480                             dissimilarity = 1
    481                         add_node({'id':child, 'y':ypos, 'x':
    482                                  self.xmin_crowd(self.positions[current_node]['x']-dissimilarity,
    483                                   self.positions[current_node]['x']+dissimilarity, ypos)})
     456               print(str(node_counter) + " " + str(timelib.time()-start_time))
     457               start_time = timelib.time()
     458
     459            # using normalized adepth
     460            if self.props['adepth'][child] >= ignore_last/self.props['adepth_max']:
     461
     462                ypos = 0
     463                if self.TIME == "BIRTHS":
     464                    ypos = child
     465                elif self.TIME == "GENERATIONAL":
     466                    # one more than its parent (what if more than one parent?)
     467                    ypos = max([self.positions[par]['y'] for par, v in self.tree.parents[child].items()])+1
     468                elif self.TIME == "REAL":
     469                    ypos = self.tree.time[child]
     470
     471                if len(self.tree.parents[child]) == 1:
     472                # if current_node is the only parent
     473                    parent = [par for par, v in self.tree.parents[child].items()][0]
     474
     475                    if self.JITTER:
     476                        dissimilarity = random.gauss(0, 0.5)
    484477                    else:
    485                         total_inheretance = sum([v for k, v in self.tree.parents[child].items()])
    486                         xpos = sum([self.positions[k]['x']*v/total_inheretance
    487                                    for k, v in self.tree.parents[child].items()])
    488                         if self.JITTER:
    489                             add_node({'id':child, 'y':ypos, 'x':xpos + random.gauss(0, 0.1)})
    490                         else:
    491                             add_node({'id':child, 'y':ypos, 'x':xpos})
    492 
    493             nodes_to_visit = nodes_to_visit[1:]
    494             # if none left, we can stop
    495             if len(nodes_to_visit) == 0:
    496                 print("done")
    497                 break
     478                        dissimilarity = 1
     479                    add_node({'id':child, 'y':ypos, 'x':
     480                             self.xmin_crowd(self.positions[parent]['x']-dissimilarity,
     481                              self.positions[parent]['x']+dissimilarity, ypos)})
     482                else:
     483                    # position weighted by the degree of inheritence from each parent
     484                    total_inheretance = sum([v for k, v in self.tree.parents[child].items()])
     485                    xpos = sum([self.positions[k]['x']*v/total_inheretance
     486                               for k, v in self.tree.parents[child].items()])
     487                    if self.JITTER:
     488                        add_node({'id':child, 'y':ypos, 'x':xpos + random.gauss(0, 0.1)})
     489                    else:
     490                        add_node({'id':child, 'y':ypos, 'x':xpos})
     491
    498492
    499493    def compute_custom(self):
Note: See TracChangeset for help on using the changeset viewer.