The latest version of what I'm working on is at:
This is for the Provides side of things. A harder unsolved problem still is the Requires side, which currently requires perusing of code (or writing packagekit hooks or finding magical ponies). I'd much prefer if this sort of metadata was more easily available, say, also in service .desktop files, but I'm not picky.
Enjoy, discuss, frolic.