This is the mail archive of the
cygwin-apps
mailing list for the Cygwin project.
Re: New Setup for Cygwin 1.7 on cygwin.com
On Aug 27 15:07, Ralph Hempel wrote:
> Corinna Vinschen wrote:
>
>> I looked a while into the algorithm doing the dependency ordering. What
>> it does is to create an ordered list sorted by using the algorithm to
>> find the strongly connected components in a directed graph. The problem
>> is that this algorithm works fine and creates a nice dependeny ordered
>> list unless there are loops in the dependencies. In this case you just
>> get a list of strongly connected components in arbitrary order.
>
> <SNIP>
>
>> Anybody having another funny idea?
>
> What about detecting a dependency loop by checking to see if the next
> package in the dependency list is already in the list. If there's a loop
> then stop.
Dependency loops are already detected, just the result is less than
desirable. It's a stadard problem of loops in directed graphs. There's
no way to create a topological sort order and the result of any sort
algorithm is basically not determinate. So you have to put some
additional heuristic into the algorithm to get a sort order you desire.
Corinna
--
Corinna Vinschen Please, send mails regarding Cygwin to
Cygwin Project Co-Leader cygwin AT cygwin DOT com
Red Hat