Apparently, Pascal Terjan recently wrote: >> * do install of package by groups which are shorter as possible >> (apt-get >> like) > Would be nice. Good luck for an optimized algorithm :)
Okay, just a little discussion on this, because I really would like this as well! =) Anyway, it's not really that *much* harder than what "make" does; you just build then traverse a DAG... just... in urpmi's case... it's not always a DAG (sometimes there ARE cycles). But that's okay. For instance, say I want to installed package "A". Say the dependancies look like this: Package: Dependancies A: B C D B: C E F C: D: F B E: F: B (oh no, a loop!) So, I go: $ urpmi A Right now it says, ah, A needs B, C, and D. B needs C (already in the list) E, and F. C doesn't need anything; great! D needs F and B (oh! already in the list, too). E needs nothing; good. F needs B (it's already in the list; yeah, it's going to be a loop, but self-consistancy is maintained, and everyone is happy); sweet! The following packages are going to be installed: A B C D E F (or whatever order it shows in) urpmi then installs them all, supposedly in a nice correct order (I don't doubt it's correct--I just haven't ever looked at how it does it currently ;). Instead, what urpmi could do is the following (and maybe it already does some of this internally--if so, hey! less work!) $ urpmi A urpmi builds a nice DAG like this by discarding edges for any reference that goes to a node we've already seen. A -> B A -> C A -> D B -> C (discarded) B -> E B -> F D -> F (discarded) D -> B F -> B (discarded) Now use djikstra's longest-path or something similar (there are more advanced algorithms); and you get the following (possible) ordering: C E B D F A Now, urpmi can run, conceptually (no new dependancy calculation is necessary) the following: urpmi C C ################ [100%] urpmi E E ################ [100%] urpmi B B ################ [100%] urpmi D F ################ [100%] D ################ [100%] urpmi F (everything is already installed) urpmi A A ################ [100%] Yeah, it's not going to get the perfectly smallest subsets when there are cycles. But it in real practical use for RPMs it's *going* to generally find lots of small subsets, even if they're not optimal, with very little processing overhead. Wes
