[Gllug] Finding the best options in Debian

[salsaman at xs4all.nl]

> On Wed, Jun 29, 2011 at 10:10:46PM +0100, Chris Bell wrote:
>> Hello,
>>    I am trying to find the best combination of ZoneMinder, package
>> dependencies, and desktop on a dedicated machine. In theory a desktop is
>> not
>> a dependency as long as the output web pages can be monitored somewhere,
>> although it may be needed in some circumstances. There is a fairly long
>> list
>> of package dependecies, although some may be met by any one from a small
>> number, while some of those listed may not be used together. One way
>> would
>> be to obtain (from where?) the huge list of packages in each desktop
>> variety
>> and then compare with the list from zoneminder, but is there another
>> way?
>>    I am starting by installing Debian, then ZoneMinder
>>


You can solve this with graph theory, but unfortunately it may take
exponential time to run. First put zoneminder as the top node of your
tree. Next sort all of the dependencies from those with smallest number of
alternatives to those with the greatest. Now add the dpendencies as nodes
to the tree, branching whenever you have a choice.

So suppose we have Z and dependencies A,B,C1,C2,D1,D2,D3. You would get a
tree Z->A->B which then branches to C1 and C2 each of which branches to
D1,D2,D3.

Next, return to A, and find its dependencies (say E, F1,F2,F3). Look at
the tree from the root to the node before the next branching point (in
this case, B). If you find anything which conflicts with an existing node,
either remove it as a choice, or if their is no choice, remove that branch
from the tree. Eliminate anything from your list which already exists, or
if it is one of a set of alternatives replace it with a special nil node
(which means branch but dont install anything). If all alternatives are
nil, then that choice set can be removed.

The remaining list are now dependencies of B. If B were a leaf node, we
would just add them, otherwise we do a depth first search down C1 and C2
(a recursion). Once that is done, you can backtrack to B (the node after
A) and repeat the process for B's dependencies. Then you need to follow
each branch C1 and C2, etc.

Running time is hard to calculate, but you can see in a worst case
scenario you would traverse the entire tree for each dependency (which
could come up multiple times) checking for duplicates and conflicts. So if
the average number of dependencies is x then we would do order n.x
comparisons with n nodes i.e (n²) comparisons. This is fine if the branch
length is long, but consider each time you have a choice you can branch at
least two ways. So after just 16 sequential choices you would have > 64k
branches. So it would be worthwhile maybe pruning the tree by selecting
some choices and discarding others, particualryl early on in the process
and where there are a large numer of choices (> 2) in the set.

Regards,
Salsaman.


Your final graph will be a tree. The branch with least nodes will be

--
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug