Към съдържанието
wannacode

Топологично сортиране

Накратко: Топологичното сортиране подрежда задачи със зависимости така, че всяка е след зависимостите си; алгоритъмът на Kahn го прави с опашка и разбира, ако има цикъл.

Проблем

Кой се строи първи

Онлайн магазинът е разделен на седем модула. core е общият код. db говори с базата и ползва core. auth пази входа на клиентите и ползва core и db. catalog, cart, payments и web стъпват на тях.

Инструментът за build трябва да компилира всеки модул след всичко, от което той има нужда. Ако строи cart преди catalog, компилаторът не намира класовете на каталога и спира.

Първото решение е редът да се пише на ръка в скрипт. Работи, докато някой не добави нова зависимост и не забрави скрипта. В голям проект модулите са стотици.

А ако auth започне да ползва нещо от web, който ползва cart, който ползва auth? Тогава всеки чака друг, и build е невъзможен. Трябва да го разбереш веднага и да знаеш кои модули са виновни.

Идеята

Граф на зависимостите

Модулите са върхове на насочен граф (виж представянето на граф). Пазим го като списък от съседи: за всеки модул, от какво има нужда.

needs = {
    "core": [],
    "db": ["core"],
    "auth": ["core", "db"],
    "catalog": ["db"],
    "cart": ["catalog", "auth"],
    "payments": ["auth"],
    "web": ["cart", "payments"],
}

Ред, в който всеки модул е след зависимостите си, се казва топологичен ред, а търсенето му е топологично сортиране. Има го само ако в графа няма цикъл.

Как се намира? Модул без зависимости може да се строи веднага. Щом е построен, за модулите, които го ползват, остава една зависимост по-малко. Числото „колко зависимости още чакат“ е входната степен (in-degree) на модула.

Това е алгоритъмът на Kahn:

  1. Преброй входната степен на всеки модул.
  2. Модулите със степен 0 влизат в опашка ready.
  3. Вземи модул от опашката и го сложи в order. На всеки, който го ползва, намали степента. Който стигне 0, влиза в опашката.
  4. Повтаряй, докато опашката свърши.

Виж го

Kahn отвътре

def build_order(needs):
    indegree = {m: len(deps) for m, deps in needs.items()}
    users = {m: [] for m in needs}
    for m, deps in needs.items():
        for dep in deps:
            users[dep].append(m)
    ready = deque(m for m in needs if indegree[m] == 0)
    order = []
    while ready:
        m = ready.popleft()
        order.append(m)
        for user in users[m]:
            indegree[user] -= 1
            if indegree[user] == 0:
                ready.append(user)
    return order

users е обратното на needs: за всеки модул, кой го ползва. Без него при всеки построен модул щеше да търсиш по целия граф.

deque от урока за опашки вади отпред за O(1). list.pop(0) би местил всички останали.
needs = {
    "core": [],
    "db": ["core"],
    "auth": ["core", "db"],
    "catalog": ["db"],
    "cart": ["catalog", "auth"],
    "payments": ["auth"],
    "web": ["cart", "payments"],
}
print("Ред:", ", ".join(build_order(needs)))
Изход
Ред: core, db, auth, catalog, payments, cart, web

def build_order(needs):
    indegree = {m: len(deps) for m, deps in needs.items()}
    users = {m: [] for m in needs}
    for m, deps in needs.items():
        for dep in deps:
            users[dep].append(m)
    ready = deque(m for m in needs if indegree[m] == 0)
    order = []
    while ready:
        m = ready.popleft()
        order.append(m)
        for user in users[m]:
            indegree[user] -= 1
            if indegree[user] == 0:
                ready.append(user)
    return order
Стъпка по стъпка, с думи
  1. Седем модула. Стрелката е от зависимостта към модула, който я ползва. Числото над модула е входната му степен: колко от зависимостите му още не са построени.
  2. Само core не чака нищо (степен 0). Той влиза в опашката ready.
  3. core излиза от ready и се строи. Всеки, който го ползва, чака с една зависимост по-малко: db пада на 0 и влиза в опашката, auth пада на 1.
  4. db се строи. auth и catalog падат на 0: и двата имат всичко, което им трябва, и влизат в опашката.
  5. auth се строи. payments пада на 0 и влиза, cart пада на 1: още чака catalog.
  6. catalog се строи и cart пада на 0. Сега и cart влиза в опашката.
  7. payments се строи. web пада на 1: още чака cart.
  8. cart се строи, web пада на 0 и влиза последен.
  9. web се строи. Никой не го ползва, и опашката е празна.
  10. build_order връща order със 7 модула, колкото са в needs: всеки е след зависимостите си. По-малко щеше да значи цикъл.

Опашката никога не държи повече от два модула: само тези, които вече имат всичко и чакат ред.

Пробвай

Предвиди изхода

Задачите на един release: проверка на стила, компилиране, тестове, пакет, качване, известие. Какво връща build_order?

tasks = {
    "lint": [],
    "compile": [],
    "test": ["compile"],
    "package": ["compile", "lint"],
    "deploy": ["test", "package"],
    "notify": ["deploy"],
}
print(", ".join(build_order(tasks)))
Отговор

Пробвай

Попълни

Кога модул влиза в опашката?

for user in users[m]:
    indegree[user] -= 1
    if :
        ready.append(user)

Идеята

Цикълът

Колега кара auth да ползва помощна функция от web:

    "auth": ["core", "db", "web"],

Сега auth чака web, web чака cart, cart чака auth. Никой от трите не стига степен 0 и не влиза в опашката. payments чака auth и също остава. Опашката свършва, а в order са само 3 от 7 модула.

Това е и проверката: по-малко модули в order, отколкото в графа, значи цикъл. За да кажеш кои модули са виновни, тръгни от първия непостроен и следвай непостроена зависимост. Всеки непостроен модул има поне една такава, затова рано или късно стигаш модул, през който вече си минал:

def find_cycle(needs, order):
    built = set(order)
    m = next(x for x in needs if x not in built)
    path = []
    while m not in path:
        path.append(m)
        m = next(d for d in needs[m] if d not in built)
    return path[path.index(m):] + [m]
order = build_order(needs)
if len(order) < len(needs):
    print("Построени:", ", ".join(order))
    print("Цикъл:", " → ".join(find_cycle(needs, order)))
else:
    print("Ред:", ", ".join(order))
Изход
Построени: core, db, catalog
Цикъл: auth → web → cart → auth
По-точно, за любопитните

Истинските инструменти правят същото и казват цикъла по име. Gradle пише „Circular dependency between the following tasks“ и изброява задачите. Maven пише „The projects in the reactor contain a cyclic reference“. MSBuild отказва проект, който стига до себе си през референциите. Поправката винаги е в кода, не в инструмента: общото на двата модула отива в трети, от който зависят и двата.

findCycle намира един цикъл. Модулите извън него, които чакат модул от цикъла (тук payments), не са част от проблема, а жертви. Те ще се построят, щом цикълът се махне.

Пробвай

Намери грешката

Колега е написал проверката за цикъл. С auth, който чака web, програмата казва:

order = build_order(needs)
if not order:
    print("Построени:", ", ".join(order))
    print("Цикъл:", " → ".join(find_cycle(needs, order)))
else:
    print("Ред:", ", ".join(order))
Изход
Ред: core, db, catalog

Build продължава със 3 модула, а 4 тихо липсват. На кой ред е грешката?

Избери реда с грешката.

Виж го

Същото с DFS

Има и втори начин, с обхождането в дълбочина от урока за DFS. Преди да сложиш модул в реда, посети всяка негова зависимост. Модулът отива в order чак след като всичките му зависимости са там. Това е post-order: записваш на връщане, не на влизане.

def dfs_order(needs):
    order = []
    done = set()
    on_path = set()


    def visit(m):
        if m in done:
            return
        if m in on_path:
            raise ValueError(f"Цикъл при {m}")
        on_path.add(m)
        for dep in needs[m]:
            visit(dep)
        on_path.remove(m)
        done.add(m)
        order.append(m)


    for m in needs:
        visit(m)
    return order
needs = {
    "core": [],
    "db": ["core"],
    "auth": ["core", "db"],
    "catalog": ["db"],
    "cart": ["catalog", "auth"],
    "payments": ["auth"],
    "web": ["cart", "payments"],
}
print("Ред:", ", ".join(dfs_order(needs)))
broken = {
    "core": [],
    "db": ["core"],
    "auth": ["core", "db", "web"],
    "catalog": ["db"],
    "cart": ["catalog", "auth"],
    "payments": ["auth"],
    "web": ["cart", "payments"],
}
try:
    dfs_order(broken)
except ValueError as e:
    print(e)
Изход
Ред: core, db, auth, catalog, cart, payments, web
Цикъл при auth

Редът е друг: тук cart е преди payments. И двата реда са верни, защото cart и payments не зависят един от друг. Топологичният ред рядко е само един.

Цикълът тук се хваща по друг начин. on_path са модулите, които DFS е започнал, но не е свършил: те са на стека на извикванията точно сега. Ако срещнеш такъв модул отново, си минал в кръг. В урока за DFS това са сивите върхове.

По-точно, за любопитните

Кой да избереш? И двата струват O(V + E): всеки модул се обработва веднъж, всяка зависимост се поглежда веднъж. Kahn е без рекурсия и дава естествено „кое може да тръгне сега“, затова build инструментите, които строят паралелно, мислят като него. DFS е по-кратък, когато графът вече се обхожда в дълбочина.

Рекурсивният DFS в Python спира при 1000 вложени извиквания (RecursionError). Верига от 1000 модула е рядкост, но граф от клетки на таблица може да я стигне. Тогава Kahn или DFS със собствен стек (от рекурсия към цикъл).

Идеята

Къде още

Топологичен ред има навсякъде, където нещо чака нещо друго:

  • Зависимостите на пакетите. npm и pip решават кои версии да сложат, после ги инсталират така, че всеки пакет да е след своите. Gradle и MSBuild строят модулите на проекта в топологичен ред, а независимите паралелно.
  • Makefile. Всяко правило казва от кои файлове зависи. make строи графа и пуска командите в такъв ред, че всеки файл да е готов, преди да трябва на друг.
  • Електронната таблица. Клетката C1 = A1 + B1 зависи от A1 и B1. При промяна на A1 таблицата преизчислява само клетките след нея, в топологичен ред. Формула, която стига до себе си, е цикъл, и Excel го казва: „circular reference“.
  • Миграциите на базата и задачите в CI: всяка стъпка чака своите.

Упражнение

Вълни в CI

Реши задачата в редактора си.

Вълни. CI сървърът пуска едновременно всички задачи, които вече могат да тръгнат. Напиши waves(needs), който връща задачите по вълни: първата вълна са задачите без зависимости, всяка следваща са тези, на които последната зависимост е в предишната вълна. Пусни я със задачите от „Предвиди изхода“:

Изход
Вълна 1: lint, compile
Вълна 2: test, package
Вълна 3: deploy
Вълна 4: notify

Подсказка: това е Kahn, но вместо една опашка пазиш текущата вълна и строиш следващата.

Още задачи

  • Най-дългата верига. Колко вълни най-малко трябват на CI, ако има безкрайно много машини? Това е най-дългият път в графа.
  • Подреден ред. Направи изхода еднакъв, каквото и да е подреждането на needs: при няколко готови модула вземи първия по азбучен ред. Каква структура трябва вместо опашката?
  • Всички виновни. Изведи всички модули, които не са построени заради цикъла, и отдели тези, които са в самия цикъл.

Тест

Провери се

1. Какво е входната степен на модул в алгоритъма на Kahn?
2. buildOrder върна 4 модула, а в needs има 7. Какво значи това?
3. Kahn дава core, db, auth, catalog, payments, cart, web, а DFS дава core, db, auth, catalog, cart, payments, web. Кое е вярно?
4. Колко струва алгоритъмът на Kahn за V модула и E зависимости?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·