Changeset 701 for mds-and-trees


Ignore:
Timestamp:
09/20/17 15:29:50 (3 years ago)
Author:
konrad
Message:

Fixed a bug that could occur for trees with a lot of crossover (assigning nodes positions in wrong order)

File:
1 edited

Legend:

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

    r700 r701  
    397397        print("Calculating measures...")
    398398        self.compute_depth()
     399        self.compute_maxdepth()
    399400        self.compute_adepth()
    400401        self.compute_children()
     
    493494        # order by maximum depth of the parent guarantees that co child is evaluated before its parent
    494495        visiting_order = [i for i in range(0, len(self.tree.parents))]
    495         visiting_order = sorted(visiting_order, key=lambda q:
    496                             0 if q == 0 else max([self.props["depth"][d] for d in self.tree.parents[q]]))
     496        visiting_order = sorted(visiting_order, key=lambda q:\
     497                            0 if q == 0 else self.props["maxdepth"][q])
    497498
    498499        start_time = timelib.time()
     
    586587        self.normalize_prop('depth')
    587588
     589    def compute_maxdepth(self):
     590        self.props["maxdepth"] = [999999999 for x in range(len(self.tree.children))]
     591        visited = [0 for x in range(len(self.tree.children))]
     592
     593        nodes_to_visit = [0]
     594        visited[0] = 1
     595        self.props["maxdepth"][0] = 0
     596        while True:
     597            current_node = nodes_to_visit[0]
     598
     599            for child in self.tree.children[current_node]:
     600                if visited[child] == 0:
     601                    visited[child] = 1
     602                    nodes_to_visit.append(child)
     603                    self.props["maxdepth"][child] = self.props["maxdepth"][current_node]+1
     604                elif self.props["maxdepth"][child] < self.props["maxdepth"][current_node]+1:
     605                    self.props["maxdepth"][child] = self.props["maxdepth"][current_node]+1
     606                    if child not in  nodes_to_visit:
     607                        nodes_to_visit.append(child)
     608
     609            nodes_to_visit = nodes_to_visit[1:]
     610            if len(nodes_to_visit) == 0:
     611                break
     612
     613        self.normalize_prop('maxdepth')
     614
    588615    def compute_adepth(self):
    589616        self.props["adepth"] = [0 for x in range(len(self.tree.children))]
     
    591618        # order by maximum depth of the parent guarantees that co child is evaluated before its parent
    592619        visiting_order = [i for i in range(0, len(self.tree.parents))]
    593         visiting_order = sorted(visiting_order, key=lambda q:
    594                             0 if q == 0 else max([self.props["depth"][d] for d in self.tree.parents[q]]))[::-1]
     620        visiting_order = sorted(visiting_order, key=lambda q: self.props["maxdepth"][q])[::-1]
    595621
    596622        for node in visiting_order:
     
    672698                if id not in self.ids:
    673699                    return None
     700
    674701            return self.ids[id]
    675702
Note: See TracChangeset for help on using the changeset viewer.