[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: Package ordering update: Handling Pre-dependencies



Hi,

>>"Kai" == Kai Henningsen <kai@khms.westfalen.de> writes:

Kai> srivasta@datasync.com (Manoj Srivastava) wrote on 24.04.97 in
Kai> <87hggvokfn.fsf@tiamat.datasync.com>:

>> Does anyone have any improvements to suggest?

Kai> In general, you'll get minimal breaks if you try to move
Kai> pre-depended on packages as early as possible, and pre-depending
Kai> packages as late as possible.

Kai> However, I'm not quite sure how to do that in the ordering step,
Kai> mostly because I haven't seen the algorithm. You'd have to do
Kai> something like, when two packages are candidates for the same
Kai> position (don't have a dependency on each other, not even
Kai> indirectly), then if one is a pre- dependency target, move it
Kai> first, or, if one is a pre-depending package, move it last.

	The pkg-order package uses tsort to to the topographic
 sorting, so we do not have access to the algorithm used for deadlock
 breaking. The only way to change the order produced would be to add
 links, but it is tricky doing that without the risk of introducing
 cycles or incorrect links in the graph; that is why I chose to post
 process. 

Kai> After doing any type of order, your method seems right to
Kai> actually find the minimal breaks for that order - it puts off
Kai> breaking as long as possible.

Kai> The reverse would also work, of course - go through the list from
Kai> right to left, and break when you encounter a package that's in
Kai> the pre-depends of one you already processed.

	Gak! I did not think of this, this is of course correct, and
 does not need the package to record any extra data. Unless I can come
 up with a need to record reverse dependencies (required by the method
 I proposed), I think I will go through the list in reverse order,
 just as you suggest.

	manoj
-- 
 Fast cars, fast women, fast algorithms... what more could a man want?
 Joe Mattis
Manoj Srivastava               <url:mailto:srivasta@acm.org>
Mobile, Alabama USA            <url:http://www.datasync.com/%7Esrivasta/>


--
TO UNSUBSCRIBE FROM THIS MAILING LIST: e-mail the word "unsubscribe" to
debian-devel-request@lists.debian.org . 
Trouble?  e-mail to templin@bucknell.edu .


Reply to: