Advanced Data Structures Part 1: Directed Acyclic Graph (DAG)

**Work in progress**

Ik wilde deze serie beginnen met een datastructuurstructuur die we als ontwikkelaars allemaal goed kennen, maar die we misschien niet eens kennen: Directed Acyclic Graphs. “Daar heb ik nog nooit van gehoord. Je kent me niet!”je kunt zeggen, maar deze grafiek is wat versiebeheer mogelijk maakt. Git is een acyclische grafiek. In deze post, Ik zal je een beetje van hoog niveau kennis over DAGs en dan laten zien hoe je een te maken met een aantal code.

Wat is een DAG?

dus wat betekent dat eigenlijk? Een dag is een grafiek die in één richting stroomt, waar geen enkel element een kind van zichzelf kan zijn. De meesten van ons zijn bekend met gekoppelde lijsten, bomen en zelfs grafieken. Een DAG lijkt erg op de eerste twee, en een implementatie van de derde.

op zijn minst zal een dag 4 dingen hebben:

1. nodes: een plaats om de gegevens op te slaan.
2. gerichte randen: Pijlen die in één richting wijzen (het ding dat deze gegevensstructuur anders maakt)
3. een groot voorouderlijk knooppunt zonder ouders. (Leuk feitje: de meeste voorouderlijke bomen zijn eigenlijk DAGs en niet echt bomen omdat neven op een gegeven moment met elkaar trouwen.)
4. Leaves: Nodes with no children

laten we een

maken, dus laten we wat code schrijven. Laten we eerst een constructor maken met twee eigenschappen en het DAG noemen.

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

vervolgens zullen we een methode toevoegen. Zie je wat ik daar deed?

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

dus hoe werkt dit? Het vertex object is waar al het goede gebeurt. We voegen een knooppunt toe, een object van binnenkomende knooppunten, en een array met al hun namen, een boolean over of het naar iets wijst en een waarde. We komen er later wel op terug.

laten we nu enkele Randen toevoegen en dingen met elkaar verbinden. Voordat we dat kunnen doen, moeten we een helperfunctie maken die controleert of we dat knooppunt hebben bezocht of niet. Laten we het bezoek noemen.

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

wat hier gebeurt is

laten we krediet geven waar het echt te wijten is

onderzoek naar dit artikel, Ik heb een aantal geweldige berichten gelezen door verbazingwekkend slimme mensen en de meeste informatie kwam van hen. Ik leerde het grootste deel van de theorie door het lezen van deze goed geschreven post op DAGs en versiebeheer. De code hier kreeg al zijn inspiratie uit de emberjs broncode en de briljante auteurs erachter. Ik heb ook gelezen tal van andere artikelen en blog posts met betrekking tot DAGs van grote mensen rond het internet. Bedankt voor het lezen!