Re: toppological sorting and datastructures
On Fri, 14 Nov 1997, Roman Hodek wrote:
> 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.)
Well, we already have generated real reverse dependancies, so I'm not sure
this is a problem..
> > Algorithm B: Depth first search.
> 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...
I think the last item (during the add to list) is also supposed to colour
the node black to mark that it is done. White means it's free, grey is
thinking about being added and black is already added. So long as you
never have a white -> grey link (circle) the algo will work okay, I think
;> (It's 5am, we just had a fire alarm, I hate my life :P)
> 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!
Heh, just don't expect to see it parsed from the status file. We can't
actually initiate change, only be ready for it. Until dpkg supports it I
won't parse it.
Jason
Reply to: