From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20401 invoked from network); 12 May 2004 05:14:34 +0000 Received: from smtp.gentoo.org (128.193.0.39) by eagle.gentoo.oregonstate.edu with DES-CBC3-SHA encrypted SMTP; 12 May 2004 05:14:34 +0000 Received: from lists.gentoo.org ([128.193.0.34] helo=eagle.gentoo.org) by smtp.gentoo.org with esmtp (Exim 4.24) id 1BNm4g-0001IH-HC for arch-gentoo-portage-dev@lists.gentoo.org; Wed, 12 May 2004 05:14:34 +0000 Received: (qmail 21257 invoked by uid 50004); 12 May 2004 05:14:32 +0000 Mailing-List: contact gentoo-portage-dev-help@gentoo.org; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail Reply-To: gentoo-portage-dev@lists.gentoo.org X-BeenThere: gentoo-portage-dev@gentoo.org Received: (qmail 3645 invoked from network); 12 May 2004 05:14:32 +0000 In-Reply-To: <40A193B5.9080206@skylineaero.com> References: <40A193B5.9080206@skylineaero.com> Mime-Version: 1.0 (Apple Message framework v613) Content-Type: text/plain; charset=US-ASCII; format=flowed Message-Id: <3F00C422-A3D3-11D8-9EB9-0003938E7E46@gentoo.org> Content-Transfer-Encoding: 7bit Cc: Pieter Van den Abeele From: Pieter Van den Abeele Date: Wed, 12 May 2004 07:14:29 +0200 To: gentoo-portage-dev@lists.gentoo.org X-Mailer: Apple Mail (2.613) Subject: Re: [gentoo-portage-dev] building dependency tree X-Archives-Salt: 3db6dc23-5507-41b8-8ff2-f2f578702640 X-Archives-Hash: d6040491a29d2005e51f774aaf817e86 On 12 May 2004, at 05:02, Andrew Gaffney wrote: > and then the list of packages to emerge A topological ordering on the relevant digraph. The relevant digraph as computed by portage is a 'tree' (note: cycles filtered) which is created by performing a (series of) walk(s) in the graph (portage "tree"). Dependencies = edges, for each ebuild there are 2^n (where n = number of USE flags in the ebuilds IUSE) choice nodes in the graph. I believe a DFS and BFS strategy have been suggested for the walk on this list, each having their own advantages and disadvantages. The main issue with the search strategy used by portage is that the runtime complexity explodes when you try to implement stuff like 'package foo conflicts with package bar' (the best we can do is without causing the explosion is: package foo version X conflicts with package foo version Y (same package - different version - 'slot' functionality). Of course there are solutions to this problem, but those fall outside the scope of your question :-) Best regards, Pieter Van den Abeele -- gentoo-portage-dev@gentoo.org mailing list