**В процес на работа**
Исках да започна тази поредица със структура на структурата на данните, с която всички като разработчици сме добре запознати, но може дори да не я знаем: насочени ациклични графики. „Никога не съм чувал за това. Ти не ме познаваш!“ може да кажете, но тази графика прави контрола на версиите възможен. Git е ациклична графика. В тази публикация ще ви дам малко познания на високо ниво за DAG и след това ще ви покажа как да направите такъв с някакъв код.
Какво е DAG?
И така, какво изобщо означава това? DAG е графика, която тече в една посока, където нито един елемент не може да бъде дете на себе си. Така че повечето от нас са запознати с LinkedLists, дървета и дори графики. DAG е много подобен на първите два и реализация на третия.
Като минимум DAG ще има 4 неща:
- Възли: Място за съхраняване на данните.
- Насочени ръбове: стрелки, които сочат в една посока (нещото, което прави тази структура от данни различна)
- Някакъв голям наследствен възел без родители. (Забавен факт: Повечето родословни дървета всъщност са DAG, а не всъщност дървета, защото братовчедите в даден момент се женят един за друг.)
- Листа: Възли без деца
Да направим едно
Така че нека напишем малко код. Първо, нека създадем конструктор с две свойства и да го наречем DAG.
function DAG() { this.nodes = []; this.vertices = {}; }
След това ще добавим метод за добавяне. Вижте какво направих там?
DAG.prototype.add = function(node) { if (!node) { return; } if (this.vertices[node]) { return this.vertices[node]; } const vertex = { node: node, incoming: {}, incomingNodes: [], hasOutgoing: false, value: null }; this.vertices[node] = vertex; this.nodes.push(node); return vertex; };
Как става това? Обектът на върха е мястото, където се случват всички добри неща. Добавяме възел, обект от входящи възли и масив с всичките им имена, булева стойност дали сочи към нещо и стойност. Ще стигнем до някои от тях малко по-късно.
Сега нека добавим малко ръбове и нещата да се свържат един с друг. Преди да можем да направим това, трябва да създадем помощна функция, която проверява дали сме посетили този възел или не. Нека го наречем посещение.
function visit(vertex, fn, visited, path) { const name = vertex.name, vertices = vertex.incoming, names = vertex.incomingNames, len = names.length, i; if (!visited) { visited = {}; } if (!path) { path = []; } if (visited.hasOwnProperty(name)) { return; } path.push(name); visited[name] = true; for (i = 0; i < len; i++) { visit(vertices[names[i]], fn, visited, path); } fn(vertex, path); path.pop(); }
Какво се случва тук е
Нека отдадем заслуженото там, където наистина се дължи
Проучвайки тази статия, прочетох някои страхотни публикации от невероятно умни хора и по-голямата част от информацията дойде от тях. Научих по-голямата част от теорията, като прочетох тази добре написана публикация за DAG и контрол на версиите. Кодът тук е вдъхновен изцяло от изходния код на emberjs и брилянтните автори зад него. Също така прочетох множество други статии и публикации в блогове относно DAG от страхотни хора в интернет. Благодаря ви, че прочетохте!