Re: toppological sorting and datastructures
Hi,
>>"Jason" == Jason Gunthorpe <jgg@gpu.srv.ualberta.ca> writes:
Jason> On 13 Nov 1997, Manoj Srivastava wrote:
>> b) adjacency list: This is an array (or linked list) of length
>> |V|. Each node is the head of a linked list of dependencies. I
>> think this is already how the backing store is represented (except
>> that we have multiple kinds of dependencies, each of which gets a
>> linked list (I think)
Jason> Check the cache.sgml on the last point there, the depends get
Jason> dropped into a single big linked list. You might as well use
Jason> all of the depends data in the ordering, with varying degrees
Jason> of strictness. A package that suggests another package should
Jason> 'gently try' to install itself first. Remember, an important
Jason> goal is to have predictability in the algorithm.
I was initially thinking of just using the Pre-depends and
Depends data, since these are the ones strictly required, and maybe
have recommends and sugggests turned on by user request (hoping to
avoid cycles, since cycles destroy the ordering invariants).
However, you seem to suggest that if A suggests B, A should
install before B? By contrsts, if C depends on D, D is installed
before C. I can see the rationale for your statement, but that means
that we have to put in code for traversing these lists of
dependencies which looks at *each* node, since various kinds of
dependencies are munged into one list.
I'd be happier if all these dependency types were in separate
linked lists, so I don't have an overhead for each node of the linked
list. The advantage of having one linked list is that one does not
need to modify the structure if a new kind of dependency comes up
(however low the probability of that is), however, we can have a
linked list of headers of linked lists, and can tack on another
linked list as we please.
_________
| |
| pkg a |---...
|-------|
| |
| pkg b |---...
|-------| |------| |------| |-----| |-----|
| | | | | pre | | | | |
| pkg c |------------|depends----| |---|recom|--|sugge|--...
|-------| | | |depends | | | |
| | |------| |------| |-----| |-----|
| ... |---... | dep 1| |dep 1 | |dep 1| |dep 1|
|-------| |______| |______| |_____| |_____|
| pkg n |---... | dep n| | dep n| |dep n| |dep n|
--------- |______| |______| |_____| |_____|
Also, the direction of the edge for recommends and suggests is
opposite the direction of the edge for depends and predepends, and
conflicts aren't used in ordering, except that conflict-and-replace
implies a relationship.
Jason> b) looks like fairly simple. First off, there is an important
Jason> distinction. You are not working with packages, you are working
Jason> with -versions-.
Right. As I mentioned later in my email, Package name, Package
version, and optionally, source and architecture, shall uniquely
identify a vertex.
Jason> So I can give you a list of versions to install, a list of
Jason> versions that are installed and a list of versions that could
Jason> possibly be installed if you really wanted to. Note that there
Jason> can be multiple versions to be possibly installed for each
Jason> package and so on.
Umm, The list would have to be pruned so that only one version
per package would be a candidate prior to the ordering step. What
criteria do we use to select the preferred version? The one with the
highest version, as described in chapter 5 of the packaging manual?
It would also be helpful to have a list of currently installed
packages (also need to check if a version is installed more recent
than the best candidate)
>> The list of packages that have to be ordered are the candidates for
>> installation, so I shall need a list of candidates separately from
>> the list of all known packages. It would also be nice to have a
>> list of installed packages (and what the heck, a list of packages
>> to be removed)
[code munched] I guess this answers my question about constructing
lists on the fly.
Jason> Taken from bits of pkgtreeitem.cc
Jason> Tada, list of versions to be removed. Similar iterations are
Jason> used to generate other forms of lists. I'm trying to come up
Jason> with an iterator scheme, but nothing so far. The crazy syntax
Jason> is to support the readonly memory map of the cache file.
>> What I need are some kind of a separate index/list. The operations
>> it wouls have to support are does package X belong to list? for
>> each package that belongs to list X do {} I have used an efficient
>> RB-tree implementation to simulate a set in the past. If there are
>> indices in the cache generator that fit the needs, then I'll gladly
>> forego writing the tree ;-)
Jason> If you really need 'member of set' then this is a job for the
Jason> extension structures, it will be many times faster and easier
Jason> to use that sort of scheme then to use a RB tree. Also,
Jason> depending on the nature of the data you are deriving it may
Jason> already be present in the cache, ie it is trivial to tell if a
Jason> version is marked for removal (see above). It is similary
Jason> trivial to tell if a version is marked for install or upgrade.
That sounds good. How about search for a package, and test the
version number, like, if I want to know if the version installed
matches (>>2.1.10)? A linear search could get tedious.
manoj
--
"Well, well, well! Well if it isn't fat stinking billy goat Billy
Boy in poison! How art thou, thou globby bottle of cheap stinking
chip oil? Come and get one in the yarbles, if ya have any yarble, ya
eunuch jelly thou!" Alex in "Clockwork Orange"
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
Reply to: