Changeset 681 for mds-and-trees


Ignore:
Timestamp:
08/28/17 18:43:30 (3 years ago)
Author:
konrad
Message:

Improved the compute_depth function so now it works much faster for trees with crossover

File:
1 edited

Legend:

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

    r680 r681  
    519519    def compute_depth(self):
    520520        self.props["depth"] = [999999999 for x in range(len(self.tree.children))]
     521        visited = [0 for x in range(len(self.tree.children))]
    521522
    522523        nodes_to_visit = [0]
     524        visited[0] = 1
    523525        self.props["depth"][0] = 0
     526
    524527        while True:
    525             for child in self.tree.children[nodes_to_visit[0]]:
    526                 nodes_to_visit.append(child)
    527                 self.props["depth"][child] = min([self.props["depth"][d] for d in self.tree.parents[child]])+1
     528            current_node = nodes_to_visit[0]
     529            for child in self.tree.children[current_node]:
     530                if visited[child] == 0:
     531                    visited[child] = 1
     532                    nodes_to_visit.append(child)
     533                    self.props["depth"][child] = self.props["depth"][current_node]+1
    528534            nodes_to_visit = nodes_to_visit[1:]
    529535            if len(nodes_to_visit) == 0:
Note: See TracChangeset for help on using the changeset viewer.