Estruturas de dados avançadas. Parte Um: Gráfico Acíclico Direcional

Olá pessoal! Na próxima semana, as aulas começarão no novo grupo do curso Algoritmos para Desenvolvedores . Nesse sentido, estamos compartilhando com você a tradução de um material muito pequeno, mas bastante interessante.

---

Eu queria começar essa série de artigos com uma estrutura de dados que todos nós, como desenvolvedores, estamos familiarizados, mas é possível que nem saibamos como isso funciona.

“Gráfico acíclico direcional? Nunca ouvi falar disso. Não pense que você sabe tudo sobre mim! ”, Você pode dizer, mas é esse gráfico que torna possível o controle de versão. Sim, o Git é um gráfico acíclico. Neste artigo, compartilharei com você o conhecimento de gráficos acíclicos direcionados (DAGs) e depois mostrarei como escrever seus próprios.

O que é um DAG?

Então, o que isso significa? Um DAG é um gráfico unidirecional em que nenhum elemento pode ser considerado filho. Muitos de nós estamos familiarizados com listas, árvores e gráficos vinculados. O DAG é muito semelhante ao primeiro e ao segundo na implementação do terceiro.


Parece uma árvore, mas não completamente

Na sua forma mais mínima, o DAG possui 4 componentes:

1. Nós Eles armazenam dados.
2. Bordas direcionais : setas que apontam em uma direção (o que torna essa estrutura de dados diferente das outras).
3. Um nó ancestral “ótimo” sem os pais . (Curiosidade: a maioria das árvores ancestrais são na verdade gráficos acíclicos direcionados, não árvores, porque às vezes "primos se casam")
4. Folhas Ou nós sem nós filhos.

Vamos escrever nosso gráfico acíclico direcionado

Agora vamos escrever o código. Primeiro, crie um construtor com duas propriedades e chame-o de DAG.

function DAG() { this.nodes = []; this.vertices = {}; } 

Crie um método para adicionar nós. Viu o que eu fiz aqui?

 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; }; 

Como isso funciona? O objeto do vertex é onde toda a mágica acontece. Nós adicionamos um nó, um objeto com nós de entrada e uma matriz com todos os seus nomes, uma variável do tipo Boolean que sinaliza se o nó aponta para algo ou não, e seu valor. Passaremos a isso mais tarde.

Agora vamos adicionar algumas arestas e conectar os nós. Antes de podermos fazer isso, precisamos criar uma função auxiliar que verifique se visitamos esse nó ou não. Vamos ligar para ela.

 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(); } 

O seguinte acontece:

 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); }; 

É hora de prestar homenagem

Enquanto estudava os materiais para escrever este artigo, li algumas mensagens maravilhosas de pessoas incrivelmente inteligentes e, como resultado, a maioria das informações foi recebida delas. Eu recebi algumas informações teóricas deste post bem estruturado sobre DAG e controle de versão. O código apresentado aqui é inspirado nas fontes emberjs e seus autores. E aprendi muito com outros artigos e postagens sobre o DAG nos blogs de muitas pessoas excelentes.

Obrigado pela leitura!