**lucrări în desfășurare**
am vrut să încep această serie cu o structură de structură de date cu care suntem cu toții ca Dezvoltatori familiarizați, dar poate nici măcar nu o știm: grafice aciclice direcționate. „Nu am auzit niciodată de asta. Nu mă cunoști!”ați putea spune, dar acest grafic este ceea ce face posibil controlul versiunii. Git este un grafic aciclic. În această postare, vă voi oferi un pic de cunoștințe de nivel înalt despre DAGs și apoi vă voi arăta cum să faceți unul cu un cod.
ce este un DAG?
deci, ce înseamnă asta? Un DAG este un grafic care curge într-o direcție, unde niciun element nu poate fi un copil al său. Deci, majoritatea dintre noi sunt familiarizați cu link-Ulliste, copaci și chiar grafice. Un DAG este foarte similar cu primele două, și o punere în aplicare a treia.
Similar cu un copac, dar nu destul de aceeași
la minim, un dag va avea 4 lucruri:
- noduri: un loc pentru stocarea datelor.
- margini direcționate: Săgeți care indică într-o direcție (lucrul care face această structură de date diferită)
- un mare nod ancestral fără părinți. (Fapt amuzant: majoritatea copacilor de origine sunt de fapt DAGs și nu de fapt copaci, deoarece veri la un moment dat se căsătoresc unul cu celălalt.)
- frunze: noduri fără copii
să facem unul
deci, să scriem un cod. În primul rând, să creăm un constructor cu două proprietăți și să-l numim DAG.
function DAG() {
this.nodes = ;
this.vertices = {};
}
în continuare vom adăuga o metodă de adăugare. Vezi ce am făcut acolo?
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;
};
Deci, cum funcționează acest lucru? Obiectul vertex este locul în care se întâmplă toate lucrurile bune. Adăugăm un nod, un obiect al nodurilor primite și o matrice cu toate numele lor, un boolean dacă indică ceva și o valoare. Vom ajunge la unele dintre acestea puțin mai târziu.
acum, vă permite să adăugați unele margini și de a face lucruri conecta între ele. Înainte de a putea face acest lucru, trebuie să creăm o funcție de ajutor care să verifice dacă am vizitat acel nod sau nu. Să-i spunem vizită.
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();
}
Ce se întâmplă aici este
să dăm Credit unde se datorează cu adevărat
cercetând acest articol, am citit câteva postări grozave ale unor oameni uimitor de deștepți și majoritatea informațiilor au venit de la ei. Am învățat cea mai mare parte a teoriei citind acest post bine scris pe DAGs și controlul versiunii. Codul de aici a primit toată inspirația din codul sursă emberjs și autorii geniali din spatele acestuia. Am citit, de asemenea, numeroase alte articole și postări pe blog cu privire la dag-uri de la oameni minunați de pe internet. Vă mulțumim pentru lectură!