Report on personal contribution to deity
Hi,
When I joined the Deity team, I made a commitment to keeping
the membership at large informed about things happening behind the
scenes, as it were, at least as far as I'm concerned. This is less
important now than it was then, since the deity list has been opened
(the digest version, that is), and interested people can follow the
nitty gritty details. However.
After a hiatus (due to a month from hell with moving into a
new house and the renovators running behind schedule), I am back in
the saddle, and have been discussing data structures for performing
the ordering of packages tagged for purge/removal and packages meant
to be installed/upgraded. In order to nail down the data structures,
I have to settle on an algorithm for a topological sort, and I have
the two most common methods outlined below, with twists for handling
pre-dependencies (I have yet to incorporate configure now! directive,
as well as removals)
Any comments appreciated.
======================================================================
Algorithm a: (for packages being installed, removal is similar)
# First generate the indegree of all package-versions
1 For each package-versions which are candidates for installation; do
2 for each dependency, predependency, and packages we are
replacing, and, optionally, packages that have recommended or
suggested us. set indegree
3 package::indegree++;
4 done
5 done
6 For each package-versions which are candidates for installation; do
7 if indegree == 0; then
8 push on todo list
9 endif
10 done
If there is nothing in the todo list, we had a cycle!! (handle
it)
11 while there is a todo list; do
12 pop package off a to do list
13 if we are in uncleared predependent list; then
14 insert a break in processing marker on ordered list
15 clear uncleared predependent list
16 endif
17 push onto ordered list
18 remove from candidates list
19 for each target (reverse dependencies!) of depends and
predepends, and packages we suggest or recommend
20 reduce indegree of target
21 if indegree of target == 0;
22 push target on todo list
23 endif
24 done
25 done
26 If not empty candidates list; there is a cycle!
======================================================================
Algorithm B: Depth first search. (again, for packages being installed)
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
======================================================================
What I like about algorithm B is that it is simpler to code
(but not by much), what I like about the first is that one has some
determination in how to break the cycle (search for the node with
minimum indegrtee, and snip a link, preferably a suggests link or a
recommends link). In the second algorithm one just follows predepends
first, then depends, and so on, and hopes for the best about cycle
removal.
Also, the second method does not call for reverse dependencies
as algorithm one does.
manoj
--
"I hate the itching. But I don't mind the swelling." new buzz
phrase, like "Where's the Beef?" that David Letterman's trying to get
everyone to start saying
Manoj Srivastava <srivasta@acm.org> <http://www.datasync.com/%7Esrivasta/>
Key C7261095 fingerprint = CB D9 F4 12 68 07 E4 05 CC 2D 27 12 1D F5 E8 6E
--
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: