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

**Work in progress**

halusin käynnistää tämän sarjan tietorakennerakenteella, jonka me kaikki olemme kehittäjinä läheisesti tunteneet, mutta emme välttämättä edes tunne sitä: Directed Acyclic Graphs. ”En ole koskaan kuullut siitä. Et tunne minua!”saatat sanoa, mutta tämä kaavio on mitä tekee versionhallinta mahdollista. Git on asyklinen graafi. Tässä viestissä, annan sinulle hieman korkean tason tietoa DAGs ja sitten näyttää, miten tehdä yksi joitakin koodia.

mikä on DAG?

Mitä se edes tarkoittaa? Dag on yhteen suuntaan virtaava graafi, jossa mikään elementti ei voi olla lapsi itsestään. Niinpä useimmat meistä tuntevat linkkilistat, puut ja jopa graafit. Dag on hyvin samanlainen kuin kaksi ensimmäistä, ja toteutus kolmas.

vähimmillään dag: ssa on 4 asiaa:

1. solmut: paikka tietojen säilyttämiseen.
2. suunnatut reunat: Yhteen suuntaan osoittavat nuolet (asia, joka tekee tästä tietorakenteesta erilaisen)
3. jokin suuri esi-isäsolmu, jolla ei ole vanhempia. (Hauska fakta: useimmat esi-isät puut ovat itse asiassa Dageja eivätkä varsinaisesti puita, koska serkut menevät jossain vaiheessa naimisiin keskenään.)
4. lehdet: solmut, joilla ei ole lapsia

tehdään yksi

joten kirjoitetaan joku koodi. Luodaan ensin rakentaja, jolla on kaksi ominaisuutta ja kutsutaan sitä dagiksi.

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

seuraavaksi lisätään add-menetelmä. Näetkö, mitä tein?

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

Joten miten tämä toimii? Vertex-objektissa kaikki hyvä tapahtuu. Lisäämme solmu, objekti saapuvien solmujen, ja array kaikki niiden nimet, boolean siitä, onko se osoittaa jotain ja arvo. Palaamme joihinkin näistä hieman myöhemmin.

nyt lisätään reunoja ja saadaan jutut kytkeytymään toisiinsa. Ennen kuin voimme tehdä sen, meidän täytyy luoda helper-toiminto, joka tarkistaa, olemmeko käyneet kyseisessä solmussa vai emme. Kutsutaan sitä vierailuksi.

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

what happens here is

annetaan kunnia siitä, mihin se todella kuuluu

tutkiessani tätä artikkelia, luin ällistyttävän fiksujen ihmisten upeita postauksia ja suurin osa tiedoista tuli heiltä. Opin suurimman osan teoriasta lukemalla tämän hyvin kirjoitetun postauksen Dageista ja versionhallinnasta. Koodi sai kaiken inspiraationsa emberjs: n lähdekoodista ja sen takana olevista nerokkaista kirjoittajista. Olen myös lukenut lukuisia muita artikkeleita ja blogikirjoituksia DAGs upeista ihmisistä ympäri Internetiä. Kiitos lukemisesta!