Package: release.debian.org Severity: wishlist User: release.debian....@packages.debian.org Usertags: britney
Hi, I have written a patch to improve britney2's auto-hinter. I noticed that britney2 does not quite cope with complex cases. The tree-circle-dependencies-huge-graph-no-hint[1] test case demonstrates this issue. The current britney cannot solve this if the "DEPTH" and "WIDTH" (in hooks/post-setup) are greater than 3. With the patch it solved the the 20x20 variant[2]. The basic algorithm for the auto-hinter in this patch is to transform the graph of valid candidates into a DAG[3]. Using the DAG it will calculate which components must migrate together. The runtime complexity of this algorithm should be in O(|V| + |E|)[4], where |V| is the number of validate candidates and |E| is the dependencies between them (vertexes and edges in the graph, respectively). ~Niels [1] http://release.debian.org/~nthykier/britney-tests/t/tree-circle-dependencies-huge-graph-no-hint/ [2] In all my tests DEPTH and WIDTH were equal to each other. [3] Using Strongly Connected Components, see http://en.wikipedia.org/wiki/Directed_acyclic_graph#Relation_to_other_kinds_of_graphs [4] I am assuming (on average) constant time hash-look up, append to lists, linear time iteration over hashes. This should be a valid assumption. :) -- System Information: Debian Release: wheezy/sid APT prefers testing APT policy: (990, 'testing'), (500, 'unstable'), (1, 'experimental') Architecture: i386 (x86_64) Kernel: Linux 3.0.0-1-amd64 (SMP w/8 CPU cores) Locale: LANG=en_DK.UTF-8, LC_CTYPE=en_DK.UTF-8 (charmap=UTF-8) Shell: /bin/sh linked to /bin/dash
>From c4f7c8b28cd0e1aa0bef74bf6dda749894b4cb05 Mon Sep 17 00:00:00 2001 From: Niels Thykier <ni...@thykier.net> Date: Sun, 16 Oct 2011 20:02:18 +0200 Subject: [PATCH] Improve auto-hinter to handle harder cases The auto-hinter will first generate a directed acycle graph (DAG) out of the valid candidates[1]. Using the DAG the auto-hinter will then calculate which of the components must migrate together and generate easy hints for those. With this patch, britney2[2] can solve the "huge-graph" test case[3]. [1] Any graph can be condensated into a DAG by calculating the strongly connected components and looking at the egdes between these components. See: http://en.wikipedia.org/wiki/Directed_acyclic_graph#Relation_to_other_kinds_of_graphs [2] Using --auto-hinter (and --compatiable) [3] tree-circle-dependencies-huge-graph-no-hint --- britney.py | 137 +++++++++++++++++++++++++++++++++++++----------------------- 1 files changed, 84 insertions(+), 53 deletions(-) diff --git a/britney.py b/britney.py index 351651a..822604f 100755 --- a/britney.py +++ b/britney.py @@ -2840,60 +2840,91 @@ class Britney: """ self.__log("> Processing hints from the auto hinter", type="I") - # consider only excuses which are valid candidates - excuses = dict([(x.name, x) for x in self.excuses if x.name in self.upgrade_me]) - - def find_related(e, hint, circular_first=False): - if e not in excuses: - return False - excuse = excuses[e] - if e in self.sources['testing'] and self.sources['testing'][e][VERSION] == excuse.ver[1]: - return True - if not circular_first: - hint[e] = excuse.ver[1] - if len(excuse.deps) == 0: - return hint - for p in excuse.deps: - if p in hint: continue - if not find_related(p, hint): - return False - return hint - - # loop on them - candidates = [] - for e in excuses: - excuse = excuses[e] - if e in self.sources['testing'] and self.sources['testing'][e][VERSION] == excuse.ver[1]: - continue - if len(excuse.deps) > 0: - hint = find_related(e, {}, True) - if isinstance(hint, dict) and e in hint and hint not in candidates: - candidates.append(hint.items()) - else: - items = [ (e, excuse.ver[1]) ] - for item, ver in items: - # excuses which depend on "item" or are depended on by it - items.extend( [ (x, excuses[x].ver[1]) for x in excuses if \ - (item in excuses[x].deps or x in excuses[item].deps) \ - and (x, excuses[x].ver[1]) not in items ] ) - if len(items) > 1: - candidates.append(items) - - to_skip = [] - for i in range(len(candidates)): - for j in range(i+1, len(candidates)): - if i in to_skip or j in to_skip: - # we already know this list isn't interesting + candidates = dict([(x.name, x) for x in self.excuses if x.name in self.upgrade_me]) + low = {} + stack = [] + components = [] + commap = {} + comdeps = {} + comrdeps = {} + hints = [] + roots = [] + + # First we generate the strongly connected components in the + # graph using Tarjan's algorithm. (Tarjan's is order O(|V| + |E|)) + # + def visit (e, candidate): + if e in low: return + num = len(low) + low[e] = num + stack_pos = len(stack) + stack.append(e) + + for suc in candidate.deps: + if not suc in candidates: continue - elif frozenset(candidates[i]) >= frozenset(candidates[j]): - # j is a subset of i; ignore it - to_skip.append(j) - elif frozenset(candidates[i]) <= frozenset(candidates[j]): - # i is a subset of j; ignore it - to_skip.append(i) - for i in range(len(candidates)): - if i not in to_skip: - self.do_hint("easy", "autohinter", candidates[i]) + visit(suc, candidates[suc]) + low[e] = min(low[e], low[suc]) + + if num == low[e]: + component = tuple(stack[stack_pos:]) + del stack[stack_pos:] + components.append(component) + for i in component: + low[i] = len(candidates) + 1 + commap[i] = component; + comdeps[component[0]] = {} + comrdeps[component[0]] = {} + + for e in candidates: + candidate = candidates[e] + # Skip if e is already in testing? (copy-wasted from the previous code) + if e in self.sources['testing'] and self.sources['testing'][e][VERSION] == candidate.ver[1]: + continue + visit(e, candidate) + + # Now that the strongly connected components are generated, we + # generate a DAG using a single element from each component as + # a represent of the component. + # + # y in condeps[x] => x depends on y + # y in conrdeps[x] => x is an rdeps of y + + for component in components: + for e in component: + for d in candidates[e].deps: + if not d in candidates: continue + if d in component: continue + dc = commap[d] + if not dc[0] in comdeps[component[0]]: + comdeps[component[0]][dc[0]] = 1; + comrdeps[dc[0]][component[0]] = 1; + # If this component does not depend on anything (outside + # itself) then it is a good starting point :) + if len(comdeps[component[0]]) < 1: + roots.append(component) + + # We look at each of the "bottom" components and add all + # reverse-dependencies of said component + for component in roots: + hint = [] + seen = {} + stack.append(component) + seen[component[0]] = 1 + while len(stack): + top = stack.pop() + for rdep in comrdeps[top[0]]: + if rdep in seen: continue + stack.append(commap[rdep]) + seen[rdep] = 1 + hint.extend(top) + hints.append(hint) + + for hint in hints: + # Hints only works if there 2 or more packages + if len(hint) < 2: + continue + self.do_hint("easy", "autohinter", [(x, candidates[x].ver[1]) for x in hint]) def old_libraries(self): """Detect old libraries left in testing for smooth transitions -- 1.7.6.3