[prev in list] [next in list] [prev in thread] [next in thread] 

List:       mandrake-cooker
Subject:    Re: [Cooker] Analysis of Relation Loops
From:       Gustavo Niemeyer <gustavo () niemeyer ! net>
Date:       2005-03-24 15:23:53
Message-ID: 20050324152353.GD6931 () burma ! localdomain
[Download RAW message or body]

Greetings Guy,

> > I've just finished an analysis of relation loops in the current
>
> Just FYI, in graph theory such a loop is called a cycle. (This is also
> a hint that one can use graph theory, if you haven't done already, for
> cycle detection in a dependency tree, which is a directed graph. :-)

There's a lot of graph theory applied in Smart Package Manager
(http://smartpm.org), which is the tool used to generate this
information.  If you like graphs, you'll find many interesting
aspects inside it, like the topological sort with optional 
disjunction groups and cycle breaking on optional relations. The
transaction system is also a neat case of optimization on graph
navigation to avoid combinatory explosion on this specific
problem domain.

-- 
Gustavo Niemeyer
http://niemeyer.net

[prev in list] [next in list] [prev in thread] [next in thread]