> The graph is not acyclic.
Hi Mac,
That is true. The scripts would need to check for cycles and either bail
out to admit manual treatment, or automagically call upon "special cases".
Ideally, the latter, once the basic idea is admitted as feasible. This
could be implemented as follows:
1. When developing a set of Package User scripts to be released in
conjunction with the latest {,B,JHA,C}LFS book, scan the dependency graph
for cycles. This can be done using Tarjan's algorithm in O(V+E) time,
where V and E are the respective vertex and edge numbers.
2. Each detected cycle can be "shrunk" to a so-called pseudonode. This can
be done recursively until the graph is directed-acyclic, i.e. a DAG.
3. Pseudonodes in the final DAG can then be associated with scripts that
resolve the circular dependencies.
It would take work the first time, but then each pseudonode script would
only need testing and a bit of reconfiguring - not a total rewrite - with
each update to the book. And once one person has it working, it will be
available for download by anyone who wishes to use this system. This would
be especially expedient if there were a package users wiki.
Cheers,
Tim
--
http://linuxfromscratch.org/mailman/listinfo/lfs-support
FAQ: http://www.linuxfromscratch.org/lfs/faq.html
Unsubscribe: See the above information page
