On Thu, Aug 31, 2006 at 01:01:06AM +0400, Alexey Tourbin wrote:
> > Далее, имея граф зависимостей между пакетами, необходимо каким-то
> > образом определить минимальный набор вершин, пути, исходящие из
> > которых, покрывают все вершины графа.  При отсутствии циклов эта
> > задача решается очень просто - достаточно найти вершины, в которые не
> > входит ни одно ребро (пакеты, которые не зависят от других пакетов).
> > Если же в графе есть циклы, каждый цикл нужно схлопнуть в одну
> > вершину, затем, когда в графе не останется циклов, определить нужный
> > набор вершин; если в этот набор попали вершины, полученные из циклов,
> > для них можно выбрать любой пакет, входивший в цикл.
> 
> Топологическая сортировка, кажется, решает эту проблему.
> Пусть есть список пакетов, отсортированный топологически: пакеты в
> начале списка требуют пакеты, которые находятся ближе к концу списка.
> 
> Тогда можно применить что-то вроде решета Эратосфена, которое
> используется для просева простых чисел.  Берем элемент списка и
> вычеркиваем все *последующие* элементы, которые к нему сводятся.
> Но не просто вычеркиваем, а как бы зануляем, чтобы уже вычеркнутые
> элементы сохранились для последующих вычеркиваний.  Тогда на выходе
> должен остаться список пакетов, которые не сводятся друг ко другу.

Вот скрипт, который использует топологическую сортировку + вычеркивание
как в решете Эратосфена.

$ cat ./optimize_package_list
#!/bin/sh -ef
. tmpdir.sh
cd $TMPDIR
rpm -q --qf '[%{REQUIRENAME}\t%{NAME}\n]' -- "$@" >qR
rpm -q --qf '[%{PROVIDENAME}\t%{NAME}\n]' -- "$@" >qP
awk '{print$2,$1}' qR |sort -u -k2,2 -k1,1 -o qR
awk '{print$2,$1}' qP |sort -u -k2,2 -k1,1 -o qP
#head -v qR qP
join -j 2 -o '1.1 2.1' qR qP |sort -u >p2p
tsort p2p >tsorted || [ -s tsorted ]
#head -v p2p tsorted
set -- `cat tsorted`
for i in `seq 1 $(($#-1))`; do
        eval master="\$$i"
        for j in `seq $((i+1)) $#`; do
                eval slave="\$$j"
                if grep -qs -Fx "$master $slave" p2p; then
                        #echo master=$master slave=$slave >&2
                        echo "$slave"
                fi
        done
done >extrareq
sort -o extrareq -u extrareq
awk '{print$1}' qR |sort -u >req
#head -v req extrareq
comm -23 req extrareq |xargs -r echo
$

У меня пока нет уверенности, что он до конца правильно работает,
однако "основные проблемы" в нём как будто не проявляются.

$ ./optimize_package_list glibc-core sh
sh
$ ./optimize_package_list perl-base    
perl-base
$ ./optimize_package_list perl-DateTime-TimeZone perl-DateTime     
tsort: p2p: input contains a loop:                                     
tsort: perl-DateTime
tsort: perl-DateTime-TimeZone
perl-DateTime
$

Очень прошу указать мне ситуацию, в которой скрипт лажается.