> The only way to fix this is to /not/ install *any* packages prior to
> resolving *all* dependencies

packaging.install rolls back in case of error, so the system can’t be left in a half-installed state.  p7g.install is only as smart as p7g.depgraph, however.

> which means that there needs to be a way to resolve the entire
> dependency graph for any given package in PyPI.

PyPI exposes requires, obsoletes and provides for releases that upload PEP 345 metadata; client code using p7g.pypi and p7g.depgraph can then build a dependency graph.

> the PyPM repository provides a sqlite db containing dependency
> information for all packages and their versions.

This experiment with a local copy of the full repo graph is interesting.  Do you have blog posts or something talking about synchronization issues, dealing with multiple repositories, using SQL vs. something less ugly <wink>, etc.?

> Let me know if you need any assistance regarding ActiveState's
> depgraph implementation

First, what we need here is a pronouncement from Tarek about smarter depgraph vs. simple stupid depgraph.  If we decide to improve depgraph, ideas from your code will have to be extracted and ported.  This will probably require a contributor agreement.