This is the mail archive of the cygwin-apps mailing list for the Cygwin project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]