awk -f deptab.gawk /var/lib/dpkg/status

deptab.gawk

BEGIN {
  FS = ": "
}

$1 == "Package" {
  pkg = $2
  tab[pkg][""]
}

$1 == "Status" {
  ok = $2 ~ / installed$/
}

$1 == "Provides" && ok {
  gsub(/ \([^)]*)/, "", $2)
  split($2, pkgs, ", ")

  for (i in pkgs) {
    v[pkgs[i]]
    tab[pkg][pkgs[i]]
  }
}

$1 == "Depends" && ok {
  gsub(/ \([^)]*)/, "", $2)
  split($2, deps, /, | \| /)

  for (i in deps)
    tab[deps[i]][pkg]
}

END {
  do {
    cont = 0
    for (dep in tab)
      for (pkg1 in tab[dep]) {
        if (!(pkg1 in tab))
          continue
        for (pkg2 in tab[pkg1]) {
          if (pkg2 in tab[dep])
            continue
          tab[dep][pkg2]
          cont = 1
        }
      }
  } while (cont)

  PROCINFO["sorted_in"] = "@ind_str_asc"
  for (dep in tab) {
    delete tab[dep][""]

    printf "%s", dep
    for (pkg in tab[dep]) {
      if (pkg in v)
        continue
      printf " %s", pkg
    }
    print ""
  }
}