Re: toppological sorting and datastructures
On 12 Nov 1997, Manoj Srivastava wrote:
> Hi,
>
> Algorithms:
> I have been reading up on directed acyclic graphs and
> topological sorting. There are two methods to do the sort that I can
> see
Sounds most interesting, a topic I certainly know very little about ;>
> a) Do a depth first search, printing out the node name after
> traversing the children (so each node occurs after all the
> dependents are listed; and reverse the order when printing)
> Algorithms [Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest]
> Algorithms in C [Robert Sedgewick]
>
> b) Look att all node with no dependencies, list them in any order,
> for each node listed, look for dependent packages and decrement the
> dependency count by one. repeat for all 0 order nodes after
> decrementing.
> Algorithms [Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest]
> Discrete Mathematics and its applications [Kenneth H. Rosen]
>
> Both algorithms can work in O(V+E), where V is the number of
> nodes (packages), and E is the number of edges (dependencies). (I'm
> still struggling with an exercise in Algorithms [Thomas H. Cormen,
> Charles E. Leiserson, Ronald L. Rivest] which suggests that one may
> determine cycles in an undirected graph using an O(V) algorithm).
Hm, I'm not sure if effeciency should be a major concern here. My main
worry would be expandability for future issues.
> Representation:
> Since the number of dependencies for any package are far less
> than the total number of packages, an adjacency list would be far
> more efficient way of representing the graphh. This is already very
> close to the data structure we use.
Tell me, what exatly do these algorithms use for an internal
representation while they are running? It sounds to me like some form of
N link tree.
> If we also construct the reverse depndency list in the backing
> store (cached list), then determining strongly connected regions
> becomes easier, since the reverse dependencies form a transposed
> directed graph of the original graph. Or else we may use tarjans
> variation of the depth first search to find strongly connected
> regions.
The reverse dependancy list is already constructed. It's a linked list of
of all dependancies which point to the package. The dependancies have a
pointer to their owning version and the owning version has a pointer to
the owning package.
> For dependency checking, we would need to have lists of
> packages installed, packages available, and packages which are
> candidates for installation.
This is easially generated by running over the whole package list, the GUI
does it when you change display modes.
> We would need to have ways of determining is a package is a
> member of a list, and cycle over all packages in a list,
> efficiently.
>
> My initial proposal is to create a data structure that
> contains pointers to the cached data (backing store, I mean), where
> lookups and traversals are cheap. My candidate for this is a
> Red-Black tree.
What exactly are you going to look up in the RB tree? Most information I
can think of that would fit into such a structure is already effeciently
indexed by the cache generator.
Also, I have worked out an effecient way for us to attach an arbitrary
data structure to the items in the cache which may prove usefull for this.
Jason
Reply to: