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

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

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

Проблем

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

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

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

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

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

Идеята

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

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

const needs = new Map([
  ["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 отвътре

function buildOrder(needs) {
  const indegree = new Map();
  const users = new Map();
  for (const [m, deps] of needs) {
    indegree.set(m, deps.length);
    users.set(m, []);
  }
  for (const [m, deps] of needs) {
    for (const dep of deps) users.get(dep).push(m);
  }
  const ready = [...needs.keys()].filter(
    (m) => indegree.get(m) === 0,
  );
  const order = [];
  let head = 0;
  while (head < ready.length) {
    const m = ready[head++];
    order.push(m);
    for (const user of users.get(m)) {
      indegree.set(user, indegree.get(user) - 1);
      if (indegree.get(user) === 0) ready.push(user);
    }
  }
  return order;
}

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

В JavaScript няма вградена опашка. shift() на масив мести всички елементи, затова head сочи следващия, а масивът само расте.
const needs = new Map([
  ["core", []],
  ["db", ["core"]],
  ["auth", ["core", "db"]],
  ["catalog", ["db"]],
  ["cart", ["catalog", "auth"]],
  ["payments", ["auth"]],
  ["web", ["cart", "payments"]],
]);
console.log(`Ред: ${buildOrder(needs).join(", ")}`);
Изход
Ред: core, db, auth, catalog, payments, cart, web

function buildOrder(needs) {
  const indegree = new Map();
  const users = new Map();
  for (const [m, deps] of needs) {
    indegree.set(m, deps.length);
    users.set(m, []);
  }
  for (const [m, deps] of needs) {
    for (const dep of deps) users.get(dep).push(m);
  }
  const ready = [...needs.keys()].filter(
    (m) => indegree.get(m) === 0,
  );
  const order = [];
  let head = 0;
  while (head < ready.length) {
    const m = ready[head++];
    order.push(m);
    for (const user of users.get(m)) {
      indegree.set(user, indegree.get(user) - 1);
      if (indegree.get(user) === 0) ready.push(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?

const tasks = new Map([
  ["lint", []],
  ["compile", []],
  ["test", ["compile"]],
  ["package", ["compile", "lint"]],
  ["deploy", ["test", "package"]],
  ["notify", ["deploy"]],
]);
console.log(buildOrder(tasks).join(", "));
Отговор

Пробвай

Попълни

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

for (const user of users.get(m)) {
  indegree.set(user, indegree.get(user) - 1);
  if () ready.push(user);
}

Идеята

Цикълът

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

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

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

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

function findCycle(needs, order) {
  const built = new Set(order);
  let m = [...needs.keys()].find((x) => !built.has(x));
  const path = [];
  while (!path.includes(m)) {
    path.push(m);
    m = needs.get(m).find((d) => !built.has(d));
  }
  return [...path.slice(path.indexOf(m)), m];
}
const order = buildOrder(needs);
if (order.length < needs.size) {
  console.log(`Построени: ${order.join(", ")}`);
  console.log(`Цикъл: ${findCycle(needs, order).join(" → ")}`);
} else {
  console.log(`Ред: ${order.join(", ")}`);
}
Изход
Построени: 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, програмата казва:

const order = buildOrder(needs);
if (order.length === 0) {
  console.log(`Построени: ${order.join(", ")}`);
  console.log(`Цикъл: ${findCycle(needs, order).join(" → ")}`);
} else {
  console.log(`Ред: ${order.join(", ")}`);
}
Изход
Ред: core, db, catalog

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

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

Виж го

Същото с DFS

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

function dfsOrder(needs) {
  const order = [];
  const done = new Set();
  const onPath = new Set();
  const visit = (m) => {
    if (done.has(m)) return;
    if (onPath.has(m)) throw new Error(`Цикъл при ${m}`);
    onPath.add(m);
    for (const dep of needs.get(m)) visit(dep);
    onPath.delete(m);
    done.add(m);
    order.push(m);
  };
  for (const m of needs.keys()) visit(m);
  return order;
}
const needs = new Map([
  ["core", []],
  ["db", ["core"]],
  ["auth", ["core", "db"]],
  ["catalog", ["db"]],
  ["cart", ["catalog", "auth"]],
  ["payments", ["auth"]],
  ["web", ["cart", "payments"]],
]);
console.log(`Ред: ${dfsOrder(needs).join(", ")}`);
const broken = new Map([
  ["core", []],
  ["db", ["core"]],
  ["auth", ["core", "db", "web"]],
  ["catalog", ["db"]],
  ["cart", ["catalog", "auth"]],
  ["payments", ["auth"]],
  ["web", ["cart", "payments"]],
]);
try {
  dfsOrder(broken);
} catch (e) {
  console.log(e.message);
}
Изход
Ред: core, db, auth, catalog, cart, payments, web
Цикъл при auth

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

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

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

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

Рекурсивният DFS в JavaScript хвърля RangeError: Maximum call stack size exceeded при верига от около 10 000 модула. 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 за достъпно обучение по програмиране ·