Debian Package Dependency Reducer (python2)

dpkgdeps

#!/usr/bin/env python
import re
import sys
import subprocess

# This program reduces dependency lists down to their top-level
# dependencies. It works by building a dependency tree obtained by
# repeated invocations of 'apt-cache depends'. It was developed for
# finding dependency list for Debian package (.deb files) control
# files.

# Here is a recommended way to obtain the initial dependency list:
#  $ ldd <binary> | cut -d' ' -f3 | xargs dpkg --search | cut -d':' -f1 > <list-file>
# This may have duplicates. Though it doesn't matter, you can make the list unique:
#  $ sort <list-file> | uniq > <list-file>.uniq
# Now reduce the list to its top-level dependencies:
#  $ dpkgdeps <list-file>.uniq
# You could have done this all in one step without the intermediate file:
#  $ ldd <binary> | cut -d' ' -f3 | xargs dpkg --search | cut -d':' -f1 | dpkgdeps

def grab_deps(x):
    m = re.match(" *Depends: *([^<>]*)$",x)
    if m is None:
        return ''
    return m.group(1)

class Dep:
    inst = {}
    built = {}

    def __init__(self,pkg):
        # Obtain dependency list from 'apt-cache'.
        try:
            self.deps = filter(lambda x: x != '',
                               map(grab_deps,
                                   subprocess.check_output(['apt-cache','depends',pkg]).split('\n')))
        except subprocess.CalledProcessError as e:
            self.deps = []
            sys.stderr.write(sys.argv[0]+": warning: "+str(e)+"\n")
        self.pkg = pkg
        self.ref = 0

        # Add object to global collection keyed by name.
        Dep.inst[pkg] = self

    def build(self):
        subbuilds = []
        for d in self.deps:
            if not d in Dep.built:
                if d in Dep.inst:
                    o = Dep.inst[d]
                else:
                    o = Dep(d)
                    subbuilds.append(o)
                o.upref()

        # Flag nodes that have been built so as to avoid cycles.
        Dep.built[self.pkg] = True
        for o in subbuilds:
            o.build()

    def upref(self):
        self.ref += 1

    def __repr__(self):
        return self.pkg

    @staticmethod
    def toplevel():
        # Find the top-level nodes that have the fewest parents. All answers
        # must fall in the same class. Ideally 'n' will be zero (except when
        # we've had circular dependencies).
        ds = []
        n = -1
        for d in Dep.inst:
            o = Dep.inst[d]
            if n < 0 or o.ref < n:
                n = o.ref
                ds = [o]
            elif o.ref == n:
                ds.append(o)
        return ds

if len(sys.argv) <= 1:
    f = sys.stdin
else:
    f = open(sys.argv[1])
pkgs = map(lambda x: Dep(x),f.read().split())
for p in pkgs:
    p.build()
print reduce(lambda x,y: x+', '+y if x != '' else y,
             map(str,Dep.toplevel()),'')