site
contact
newswoofV topological sort
If you have ever used Woof, the Puppy-builder, or even as a user of Puppy, you may be familiar with /root/.packages/woof-installed-packages. Or, in recent Woof-CE-built pups, it is at /var/packages/woof-installed-packages.
This has a list of the packages that are "builtin", in "Puppy DB" format. By builtin, that means that are in the SFS(s); in the case of EasyOS that is 'easy.sfs'. Here is an example of one line in that file:
argon2-20190702_3|argon2|20190702|3|Personal;lock|16K|current|argon2-20190702_3.x86_64.xbps|+glibc|Password hashing function|void|current||
Alright, here is another package, that has more dependencies:
alsa-utils-1.2.10_1|alsa-utils|1.2.10|1|BuildingBlock|1279K|current|alsa-utils-1.2.10_1.x86_64.xbps|+alsa-lib,+glibc,+libfftw,+libsamplerate,+ncurses-libs|Advanced Linux Sound Architecture (ALSA) utilities|void|current||
In woofV, I am building easy.sfs by installing each package in woof-installed-package into a folder named 'rootfs', then using the 'mksquashfs' utility to create easy.sfs.
What is different from WoofQ, is that woofV is installing each package using the XBPS package management utility 'xbps-install'. When a package is installed, 'xbps-install' will automatically install any dependencies. To get more control over this, I would like to install packages in order of dependencies.
In the case of 'alsa-utils', I want to first install 'alsa-lib', 'glibc', 'libfftw;, 'libsamplerate' and 'ncurses-libs' -- but they also need to be installed in order of dependencies. So, for the last few days, I have been trying to sort 'woof-installed-packages' into order of dependencies. Which is very difficult.
I had a little algorithm, extremely slow, but it didn't work. The problem I hit, that killed my algorithm, is that several packages in the Void repository have circular dependencies. That is, package 'A' has dependency 'B', and package 'B' has dependency 'A'.
After much puzzling, I discovered that a topological sort will do the job. This is explained on Wikipedia, but be warned, your head might hurt trying to understand it:
https://en.wikipedia.org/wiki/Topological_sorting
The 'coreutils' package has a utility 'tsort', as also does busybox. However, the busybox one threw a fit over the circular dependencies. The 'tsort' in 'coreutils' gracefully handles the circular deps, using perhaps random choice which one to install first.
I have written two scripts. Firstly, 'findwoofinstalledpkgs', which generates 'woof-installed-packages' and 'devx-only-installed-packages':
Then wrote 'sort-dep-order', which applies the topological sort and generates 'woof-installed-packges-dep-order':
woofV development is moving at a glacial pace, as it is a
complete rewrite relative to previous Woofs.
Tags: easy