Re: [gentoo-dev] Portage version resolution deficiencies

[Paul de Vrieze]

On Tuesday 23 March 2004 20:01, Jason Stubbs wrote:
> On Wednesday 24 March 2004 00:57, Paul Smith wrote:
> > Hi all; I posted a message about this problem a few weeks ago.  Since
> > then I've looked at the code and traced it through, and verified my
> > fears: Portage's dependency resolution method is only superficial.
>
> I must have missed your last message, but yes portage's dependency
> resolution is lacking. I just rewrote the dependency checker for other
> purposes so understand fairly well how it works, but have never looked at
> addressing these problems before. I previously thought that the main issue
> was speed but, after a quick attempt, I found that the main issue is really
> reverse dependencies.

This issue should be solved in portage-ng. pvdabeel is working on a dependency 
resolution mechanism. Part of the trick is to actively build a graph of 
candidate solutions. Then the best subgraph needs to be selected. The trick 
is to have a lazy strategy of building the candidate solution graph so that 
the actual graph that needs to be constructed (in memory) is not much bigger 
than the best subgraph. One thing that is important too is to have an 
algorithm that determines the best subgraph to work well together with the 
lazy graph solution.

Solving the problem goes really into graph theory but together with early 
pruning I expect the initialised nodes in the complete graph to be only about 
10 times the number of nodes for the best subgraphs (remember that every 
ebuild i a node, possibly even more than one (useflag deps))

Paul

ps. for useflag deps a smart splitting strategy should be used so that nodes 
are only split on useflags when actually needed

-- 
Paul de Vrieze
Gentoo Developer
Mail: pauldv@g.o
Homepage: http://www.devrieze.net