Re: toppological sorting and datastructures
Hi Manoj!
I don't know what's going on exactly in Diety, but some little
notes...
> Algorithm a: (for packages being installed, removal is similar)
[...]
> 19 for each target (reverse dependencies!) of depends and
> predepends, and packages we suggest or recommend
Why are these reverse dependencies? To get the target of a
depends&Co., just follow the edge in the graph... Is there any
additional work to do for this?
And, BTW, if you need to work always with reversed dependencies, i.e.
just turn around all the edges in the graph, it's maybe more efficient
to leave the edges as they are and just reverse the resulting ordered
list. (Or, even better, built the list already in reverse order.)
> Algorithm B: Depth first search.
[...]
Does that really work? Consider this example graph:
A ----> B -----> C (i.e., A depends on B and C, B depends on C)
| ^
| |
+----------------+
If your depth-first alorithms, which non-deterministically chooses
which node to visit first and which dependency to visit first, chooses
the following order of things, that happens:
- visit A, a is white
- color A gray
- follow A->C edge, visit C
- color C gray
- no more edges, add C to list (list now: C)
- follow A->B edge, visit B
- color B gray
- follow B->C edge, visit C
- color of C is already gray => you assume a cycle
But there's no cycle in the example above, just a direct and one
indirect dependency of A on C...
Jason> Um, we are implementing enhanced provides, they have versions and
Jason> can match versioned depends with the 'provides' version. Tom wants
Jason> this.
In the past, I always argued that versioned provides are a good
thing... :-) Fine!
Roman
Reply to: