Que es un dag

Ordenación topológica

En matemáticas, especialmente en teoría de grafos, y en informática, un grafo acíclico dirigido (DAG) es un grafo dirigido sin ciclos dirigidos. Es decir, está formado por vértices y aristas (también llamados arcos), con cada arista dirigida de un vértice a otro, de tal forma que siguiendo esas direcciones nunca se formará un bucle cerrado. Un grafo dirigido es un DAG si y sólo si puede ordenarse topológicamente, disponiendo los vértices según un orden lineal que sea coherente con todas las direcciones de las aristas. Los DAG tienen numerosas aplicaciones científicas y computacionales, desde la biología (evolución, árboles genealógicos, epidemiología) a las ciencias de la información (redes de citas) o la computación (programación).

Un grafo está formado por vértices y por aristas que conectan pares de vértices, donde los vértices pueden ser cualquier tipo de objeto conectado por pares mediante aristas. En el caso de un grafo dirigido, cada arista tiene una orientación, de un vértice a otro vértice. Un camino en un grafo dirigido es una secuencia de aristas que tiene la propiedad de que el vértice final de cada arista de la secuencia es el mismo que el vértice inicial de la siguiente arista de la secuencia; un camino forma un ciclo si el vértice inicial de su primera arista es igual al vértice final de su última arista. Un grafo acíclico dirigido es un grafo dirigido que no tiene ciclos[1][2][3].

El camino más largo en dag

Si trabajas con dbt, Airflow o Dagster, no tardarás en encontrarte con el concepto de DAG: grafos acíclicos dirigidos. Pero, ¿qué es exactamente un DAG? ¿Y por qué son un concepto tan importante en la ingeniería de datos?

Empecemos por el grafo: no estamos hablando de un gráfico. Se trata de un tipo de grafo de la "teoría de grafos", que es una forma de representar objetos y las relaciones entre ellos. En ingeniería de datos, los objetos (o "nodos") representados en el gráfico suelen ser una tarea que debe ejecutar un ordenador ("construir esta tabla", "extraer estos datos"). Las relaciones entre los objetos son las dependencias entre ellos ("esto tiene que ocurrir antes que aquello"). Por último, en un DAG no puede haber ciclos: ésa es la parte acíclica.

Si nada de esto tiene sentido, ¡no pasa nada! Vamos a saltar a un ejemplo de la vida real para aprender algunos principios más, y podría hacer clic. Vamos a ver una actividad que hago varias veces al día, hacer café, representado como un DAG:

Algoritmos de grafos dirigidos

DefiniciónEn informática y matemáticas, un grafo acíclico dirigido (DAG) se refiere a un grafo dirigido que no tiene ciclos dirigidos.ExplicaciónEn teoría de grafos, un grafo se refiere a un conjunto de vértices que están conectados por líneas llamadas aristas. En un grafo dirigido o dígrafo, cada arista está asociada a una dirección desde un vértice inicial hasta un vértice final. Si recorremos la dirección de las aristas y comprobamos que no se forman bucles cerrados en ningún camino, decimos que no hay ciclos dirigidos. El grafo formado es un grafo acíclico dirigido.Un DAG siempre está topológicamente ordenado, es decir, para cada arista del grafo, el vértice inicial de la arista aparece antes en la secuencia que el vértice final de la arista.EjemploEn el grafo dirigido anterior, si encontramos los caminos desde cualquier nodo, digamos u, nunca encontraremos un camino que vuelva a u. Por lo tanto, se trata de un DAG.Áreas de aplicaciónAlgunas de las principales áreas de aplicación de los DAG son.

Dagitty

El grafo acíclico dirigido (DAG) es un esquema más expresivo que un modelo absolutamente lineal. Un DAG es una estructura de información o datos que puede utilizarse para demostrar diversos problemas. Se trata de un grafo acíclico ordenado topológicamente. Cada arista dirigida tiene un orden determinado seguido del nodo. Cada DAG comienza con un nodo que no tiene padres y termina con uno que no tiene hijos. Estos grafos nunca son cíclicos. Un DAG se compone de un conjunto de nodos y flechas donde las flechas se dirigen de un nodo a otro.

¿Ha oído el término DAG coins y ha pensado que es el nombre de una nueva criptomoneda? Si la respuesta es afirmativa, probablemente esté cerca de la idea... En realidad, todas las monedas digitales que hacen uso de DAG (grafos acíclicos dirigidos) se denominan monedas DAG.

El propósito básico de las criptomonedas basadas en blockchain era proporcionar un sustituto descentralizado, escalable, robusto y rápido para las transacciones financieras a través de múltiples medios. De hecho, todo el mérito de una idea tan revolucionaria recae en blockchain. Pero, ¿es blockchain lo suficientemente eficiente para proporcionar todo esto?