Commits

Peter Arrenbrecht committed 556045f

fix and speed up general headsof

Current headsof() only works if nodes is a connected set.
So I renamed current headsof to headsofconnectedset and
readded the old headsof. Made old headsof faster too.

Comments (0)

Files changed (2)

     def headsof(self, nodes):
         '''return subset of nodes where no node has a descendant in nodes'''
         hds = set(nodes)
+        seen = set()
+        if not hds:
+            return hds
+        for n in sorted(nodes, reverse=True):
+            if n in hds:
+                ps = self.parents(n)
+                if ps:
+                    ancestors = self.nodeset(heads=ps, stops=seen)
+                    seen.update(ancestors)
+                    hds.difference_update(ancestors)
+        assert hds
+        return hds
+
+    def headsofconnectedset(self, nodes):
+        '''return subset of connected set so that no node has a descendant in it
+
+        By "connected set" we mean that if an ancestor and a descendant are in
+        the set, then so is at least one path connecting them.'''
+        hds = set(nodes)
         if not hds:
             return hds
         for n in nodes:

src/discovery_tonfa.py

         return set(nodes)
 
     if TRACE: print "headsof"
-    heads = dag.headsof(nodes)
+    heads = dag.headsofconnectedset(nodes)
     if TRACE: print heads
     sample = set()