Re: toppological sorting and datastructures
Hi,
The data structures used for most graph algorithms is either:
a) Adjacency matrix. Suppose the graph has V nodes and E edges. The
adjacency matrix is a |V| x |V| array, with Ai,j = ! if an edge
exists from vertex i to vertex j (or, in other words, it has a |E|
non null elements). This representation is good for dense arrays
(lots of edges). In our case, Vertexes are packages, and
dependency relations are edges, and the matrix is quite sparse.
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)
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)
What I need are some kind of a separate index/list. The
operations it wouls have to support are
a) does package X belong to list?
b) 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 ;-)
It would be nice to be able to construct a list on the fly
(list of all packages which pre depend on others and thus mark the
end of a run for dpkg; pre-dependees and pre-dependent packages are
installed on separate runs of dpkg). I can use the same
infrastructure to build the final ordered list too.
I'd need the data structure that can be added to the backing
store (coloring nodes during an ordering run, for example).
manoj
ps: actually, package name, version, and optionally, source and
architecture determine a vertex, if one is to be pedantic.
--
"Neurotic: Self-taut person." Author Unknown
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: