Minimizes a list of debian packages by removing those implied as dependencies of the others

mindeps.py

#!/usr/bin/python
#######################################################################
# This program is free software; you can redistribute it and/or       #
# modify it under the terms of the GNU General Public License as      #
# published by the Free Software Foundation; either version 2 of the  #
# License, or (at your option) any later version.                     #
#                                                                     #
# This program is distributed in the hope that it will be useful, but #
# WITHOUT ANY WARRANTY; without even the implied warranty of          #
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU   #
# General Public License for more details.                            #
#                                                                     #
# Written and (c) by Francois Garillot                                #
# Contact <francois@garillot.net> for comment & bug reports           #
#######################################################################
# mindeps
import sys,subprocess, re

def getpipeoutput(cmds, quiet = False):
    if not quiet:
        print '>> ' + ' | '.join(cmds),
        sys.stdout.flush()
    p0 = subprocess.Popen(cmds[0], stdout = subprocess.PIPE, shell = True)
    p = p0
    for x in cmds[1:]:
        p = subprocess.Popen(x, stdin = p0.stdout, stdout = subprocess.PIPE, shell = True)
        p0 = p
    output = p.communicate()[0]
    return output.rstrip('\n')

def get_crazyformat_reqs(pack,dependtypes):
    """apt-cache in depends mode includes abstract requirements like
    <emacs-21> that do not play nice with our format"""
    folist = getpipeoutput(['apt-cache depends %s 2> /dev/null' % pack],
                           quiet=True).split('\n')
    foreqs = {}
    for req in dependtypes:
        reqlist = filter(lambda s : s.find(req) >= 0,folist)
        foreqs[req] = map (lambda s : s.rpartition(': ')[2].strip(),reqlist)
    return foreqs

def get_saneformat_stg(pack):
    """apt-cache in showpkg mode gives you a nice ouptut but
    indiscriminately includes suggestions, depends, etc"""
    fostr = getpipeoutput(['apt-cache showpkg %s 2> /dev/null' % pack,
                            'grep -A 1 Dependencies', 'tail -n 1'], quiet=True).rstrip('\n')
    fostr = fostr.partition(' - ')[2]
    return re.sub('\s\(\d+\s.*?\)\s',' ',fostr).split(' ')

def build_graph(vertexes):
    fodepends=[]
    wanted = ['Depends']
    for pack in vertexes:
        # We want to get the benefits of graph traversal sharing when
        # giving many arguments to apt-rdepends. That implies getting the
        # first-order depends before invoking apt-rdepends since, from
        # looking at apt-depends output, it's impossible to discriminate
        # between packages that were passed on the command line and those
        # that were deduced as transitive dpeendencies of other packages
        crazydepends = get_crazyformat_reqs(pack,wanted)
        sanedeps = set(get_saneformat_stg(pack))
        for d in wanted:
            sanedeps = sanedeps.intersection(set(crazydepends[d]))
        fodepends += list(sanedeps)
    packs = " ".join(fodepends)
    deps = getpipeoutput(['apt-rdepends %s 2> /dev/null' % packs,
                          'grep -v Depends'], quiet=True).split('\n')
    newdeps = filter(lambda x : x in vertexes,deps)
    return newdeps

def undup(l):
    return list(set(l))

def main(args):
    implied = undup(build_graph(args))
    print " ".join(filter(lambda x : x not in implied,args))

if __name__ == '__main__':
    main(sys.argv[1:])

To use mindeps.py, please, install apt-rdepends:
sudo apt-get install apt-rdepends

Port to Python 3 & refactoring: https://gist.github.com/tobwen/f010b680f9920186aad1ac6d1f8882db