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

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

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

Проблем

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

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

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

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

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

Идеята

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

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

var needs = new Dictionary<string, string[]>
{
    ["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 отвътре

static List<string> BuildOrder(
    Dictionary<string, string[]> needs)
{
    var indegree = new Dictionary<string, int>();
    var users = new Dictionary<string, List<string>>();
    foreach (var (m, deps) in needs)
    {
        indegree[m] = deps.Length;
        users[m] = [];
    }
    foreach (var (m, deps) in needs)
    {
        foreach (string dep in deps) users[dep].Add(m);
    }
    var ready = new Queue<string>();
    foreach (string m in needs.Keys)
    {
        if (indegree[m] == 0) ready.Enqueue(m);
    }
    var order = new List<string>();
    while (ready.Count > 0)
    {
        string m = ready.Dequeue();
        order.Add(m);
        foreach (string user in users[m])
        {
            indegree[user]--;
            if (indegree[user] == 0) ready.Enqueue(user);
        }
    }
    return order;
}

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

Queue<T> е опашката: Enqueue слага отзад, Dequeue вади отпред, и двете за O(1).
var needs = new Dictionary<string, string[]>
{
    ["core"] = [],
    ["db"] = ["core"],
    ["auth"] = ["core", "db"],
    ["catalog"] = ["db"],
    ["cart"] = ["catalog", "auth"],
    ["payments"] = ["auth"],
    ["web"] = ["cart", "payments"],
};
Console.WriteLine($"Ред: {string.Join(", ", BuildOrder(needs))}");
Изход
Ред: core, db, auth, catalog, payments, cart, web

static List<string> BuildOrder(
    Dictionary<string, string[]> needs)
{
    var indegree = new Dictionary<string, int>();
    var users = new Dictionary<string, List<string>>();
    foreach (var (m, deps) in needs)
    {
        indegree[m] = deps.Length;
        users[m] = [];
    }
    foreach (var (m, deps) in needs)
    {
        foreach (string dep in deps) users[dep].Add(m);
    }
    var ready = new Queue<string>();
    foreach (string m in needs.Keys)
    {
        if (indegree[m] == 0) ready.Enqueue(m);
    }
    var order = new List<string>();
    while (ready.Count > 0)
    {
        string m = ready.Dequeue();
        order.Add(m);
        foreach (string user in users[m])
        {
            indegree[user]--;
            if (indegree[user] == 0) ready.Enqueue(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?

var tasks = new Dictionary<string, string[]>
{
    ["lint"] = [],
    ["compile"] = [],
    ["test"] = ["compile"],
    ["package"] = ["compile", "lint"],
    ["deploy"] = ["test", "package"],
    ["notify"] = ["deploy"],
};
Console.WriteLine(string.Join(", ", BuildOrder(tasks)));
Отговор

Пробвай

Попълни

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

foreach (string user in users[m])
{
    indegree[user]--;
    if () ready.Enqueue(user);
}

Идеята

Цикълът

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

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

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

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

static List<string> FindCycle(
    Dictionary<string, string[]> needs, List<string> order)
{
    var built = order.ToHashSet();
    string m = needs.Keys.First(x => !built.Contains(x));
    var path = new List<string>();
    while (!path.Contains(m))
    {
        path.Add(m);
        m = needs[m].First(d => !built.Contains(d));
    }
    int from = path.IndexOf(m);
    var loop = path.GetRange(from, path.Count - from);
    loop.Add(m);
    return loop;
}
var order = BuildOrder(needs);
if (order.Count < needs.Count)
{
    Console.WriteLine($"Построени: {string.Join(", ", order)}");
    var loop = FindCycle(needs, order);
    Console.WriteLine($"Цикъл: {string.Join(" → ", loop)}");
}
else
{
    Console.WriteLine($"Ред: {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, програмата казва:

var order = BuildOrder(needs);
if (order.Count == 0)
{
    Console.WriteLine($"Построени: {string.Join(", ", order)}");
    var loop = FindCycle(needs, order);
    Console.WriteLine($"Цикъл: {string.Join(" → ", loop)}");
}
else
{
    Console.WriteLine($"Ред: {string.Join(", ", order)}");
}
Изход
Ред: core, db, catalog

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

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

Виж го

Същото с DFS

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

static List<string> DfsOrder(Dictionary<string, string[]> needs)
{
    var order = new List<string>();
    var done = new HashSet<string>();
    var onPath = new HashSet<string>();
    void Visit(string m)
    {
        if (done.Contains(m)) return;
        if (!onPath.Add(m))
        {
            throw new InvalidOperationException($"Цикъл при {m}");
        }
        foreach (string dep in needs[m]) Visit(dep);
        onPath.Remove(m);
        done.Add(m);
        order.Add(m);
    }
    foreach (string m in needs.Keys) Visit(m);
    return order;
}
var needs = new Dictionary<string, string[]>
{
    ["core"] = [],
    ["db"] = ["core"],
    ["auth"] = ["core", "db"],
    ["catalog"] = ["db"],
    ["cart"] = ["catalog", "auth"],
    ["payments"] = ["auth"],
    ["web"] = ["cart", "payments"],
};
Console.WriteLine($"Ред: {string.Join(", ", DfsOrder(needs))}");
var broken = new Dictionary<string, string[]>
{
    ["core"] = [],
    ["db"] = ["core"],
    ["auth"] = ["core", "db", "web"],
    ["catalog"] = ["db"],
    ["cart"] = ["catalog", "auth"],
    ["payments"] = ["auth"],
    ["web"] = ["cart", "payments"],
};
try
{
    DfsOrder(broken);
}
catch (InvalidOperationException e)
{
    Console.WriteLine(e.Message);
}
Изход
Ред: core, db, auth, catalog, cart, payments, web
Цикъл при auth

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

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

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

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

В C# препълването на стека при много дълга верига спира целия процес. 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 за достъпно обучение по програмиране ·