On Thu, Oct 21, 2010 at 05:04:46PM +0300, Igor Vlasenko wrote:

IV> Денис, вы наверное, не вникли в суть.
IV> Эта утилита на сортирует не последовательность,
IV> а множество, т.е. несортированный объект.
IV> Она его сортирует по транзитивному замыканию частичной упорядоченности,
IV> которое ей подают на вход.

Угу, я хотел уточнить, что вариантов сортировки может быть множество. К
примеру:

a -> b
a -> c
c -> d

В каком порядке собираем?

Очевидно что a собирается последним. Но мы можем собирать так:
d, c, b, a
можем:
b, d, c, a
можем:
d, c, b, a
можем:
d, b, c, a

Но очевидно что в самом начале должны быть собраны пакеты d и b, но в
любом порядке. Таким образом результат сортировки моим алгоритмом будет
выглядеть так:
>>> stage 1
b
d
>>> stage 2
c
>>> stage 3
a


Такая схема не дает всей полноты картины, ибо не показывает варианта, к
примеру, d, c, b, a. Однако если мы выполнив любое из заданий в stage 1
запустим алгоритм снова, то он уже покажет что прямо сейчас мы можем
собрать не нарушая зависимостей.

Это крайне удобный подход если мы хотим выполнять какие-то задачи
параллельно, а также если работа ведется параллельно. Это позволяет список
из stage 1 просто опубликовать со словами "соберите кто-нибудь срочно,
пожалуйста", и далее множество людей может параллельно собирать свои
пакетики :)

IV> В результате выйдет уже сортированная последовательность --
IV> это уже то что вы ищете.

Почти :)

IV> Что может смутить, что утилита не понимает строковый ввод,
IV> т.е. вместо пар 
IV> libfoo < libbar
IV> на вход надо подать кодировку - число.

Это не страшно. Кстати почему числа? Моей алгоритм хотя дает столь же
верный результат это пара десятков строчек на перле.

>> При этом вариантов конкретной последовательности для данной задачи --
>> очччень большое число.
IV> посортировать, например, строки в лексикографическом порядке,
IV> (по алфавиту). и получится кодировка - номер строки в списке.

Как закодировать строки в числа я знаю, честно-честно :)

А мой алгоритм туп как пробка.

1. Делаем хэш. Ключ -- имя пакета, значение -- массив зависимостей.
2. Пробегаюсь по списку ключей хэша, повторяем пока этот хэш не пустой
2.1. Для каждой зависимости -- если отсутствует в хэше пакет с таким
именем -- удаляю зависимость.
2.2. Если у пакета нет зависимостей -- мы его можем отправить на сборку
2.3. Если мы отправили пакет на сборку -- удаляю ключ с его именем из хэша
2.4. Если в этот цикл мы не смогли собрать ни одного пакета (хотя они
есть), значит где-то кольцо. Весь остаток выводим как есть, пущай
пользователь разбирается.

Собственно и все :)

-- 
С уважением, Денис

http://mithraen.ru/
----------------------------------------------------------------------------