¿Qué es un DAG?

Un DAG o gráfico acíclico dirigido es un tipo de gráfico en el que los nodos están vinculados por conexiones unidireccionales que no forman ningún ciclo. Los DAG se utilizan para ilustrar las dependencias y las relaciones causales.

Al igual que todos los gráficos, los DAG pueden ser útiles para visualizar relaciones entre nodos que representan datos, tareas o eventos. Sin embargo, los DAG son útiles para representar sistemas donde los eventos ocurren en un orden específico, como un cronograma de tareas que deben completarse para lograr un objetivo.

Los DAG también son importantes para crear diagramas causales: los DAG pueden representar sistemas en los que algunos nodos afectan a otros nodos, pero los efectos causales no funcionan en la dirección opuesta. Un ejemplo básico de este tipo de relaciones unidireccionales puede encontrarse en los árboles genealógicos, ya que los DAG trazan un mapa de generaciones sucesivas de padres e hijos.

La aplicación de DAG es común en informática, con desarrolladores e ingenieros que utilizan DAGS para canalizaciones de datos y procesamiento de datos, redes neuronales, robótica y más.

Para comprender mejor qué es un gráfico acíclico dirigido, analicemos sus componentes:

Nodos

Los nodos, también conocidos como vértices, representan entidades, objetos o variables en un gráfico. Suelen representarse como puntos o círculos.

Aristas

Las aristas representan conexiones entre entidades. Se representan como líneas.

Aristas dirigidas

Las aristas dirigidas representan conexiones que pueden recorrer en una sola dirección. Las flechas en dichos bordes indican su dirección.

Gráficos dirigidos

Los gráficos formados enteramente por aristas dirigidas son gráficos dirigidos o digráficos. Por el contrario, los gráficos sin aristas dirigidas son gráficos no dirigidos.

Colisionadores

Los colisionadores son nodos que tienen dos aristas dirigidas apuntando hacia ellos.

Rutas

Las rutas son una secuencia de aristas que conectan un nodo dado a otro. Las rutas que consisten completamente en aristas dirigidas se conocen como rutas dirigidas. Las rutas dirigidas que indican relaciones causales se denominan rutas causales.

Árbol

En informática, un árbol es un gráfico acíclico dirigido en el que cada nodo tiene solo una arista dirigida que apunta a él, excepto el nodo inicial (el nodo “raíz”). Aunque las aristas se extienden desde el nodo raíz, ninguna arista apunta al nodo raíz.

Además de comprender las partes de un DAG, también es importante reconocer un componente del que carece: un ciclo. El término “acíclico” en gráfico acíclico dirigido se refiere a la ausencia de ciclos o bucles cerrados en estos gráficos. En otras palabras, cuando se empieza en un nodo de un DAG y se recorren los nodos y las aristas siguientes, es imposible volver al nodo inicial.

En la teoría de gráficos (el estudio de gráficos), a menudo se aplican varios conceptos o procesos cuando se trabaja con gráficos acíclicos dirigidos. Entre las que se encuentran:

Una clasificación topológica, también conocida como ordenamiento topológico, es una forma de organizar los nodos de un DAG de manera lineal de modo que los nodos que apuntan a otros nodos aparezcan primero y los sucesores no aparezcan antes que sus predecesores. Los algoritmos de ordenamiento topológico pueden producir dichas secuencias basadas en DAG.¹

En gráficos complicados, puede ser difícil reconocer qué nodos pueden ser “accesibles” por rutas dirigidas desde otros nodos. En el cierre transitivo, estos enlaces indirectos entre nodos se identifican y diagraman.

Por ejemplo, si un gráfico tiene una arista dirigida que une el nodo A y el nodo B y otra arista dirigida que une el nodo B y el nodo C, eso indicaría que A y C están vinculados indirectamente. Un cierre transitivo daría como resultado una nueva arista dirigida que conectaría A con C, ahora el camino más corto entre estos dos nodos, además de las aristas dirigidas originales entre A y B y B y C. Al igual que con la ordenación topológica, se pueden utilizar algoritmos para los cálculos de cierre transitivo.

La reducción transitiva puede considerarse lo contrario del cierre transitivo. En el contexto de un gráfico dirigido, la reducción transitiva del gráfico tiene el mismo número de nodos que el gráfico original y los pares de nodos a los que se puede acceder son los mismos. Sin embargo, el número de aristas en la reducción transitiva del gráfico se minimiza.

Consideremos, por ejemplo, un gráfico original que incluye una arista dirigida que vincula el nodo A con el nodo C, y una secuencia de aristas dirigidas que vinculan el nodo A con el nodo B y el nodo B con el nodo C. Una reducción transitiva de ese gráfico excluiría la arista entre A y C manteniendo las aristas entre el conjunto más grande de variables: A y B y B y C.

En otras palabras, la ruta más larga entre A y C en el gráfico original se incluye en el nuevo gráfico, mientras que la ruta con solo una arista se elimina. 

Los gráficos acíclicos dirigidos ocupan un lugar destacado en la ciencia informática a través de una serie de casos de uso:

Los DAG ayudan a los ingenieros de datos a definir estructuras de datos y lograr la optimización de los flujos de datos. Las plataformas de orquestación de datos como Apache Airflow, por ejemplo, emplean DAGs (definidos en scripts de Python) para definir tareas de procesamiento de datos y especificar su orden de ejecución en pipelines de datos y flujos de trabajo.

En los casos en los que varios DAG dependen unos de otros, las herramientas de orquestación pueden crear gráficos de dependencias para aclarar esas relaciones.² Plataformas de observabilidad de los datos se pueden utilizar junto con plataformas de orquestación de datos para identificar y dirigirse a los problemas de canalización de datos.

La aceleración de la adopción de aplicaciones generativas de inteligencia artificial, que se basan en el acceso a datos, ha amplificado la importancia de las canalizaciones de datos y los DAG en el panorama tecnológico moderno.

Una red neuronal es un programa de machine learning que decide de manera similar al cerebro humano mediante el uso de procesos que imitan la forma en que las neuronas biológicas trabajan juntas para hacer observaciones y llegar a conclusiones. Los DAG se utilizan para mapear redes neuronales y pueden ser especialmente útiles en la visualización de redes neuronales profundas con múltiples capas.

Los DAG pueden desempeñar un papel en los esfuerzos por “enseñar” a los modelos de IA a reconocer relaciones causales a través de la inferencia causal. La inferencia causal es un paradigma para determinar los efectos causales y, a menudo, emplea DAG. Por ejemplo, los DAG pueden ayudar a detectar “factores de confusión”, que son variables que distorsionan u oscurecen la causalidad real. La IA potenciada con inferencia causal está emergiendo como una herramienta en epidemiología en particular, con el potencial de ayudar a los investigadores en sus investigaciones de determinantes de enfermedades.³

Los investigadores han propuesto utilizar un método de planificación estructural basado en DAG y modelos de lenguaje amplio para mejorar el rendimiento de los robots de doble brazo. En el marco propuesto, un LLM genera un DAG que representa tareas complejas como subtareas, con aristas que indican las dependencias entre ellas. Esta información se utiliza para ayudar a determinar la planificación del movimiento y la coordinación entre los dos brazos para la ejecución de la tarea.⁴

Los DAG se utilizan para optimizar el diseño de los compiladores, que son programas que convierten los lenguajes de programación (código fuente) en instrucciones para los ordenadores (código máquina). Por ejemplo, un DAG puede ayudar a identificar subexpresiones comunes que pueden eliminarse para mejorar la eficacia.

Según los investigadores, una blockchain basada en un DAG demuestra un mejor rendimiento que las blockchains convencionales. Una blockchain basada en DAG puede permitir el procesamiento paralelo de transacciones, lo que aumenta la tasa de transacciones procesadas en un período determinado y permite una mayor flexibilidad y escalabilidad. Estas mejoras pueden tener aplicaciones en áreas como la gestión de la cadena de suministro y los controles de acceso para las redes de Internet de las cosas.^{5, 6}