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: