**Trabalho em progresso.**
eu queria começar esta série com uma estrutura de dados estrutura de que todos nós somos como os desenvolvedores intimamente familiarizado com, mas não pode mesmo saber é: Direcionado Acíclico Gráficos. “Nunca ouvi falar disso. Não me conheces!”você pode dizer, mas este gráfico é o que torna o controle de Versão possível. Git é um grafo acíclico. Neste post, eu vou dar-lhe um pouco de conhecimento de alto nível em DAGs e, em seguida, mostrar-lhe como fazer um com algum código.o que é um DAG?o que significa isso? Um DAG é um grafo que flui em uma direção, onde nenhum elemento pode ser um filho de si mesmo. Assim, a maioria de nós está familiarizada com listas de links, árvores e até mesmo gráficos. Um DAG é muito semelhante aos dois primeiros, e uma implementação do terceiro.
No mínimo, um DAG tem 4 coisas:
- Nós: Um lugar para armazenar os dados.arestas direcionadas: Setas que apontam em uma direção (a coisa que faz esta estrutura de dados diferente)
- algum grande nó ancestral sem pais. (Fato engraçado: a maioria das árvores ancestrais são realmente Cãos e não realmente árvores porque primos em algum momento se casam um com o outro.)
- folhas: nós sem filhos
vamos fazer um
então vamos escrever algum código. Primeiro, vamos criar um construtor com duas propriedades e chamá-lo de DAG.
function DAG() {
this.nodes = ;
this.vertices = {};
}
em seguida, adicionaremos um método de adição. Viste o que eu fiz?
DAG.prototype.add = function(node) {
if (!node) { return; }
if (this.vertices) {
return this.vertices;
}
const vertex = {
node: node,
incoming: {},
incomingNodes: ,
hasOutgoing: false,
value: null
};
this.vertices = vertex;
this.nodes.push(node);
return vertex;
};
então como isso funciona? O objeto vértice é onde todas as coisas boas acontecem. Nós adicionamos um nó, um objeto de nós de entrada, e um array com todos os seus nomes, um booleano sobre se ele aponta para algo e um valor. Vamos chegar a alguns destes um pouco mais tarde.
Agora vamos adicionar algumas arestas e fazer com que as coisas se liguem umas às outras. Antes de podermos fazer isso, temos que criar uma função auxiliar que verifique se nós visitamos esse nó ou não. Vamos chamar-lhe visita.
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 = true;
for (i = 0; i < len; i++) {
visit(vertices], fn, visited, path);
}
fn(vertex, path);
path.pop();
}
o Que acontece aqui é
Vamos Dar Crédito Onde ele é Realmente Devido
a Investigar este artigo, eu li alguns ótimos posts por incrivelmente pessoas inteligentes e a maioria das informações que vieram com eles. Aprendi a maior parte da teoria lendo este post bem escrito em DAGs e controle de versão. O código aqui tem toda a sua inspiração no código fonte emberjs e os autores brilhantes por trás dele. Eu também li muitos outros artigos e posts de blogs sobre os Cãos de grandes pessoas ao redor da internet. Obrigado por ler!