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

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

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

Проблем

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

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

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

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

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

Идеята

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

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

Map<String, List<String>> needs = new LinkedHashMap<>();
needs.put("core", List.of());
needs.put("db", List.of("core"));
needs.put("auth", List.of("core", "db"));
needs.put("catalog", List.of("db"));
needs.put("cart", List.of("catalog", "auth"));
needs.put("payments", List.of("auth"));
needs.put("web", List.of("cart", "payments"));

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

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

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

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

Виж го

Kahn отвътре

static List<String> buildOrder(
        Map<String, List<String>> needs) {
    Map<String, Integer> indegree = new HashMap<>();
    Map<String, List<String>> users = new HashMap<>();
    for (String m : needs.keySet()) {
        indegree.put(m, needs.get(m).size());
        users.put(m, new ArrayList<>());
    }
    for (String m : needs.keySet()) {
        for (String dep : needs.get(m)) {
            users.get(dep).add(m);
        }
    }
    Deque<String> ready = new ArrayDeque<>();
    for (String m : needs.keySet()) {
        if (indegree.get(m) == 0) ready.add(m);
    }
    List<String> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        String m = ready.poll();
        order.add(m);
        for (String user : users.get(m)) {
            indegree.put(user, indegree.get(user) - 1);
            if (indegree.get(user) == 0) ready.add(user);
        }
    }
    return order;
}

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

ArrayDeque е опашката: add слага отзад, poll вади отпред, и двете за O(1).
Map<String, List<String>> needs = new LinkedHashMap<>();
needs.put("core", List.of());
needs.put("db", List.of("core"));
needs.put("auth", List.of("core", "db"));
needs.put("catalog", List.of("db"));
needs.put("cart", List.of("catalog", "auth"));
needs.put("payments", List.of("auth"));
needs.put("web", List.of("cart", "payments"));
System.out.println("Ред: " + String.join(", ", buildOrder(needs)));
Изход
Ред: core, db, auth, catalog, payments, cart, web

static List<String> buildOrder(
        Map<String, List<String>> needs) {
    Map<String, Integer> indegree = new HashMap<>();
    Map<String, List<String>> users = new HashMap<>();
    for (String m : needs.keySet()) {
        indegree.put(m, needs.get(m).size());
        users.put(m, new ArrayList<>());
    }
    for (String m : needs.keySet()) {
        for (String dep : needs.get(m)) {
            users.get(dep).add(m);
        }
    }
    Deque<String> ready = new ArrayDeque<>();
    for (String m : needs.keySet()) {
        if (indegree.get(m) == 0) ready.add(m);
    }
    List<String> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        String m = ready.poll();
        order.add(m);
        for (String user : users.get(m)) {
            indegree.put(user, indegree.get(user) - 1);
            if (indegree.get(user) == 0) ready.add(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. buildOrder връща order със 7 модула, колкото са в needs: всеки е след зависимостите си. По-малко щеше да значи цикъл.

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

Пробвай

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

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

Map<String, List<String>> tasks = new LinkedHashMap<>();
tasks.put("lint", List.of());
tasks.put("compile", List.of());
tasks.put("test", List.of("compile"));
tasks.put("package", List.of("compile", "lint"));
tasks.put("deploy", List.of("test", "package"));
tasks.put("notify", List.of("deploy"));
System.out.println(buildOrder(tasks));
Отговор

Пробвай

Попълни

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

for (String user : users.get(m)) {
    indegree.put(user, indegree.get(user) - 1);
    if () ready.add(user);
}

Идеята

Цикълът

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

needs.put("auth", List.of("core", "db", "web"));

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

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

static List<String> findCycle(
        Map<String, List<String>> needs, List<String> order) {
    Set<String> built = new HashSet<>(order);
    String m = needs.keySet().stream()
            .filter(x -> !built.contains(x)).findFirst().get();
    List<String> path = new ArrayList<>();
    while (!path.contains(m)) {
        path.add(m);
        m = needs.get(m).stream()
                .filter(d -> !built.contains(d)).findFirst().get();
    }
    List<String> loop = new ArrayList<>(
            path.subList(path.indexOf(m), path.size()));
    loop.add(m);
    return loop;
}
List<String> order = buildOrder(needs);
if (order.size() < needs.size()) {
    System.out.println("Построени: " + String.join(", ", order));
    List<String> loop = findCycle(needs, order);
    System.out.println("Цикъл: " + String.join(" → ", loop));
} else {
    System.out.println("Ред: " + String.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, програмата казва:

List<String> order = buildOrder(needs);
if (order.isEmpty()) {
    System.out.println("Построени: " + String.join(", ", order));
    List<String> loop = findCycle(needs, order);
    System.out.println("Цикъл: " + String.join(" → ", loop));
} else {
    System.out.println("Ред: " + String.join(", ", order));
}
Изход
Ред: core, db, catalog

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

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

Виж го

Същото с DFS

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

static List<String> dfsOrder(Map<String, List<String>> needs) {
    List<String> order = new ArrayList<>();
    Set<String> done = new HashSet<>();
    Set<String> onPath = new HashSet<>();
    for (String m : needs.keySet()) {
        visit(m, needs, done, onPath, order);
    }
    return order;
}


static void visit(String m, Map<String, List<String>> needs,
        Set<String> done, Set<String> onPath, List<String> order) {
    if (done.contains(m)) return;
    if (!onPath.add(m)) {
        throw new IllegalStateException("Цикъл при " + m);
    }
    for (String dep : needs.get(m)) {
        visit(dep, needs, done, onPath, order);
    }
    onPath.remove(m);
    done.add(m);
    order.add(m);
}
Map<String, List<String>> needs = new LinkedHashMap<>();
needs.put("core", List.of());
needs.put("db", List.of("core"));
needs.put("auth", List.of("core", "db"));
needs.put("catalog", List.of("db"));
needs.put("cart", List.of("catalog", "auth"));
needs.put("payments", List.of("auth"));
needs.put("web", List.of("cart", "payments"));
System.out.println("Ред: " + String.join(", ", dfsOrder(needs)));
Map<String, List<String>> broken = new LinkedHashMap<>();
broken.put("core", List.of());
broken.put("db", List.of("core"));
broken.put("auth", List.of("core", "db", "web"));
broken.put("catalog", List.of("db"));
broken.put("cart", List.of("catalog", "auth"));
broken.put("payments", List.of("auth"));
broken.put("web", List.of("cart", "payments"));
try {
    dfsOrder(broken);
} catch (IllegalStateException e) {
    System.out.println(e.getMessage());
}
Изход
Ред: core, db, auth, catalog, cart, payments, web
Цикъл при auth

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

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

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

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

Рекурсивният DFS в Java хвърля StackOverflowError при верига от няколко хиляди до десетки хиляди модула, според стека. Kahn няма този проблем.

Идеята

Къде още

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

  • Зависимостите на пакетите. 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 за достъпно обучение по програмиране ·