New Setup for Cygwin 1.7 on

Corinna Vinschen
Thu Aug 28 07:42:00 GMT 2008

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 Vinschen                  Please, send mails regarding Cygwin to
Cygwin Project Co-Leader          cygwin AT cygwin DOT com
Red Hat

More information about the Cygwin-apps mailing list