Skip to content

Instantly share code, notes, and snippets.

Last active December 19, 2023 16:41
Show Gist options
  • Star 5 You must be signed in to star a gist
  • Fork 3 You must be signed in to fork a gist
  • Save kotarou3/2b311fb7b79ae6b682246b32acf0b7e9 to your computer and use it in GitHub Desktop.
Save kotarou3/2b311fb7b79ae6b682246b32acf0b7e9 to your computer and use it in GitHub Desktop.
Find top-level packages of the dependency graph for debian packages
import argparse, sys
import apt
import networkx as nx
parser = argparse.ArgumentParser(
description = "Find top-level packages of the dependency graph"
"names", metavar = "package", nargs = "*",
help = "package names to use (default: all installed packages)"
"--root-dir", metavar = "dir",
help = "act as if chrooted in the specified directory"
"--follow-unspecified-packages", action = "store_true",
help = "follow dependencies of packages not part of the initial input"
"--no-use-recommends", action = "store_true",
help = "don't use recommended packages for the dependency graph"
"--show-missing-recommends", action = "store_true",
help = "list missing recommended packages suffixed with a dash"
args = parser.parse_args()
inputPackages = set()
cache = apt.Cache(rootdir = args.root_dir)
providedPackages = dict()
def nameToPackage(name):
if name not in cache:
if name in providedPackages:
return providedPackages[name]
return None
package = cache[name]
if package.installed:
return package.installed
return max(package.versions)
def resolveDependencyBranch(dependency, arch):
# Pick every possible or branch for simplicity if the dependency isn't one
# of the input packages, which means we might not find all the root nodes,
# but in practice usually isn't a problem since a branched dependency is
# usually of libraries
baseDependencies = set()
for baseDependency in dependency.or_dependencies:
package = nameToPackage( + ":" + arch)
if not package:
if package in inputPackages:
return {(package, type)}
baseDependencies.add((package, baseDependency.rawtype))
return baseDependencies
def outputPackageList(packages):
if len(packages) > 1:
return "(" + " ".join(packages) + ")"
return packages[0]
# Find the packages
fail = False
for name in args.names:
package = nameToPackage(name)
if not package:
print("Could not find in package cache:", name, file = sys.stderr)
fail = True
for name in package.provides:
providedPackages[name + ":" + package.package.architecture()] = package
if fail:
# Use all installed packages if no packages were specified
if len(inputPackages) == 0:
for package in cache:
package = package.installed
if not package:
for name in package.provides:
providedPackages[name + ":" + package.package.architecture()] = package
# Build our dependency graph
packagesDG = nx.MultiDiGraph()
visitStack = list(inputPackages)
visitedPackages = set()
while len(visitStack) > 0:
package = visitStack.pop()
fullname = package.package.fullname
dependencies = package.dependencies
if not args.no_use_recommends:
arch = package.package.architecture()
for dependency in dependencies:
for dependencyPackage, type in resolveDependencyBranch(dependency, arch):
dependencyFullname = dependencyPackage.package.fullname
packagesDG.add_edge(fullname, dependencyFullname, type = type)
if args.follow_unspecified_packages and dependencyFullname not in visitedPackages:
# Remove any cycles
nodes = list(nx.strongly_connected_components(packagesDG))
packagesDAG = nx.condensation(packagesDG, scc = nodes)
# Find the nodes that have no in-edges - these are the top-level nodes
topLevelNodes = set()
for node in packagesDAG:
if len(list(packagesDAG.predecessors(node))) == 0:
# Convert the nodes back into package names
topLevelPackages = set()
for node in topLevelNodes:
packages = inputPackages & set(map(nameToPackage, nodes[node]))
packages = sorted(packages, key = lambda p:
packageNames = [ for package in packages]
# The results should always be one of the input packages
assert(len(packages) > 0)
if packages[0].priority not in {"required", "important"}:
if len(packages) > 1:
print("{} consists of {}".format(packageNames[0], outputPackageList(packageNames)), file = sys.stderr)
# Find missing recommend packages if requested
if args.show_missing_recommends:
recommendedVias = dict()
for edge in packagesDG.edges(data = True):
if edge[2]["type"] != "Recommends":
package = nameToPackage(edge[1])
if package and package not in inputPackages:
recommendedVias.setdefault(edge[1], set()).add(edge[0])
for edge in packagesDG.edges(data = True):
if edge[2]["type"] != "Recommends":
recommendedVias.pop(edge[1], None)
for name, via in recommendedVias.items():
by = topLevelPackages & set(map(nameToPackage, nx.ancestors(packagesDG, name)))
via = set(map(nameToPackage, via)) - set(by)
name = nameToPackage(name)
via = sorted( for package in via)
by = sorted( for package in by)
"{}- is recommended by {}{}".format(
" via {}".format(outputPackageList(sorted(via))) if len(via) > 0 else ""
file = sys.stderr
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment