Re: toppological sorting and datastructures
On 13 Nov 1997, Manoj Srivastava wrote:
> Hi,
> >>"Jason" == Jason Gunthorpe <jgg@gpu.srv.ualberta.ca> writes:
>
> Jason> On 13 Nov 1997, Manoj Srivastava wrote:
>
> Jason> It's not so bad to build, it just means I need to add another
> Jason> structure which is a bit of work. Also consider the size
> Jason> impact, their is going to be > 2000 of these new items, there
> Jason> are only 3000 dependancies though! With 3000 deps and 1000
> Jason> packages that is an average of 3 deps per package, I know some
> Jason> have more, ie 10. I'm not convinced any speed concerns can be
> Jason> applied here.
>
> I don't understand. Why are there going to be >2000 new items?
> Are you talking about linked list headers?
Yes I am talking about linked list headers. What you propose would cause
there to be around 5000 structure instances devoted to dependancy
handling, an increase in side of approximately 50K (13% bigger!)
> Speed concerns: Applying a list selection function, runs
> O(|V|), applying an function for all members of the long list
> is O(|V| + |E|). As |E|>|V|, there is some extra overhead (whether it
> is significant ot not is another matter; since the constants involved
> are totally different). (this is not a very telling argument)
Do you want to know the real numbers? :> I can get them!
> ======================================================================
> Algorithm B: Depth first search.
>
> 1 For each package-versions which are candidates for installation; do
> 2 Color each node white
> 3 done
>
> 4 For each package-versions which are candidates for installation; do
> 5 if color of node is white; then
> 6 Visit (Vertex)
> 7 endif
> 8 done
>
> Visit:
> 9 color node Gray
> 10 for each dependency, predependency, and packages we are
> replacing, and, optionally, packages that have recommended or
> suggested us.
> 11 if dependency is predepends,
> 12 add node to list of predepends
> 13 endif
> 14 if color of dependency is white (else this was a cycle!)
> 15 visit (dependent)
> 16 endif
> 17 done
> 18 if we are in the list of predepends
> 19 add a break event on the ordered list
> 20 endif
> 21 add node to order list
> ======================================================================
This is unbelivably simple to code! You don't need any lists but a single
package extension structure containg the colour of the package. It's also
amazingly fast, the only loop is the main one. The other one requires a
reverse depends lookup, which requires iterating over all packages
depending on the package, even if it is not a cand.
However, it's recursive, will the depth cause a problem for us? I suppose
I should go and calculate the worst case depth of the routine (tomorrow
I'll write a stats report into dpkg-cache)
> Provides should satisfy any non versioned dependency (I think
> provides should only provide virtual packages, but I'm not
> sure this is ever required anywhere)
Um, we are implementing enhanced provides, they have versions and can
match versioned depends with the 'provides' version. Tom wants this.
I guess a provided targeted depends simply effects more than one package.
Jason
Reply to: