gnuplot has three packages that can get installed when you run
apt install gnuplot
On my system, the gnuplot-qt package was installed, and update-alternatives post-install script created the /usr/bin/gnuplot symlink.
But of course, almost everyone is going to run gnuplot via this symlink, and they're never going to type gnuplot-qt
However, command-not-found didn't suggest the "gnuplot" package when I tried to type "gnuplot" before I installed it.
Since command-not-found generally works so well, this made me assume, at first, that gnuplot had been removed, and I wasted a bunch of time looking up the status of the package, etc.
command-not-found is one of the most amazing features of Debian, so it really should work in all cases.
Given that command-not-found cannot sanely parse every postinst script to figure out which alternatives get registered, the only real way to do this is to add alternatives metadata at the package level. This would have to be optional, but something that package maintainers could do if they wanted their alternatives-burdened package to work with command-not-found.
It seems like User-Defined fields, from 5.7 here, are the way to do this:
https://www.debian.org/doc/debian-policy/policy.txt
So, for example, it could be like this:
XBC-Provides-Alternative-Command: /usr/bin/gnuplot
And then this would make it into the binary package as:
Provides-Alternative-Command: /usr/bin/gnuplot
Then command-not-found could include paths from this field in its index.
So anyway, if command-not-found supported this, a package maintainer who's like, "Hey, why is my gnuplot not showing up in command-not-found?" would have a way that they could fix it (by adding this user-defined field to their package).
It would have to be fixed package-by-package, but at least there would be a way forward for any package that wanted to fix it.
Currently, there's no way forward at all.
Jason