**В процес на работа**

Исках да започна тази поредица със структура на структурата на данните, с която всички като разработчици сме добре запознати, но може дори да не я знаем: насочени ациклични графики. „Никога не съм чувал за това. Ти не ме познаваш!“ може да кажете, но тази графика прави контрола на версиите възможен. Git е ациклична графика. В тази публикация ще ви дам малко познания на високо ниво за DAG и след това ще ви покажа как да направите такъв с някакъв код.

Какво е DAG?

И така, какво изобщо означава това? DAG е графика, която тече в една посока, където нито един елемент не може да бъде дете на себе си. Така че повечето от нас са запознати с LinkedLists, дървета и дори графики. DAG е много подобен на първите два и реализация на третия.

Като минимум DAG ще има 4 неща:

  1. Възли: Място за съхраняване на данните.
  2. Насочени ръбове: стрелки, които сочат в една посока (нещото, което прави тази структура от данни различна)
  3. Някакъв голям наследствен възел без родители. (Забавен факт: Повечето родословни дървета всъщност са DAG, а не всъщност дървета, защото братовчедите в даден момент се женят един за друг.)
  4. Листа: Възли без деца

Да направим едно

Така че нека напишем малко код. Първо, нека създадем конструктор с две свойства и да го наречем 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 от страхотни хора в интернет. Благодаря ви, че прочетохте!