Продвинутые структуры данных. Часть первая: Направленный ациклический граф

Всем привет! Уже на следующей неделе стартуют занятия в новой группе курса «Алгоритмы для разработчиков». В связи с этим, делимся с вами переводом совсем небольшого, но довольно интересного материала.

---

Я хотел начать эту серию статей со структуры данных, с которой все мы как разработчики, хорошо знакомы, но вполне возможно, что даже не представляем как она устроена.

«Направленный ациклический граф? Никогда об этом не слышал. Не думай, что все обо мне знаешь!», вы можете сказать, но именно этот граф делает возможным контроль версий. Да, Git представляет из себя ациклический граф. В этой статье я поделюсь с вами знаниями о направленных ациклических графах (Directed Acyclic Graphs, DAG), а затем покажу, как написать свой собственный.

Что такое DAG?

Так что это вообще значит? DAG – это однонаправленный граф, где ни один элемент не может считаться дочерним. Многие из нас знакомы со связными списками, деревьями и графами. DAG очень похож на первое и второе в реализации третьего.


Выглядит похоже на дерево, но не совсем

В самом минимальном виде у DAG есть 4 составляющих:

1. Узлы. В них хранятся данные.
2. Направленные ребра: стрелки, которые указывают в одном направлении (то, что делает эту структуру данных непохожей на другие).
3. Один «великий» узел-предок без родителей. (Забавный факт: большинство деревьев предков на самом деле являются направленными ациклическими графами, а не деревьями, поскольку порой «двоюродные братья и сестры женятся друг на друге»)
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;
};

Как это работает? Объект vertex – это место, где происходит вся магия. Мы добавляем узел, объект с поступающими узлами и массив со всеми их именами, переменную типа Boolean, сигнализирующую о том, указывает ли узел на что-то или нет, и его значение. К этому мы перейдем попозже.

Теперь давайте добавим несколько ребер и соединим узлы друг с другом. Прежде чем мы сможем это сделать, мы должны создать вспомогательную функцию, которая проверяет, посещали мы этот узел или нет. Давайте назовем ее visit.

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.prototype.addEdge = function(fromName, toName) {
  if (!fromName || !toName || fromName === toName) {
  return;
  }
  const from = this.add(fromName)
  const to = this.add(toName);
  if (to.incoming.hasOwnProperty(fromName)) {
  return;
  }
  function checkCycle(vertex, path) {
    if (vertex.name === toName) {
    throw new Error(“Theres a cycle foo!!!!!“));
    }
  }
  visit(from, checkCycle);
  from.hasOutgoing = true;
  to.incoming[fromName] = from;
  to.incomingNames.push(fromName);
};

Пора отдать должное

Пока я изучал материалы для написания этой статьи, я прочел несколько замечательных сообщений от удивительно умных людей, и в итоге большая часть информации была получена от них. Часть теоретической информации я получил, изучив этот хорошо структурированный пост о DAG и контроле версий. Код, представленный здесь, вдохновлен исходниками emberjs и их авторами. А еще я многое почерпнул из других статей и сообщений о DAG в блогах множества великих людей.

Спасибо за то, что прочитали!