Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Category:

Задачка "на графы"

Есть у нас граф зависимостей дистров. Узлы - дистры, дуги - зависимости. Зависимости бывают обязательными и опциональными. Подграф, содержащий только обязательные зависимости - это DAG (нет циклов). А так циклы есть.

Есть установщик дистра, по дистру устанавливающий все достижимые из него обязательные зависимости.

Написать функцию, которая по списку дистров вернет скрипт установки всех обязательных и опциональных зависимостей этих дистров. Скрипт - это другой список дистров, которые последовательно передаются установщику и он ставит (в правильном, т.е. топологическом, порядке) все транзитивные обязательные зависимости каждого переданного дистра.

Валидный скрипт - это скрипт, в котором если А зависит от Б - то А ставится раньше, если только Б также не зависит от А (то есть нет цикла). В-общем в обычном порядке топологической сортировки, за исключением того что надо хендлить циклы.

Лишние дистры, понятно, ставить нельзя.

Надо найти минимальный валидный скрипт для данного списка. Их может быть более одного :)

Пример (=> - обязательные зависимости а -> - опциональные):

Foo => Bar -> Baz
Baz => Quux

Минимальный скрипт установки всех 4 пекеджей - это [Baz, Foo]

А вот вам риал-лайф граф: https://gist.github.com/nponeccop/0d4df7839d73f9b960a1dda51fd0d380

Upd: вариант со звёздочкой - учитывать поломанные дистры. То есть нашей функции передается ещё и список поломанных дистров. И задача - не собирать все пекеджи, у которых один из поломанных пекеджей является обязательной транзитивной зависимостью.
Tags: fp, programming
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments