Re: Report on personal contribution to deity

[Raul Miller <rdm@test.legislate.com>]

Manoj Srivastava <srivasta@datasync.com> wrote:
> 	Any comments appreciated. 

Forgive me, but I just skimmed over your post.  I think I'd want
to isolate the topological sort from the grungy details of
what the topology represents.

A topological sort may be obtained by transitive closure on
dependencies. Here's a fairly trivial algorithm (at the expense of
O(n^2) memory, and O(n^3.5) time:

create an NxN bit matrix, if bit[packagea][packageb] is set, then
package b must be installed for package a to be installed.

int h, i, j, k, l= 1+sqrt(N);
for (h=0; h<l; h++) {
        for (i=0; i<l; i++) {
                for (j=0; j<N; j++) {
                        for (k=0; k<N; k++) {
                                bit[i][j]|=bit[i][k]&bit[k][j];
                        }
                }
        }
}

To assign numerics, just add up along last dimension (and install in
that order).

You can get better memory use for the typical case by representing
dependencies on a linked list. Here, you get one list per package
(corresponds to first dimension in bit matrix -- presence of a package
in list corresponds to 1 in the second dimension). bit[x][y] becomes
ismemberof(x, y), and |= becomes addifnotpresent(). To assign numerics
you count how many are on list.

[Alternatively, you can get an 8x space improvement by using packed bits
and a slightly more complicated indexing scheme, dunno if that's worth
it if we're heading towards multi-thousand package installs].

The depth-first algorithm is probably the most sparing on memory
[just need linear space to catch loops], but unless you adopt some
representative data structure you'll wind up continually analyzing
package descriptions to extract dependencies. This seems like it could
get rather slow... [that's off the cuff, I've not thought about this one
very seriously].

--
Raul


--
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 .