**Work in progress**
Volevo dare il via a questa serie con una struttura di struttura dati che siamo tutti come sviluppatori intimamente familiari con ma potrebbe anche non saperlo: Directed Acyclic Graphs. “Non ne ho mai sentito parlare. Tu non mi conosci!”si può dire, ma questo grafico è ciò che rende possibile il controllo della versione. Git è un grafico aciclico. In questo post, ti darò un po ‘ di conoscenza di alto livello sui DAG e poi ti mostrerò come crearne uno con del codice.
Che cos’è un DAG?
Quindi cosa significa? Un DAG è un grafico che scorre in una direzione, dove nessun elemento può essere figlio di se stesso. Quindi la maggior parte di noi ha familiarità con Linkedlist, alberi e persino grafici. Un DAG è molto simile ai primi due e un’implementazione del terzo.
Come minimo, un DAG sono 4 cose:
- Nodi: Un posto per memorizzare i dati.
- Bordi diretti: Frecce che puntano in una direzione (la cosa che rende questa struttura dati diversa)
- Un grande nodo ancestrale senza genitori. (Fatto divertente: la maggior parte degli alberi di ascendenza sono in realtà DAG e non in realtà alberi perché i cugini ad un certo punto si sposano l’un l’altro.)
- Foglie: Nodi senza figli
Facciamo uno
Quindi scriviamo un po ‘ di codice. Innanzitutto, creiamo un costruttore con due proprietà e lo chiamiamo DAG.
function DAG() {
this.nodes = ;
this.vertices = {};
}
Successivamente aggiungeremo un metodo add. Hai visto cosa ho fatto?
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;
};
Quindi come funziona? L’oggetto vertice è dove tutte le cose buone accadono. Aggiungiamo un nodo, un oggetto di nodi in entrata e un array con tutti i loro nomi, un booleano sul fatto che punti a qualcosa e un valore. Arriveremo ad alcuni di questi un po ‘ più tardi.
Ora consente di aggiungere alcuni bordi e fare cose connettersi tra loro. Prima di poterlo fare, dobbiamo creare una funzione di supporto che controlli se abbiamo visitato quel nodo o meno. Chiamiamola 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();
}
Quello che succede qui è
Diamo credito dove è veramente dovuto
Ricercando questo articolo, ho letto alcuni ottimi post di persone incredibilmente intelligenti e la maggior parte delle informazioni è venuta da loro. Ho imparato la maggior parte della teoria leggendo questo post ben scritto su DAG e controllo della versione. Il codice qui ha preso tutta la sua ispirazione dal codice sorgente emberjs e dai brillanti autori dietro di esso. Ho anche letto numerosi altri articoli e post di blog riguardanti DAG da grandi persone su Internet. Grazie per la lettura!