I am happy to announce that I have accepted PEP 643: Metadata for Package Source Distributions, which has the potential to dramatically simplify Python package metadata resolution in the future. https://python.org/dev/peps/pep-0643/
Soon you may be able to build reliable dependency graphs!
For some background on one problem this solves, see @di_codes@twitter.com 's 2018 article "Why PyPI Doesn't Know Your Project's Dependencies": https://dustingram.com/articles/2018/03/05/why-pypi-doesnt-know-dependencies/
PEP 643 can't 100% fix this, but it makes it possible for a project to indicate that it doesn't have this failure mode.
With the right implementation in setuptools, 90% of packages will start cutting releases with reliable dependency metadata without any action needed by their maintainers.
You can ensure that your package will have properly annotated reliable metadata by either:
Specifying install_requires in setup.cfg or by using literals in your http://setup.py. If you have conditional dependencies, use environment markers:
https://www.python.org/dev/peps/pep-0508/#environment-markers
When PEP 621 is implemented in setuptools, using PEP 621 for your metadata spec will also work (and is probably the best option): https://www.python.org/dev/peps/pep-0621/