* * Trabajo en curso * *
Quería iniciar esta serie con una estructura de datos con la que todos, como desarrolladores, estamos íntimamente familiarizados, pero que tal vez ni siquiera la conozcamos: Grafos Acíclicos dirigidos. «Nunca he oído hablar de eso. ¡No me conoces!»se puede decir, pero este gráfico es lo que hace posible el control de versiones. Git es un gráfico acíclico. En este post, te daré un poco de conocimiento de alto nivel sobre DAGs y luego te mostraré cómo hacer uno con algún código.
¿Qué es un DAG?
Entonces, ¿qué significa eso? Un DAG es un gráfico que fluye en una dirección, donde ningún elemento puede ser hijo de sí mismo. Así que la mayoría de nosotros estamos familiarizados con listas de enlaces, árboles e incluso gráficos. Un DAG es muy similar a los dos primeros, y una implementación del tercero.
Como mínimo, un DAG de 4 cosas:
- Nodos: Un lugar para almacenar los datos.
- Bordes dirigidos: Flechas que apuntan en una dirección (lo que hace que esta estructura de datos sea diferente)
- Algún gran nodo ancestral sin padres. (Dato curioso: La mayoría de los árboles de ascendencia son en realidad DAG y no en realidad árboles porque los primos en algún momento se casan entre sí.)
- Hojas: Nodos sin hijos
Hagamos uno
Así que escribamos algo de código. Primero, vamos a crear un constructor con dos propiedades y llamarlo DAG.
function DAG() {
this.nodes = ;
this.vertices = {};
}
A continuación añadiremos un método add. ¿Ves lo que hice allí?
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;
};
Entonces, ¿cómo funciona esto? El objeto vértice es donde suceden todas las cosas buenas. Agregamos un nodo, un objeto de nodos entrantes, y una matriz con todos sus nombres, un booleano sobre si apunta a algo y un valor. Llegaremos a algunos de estos un poco más tarde.
Ahora vamos a añadir algunos bordes y hacer que las cosas se conecten entre sí. Antes de que podamos hacer eso, tenemos que crear una función auxiliar que comprueba si hemos visitado ese nodo o no. Llamémoslo 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();
}
Lo que sucede aquí es
Vamos a dar crédito Donde realmente se debe
Investigando este artículo, leí algunos mensajes geniales de personas increíblemente inteligentes y la mayor parte de la información provino de ellos. Aprendí la mayor parte de la teoría leyendo este post bien escrito sobre DAG y control de versiones. El código aquí tiene toda su inspiración en el código fuente emberjs y los brillantes autores detrás de él. También he leído muchos otros artículos y publicaciones de blog sobre DAGs de grandes personas en Internet. Gracias por leer!