Gráfico de dependencia

Gráfico dirigido que representa dependencias

En matemáticas , informática y electrónica digital , un grafo de dependencia es un grafo dirigido que representa las dependencias de varios objetos entre sí. Es posible derivar un orden de evaluación o la ausencia de un orden de evaluación que respete las dependencias dadas a partir del grafo de dependencia.

Definición

A depende de B y C ; B depende de D

Dado un conjunto de objetos y una relación transitiva con modelado de una dependencia " a depende de b " (" a necesita que b se evalúe primero"), el gráfico de dependencia es un gráfico con la reducción transitiva de R. ${\displaystyle S}$ ${\displaystyle R\subseteq S\times S}$ ${\displaystyle (a,b)\in R}$ ${\displaystyle G=(S,T)}$ ${\displaystyle T\subseteq R}$

Por ejemplo, supongamos que tenemos una calculadora sencilla. Esta calculadora permite asignar valores constantes a las variables y asignar la suma de exactamente dos variables a una tercera variable. Dadas varias ecuaciones como " A = B + C ; B = 5+ D ; C =4; D =2;", entonces y . Esta relación se puede derivar directamente: A depende de B y C , porque se pueden sumar dos variables si y solo si se conocen los valores de ambas variables. Por lo tanto, B debe calcularse antes de que A pueda calcularse. Como B depende de D para calcularse, A también debe depender de D para calcularse antes (de ahí la propiedad transitiva indicada anteriormente). Por otro lado, los valores de C y D se conocen inmediatamente, porque son literales numéricos. ${\displaystyle S=\{A,B,C,D\}}$ ${\displaystyle R=\{(A,B),(A,C),(B,D),(A,D)\}}$

Reconociendo evaluaciones imposibles

En un gráfico de dependencias, los ciclos de dependencias (también llamados dependencias circulares ) conducen a una situación en la que no existe un orden de evaluación válido, porque ninguno de los objetos en el ciclo puede evaluarse primero. Si un gráfico de dependencias no tiene ninguna dependencia circular, forma un gráfico acíclico dirigido y se puede encontrar un orden de evaluación mediante ordenamiento topológico . La mayoría de los algoritmos de ordenamiento topológico también son capaces de detectar ciclos en sus entradas; sin embargo, puede ser deseable realizar la detección de ciclos por separado del ordenamiento topológico para proporcionar un manejo adecuado para los ciclos detectados.

Supongamos que la calculadora es sencilla. El sistema de ecuaciones " A = B ; B = D + C ; C = D + A ; D = 12" contiene una dependencia circular formada por A , B y C , ya que B debe evaluarse antes que A , C debe evaluarse antes que B y A debe evaluarse antes que C.

Derivación de una orden de evaluación

Un orden de evaluación correcto es una numeración de los objetos que forman los nodos del grafo de dependencia de modo que se cumpla la siguiente ecuación: con . Esto significa que, si la numeración ordena dos elementos y de modo que se evaluarán antes que , entonces no deben depender de . ${\displaystyle n:S\rightarrow \mathbb {N} }$ ${\displaystyle n(a)<n(b)\Rightarrow (a,b)\notin R}$ ${\displaystyle a,b\in S}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$

Puede haber más de un orden de evaluación correcto. De hecho, una numeración correcta es un orden topológico , y cualquier orden topológico es una numeración correcta. Por lo tanto, cualquier algoritmo que derive un orden topológico correcto deriva un orden de evaluación correcto.

Supongamos una vez más la calculadora simple de arriba. Dado el sistema de ecuaciones " A = B + C ; B = 5+ D ; C = 4; D = 2;", un orden de evaluación correcto sería ( D , C , B , A ). Sin embargo, ( C , D , B , A ) también es un orden de evaluación correcto.

Estructura monoide

Un gráfico de dependencia acíclica corresponde a una traza de un monoide de traza como sigue: ^{[1] : 12}

• Una función etiqueta cada vértice con un símbolo del alfabeto. ${\displaystyle \phi :S\to \Sigma }$ ${\displaystyle \Sigma }$
• Hay una arista o si y sólo si está en la relación de dependencia . ${\displaystyle a\to b}$ ${\displaystyle b\to a}$ ${\displaystyle (\phi (a),\phi (b))}$ ${\displaystyle D}$
• Se consideran dos gráficos iguales si sus etiquetas y aristas corresponden.

Entonces, la cadena que consta de las etiquetas de vértice ordenadas por un orden de evaluación correcto corresponde a una cadena de una traza.

La operación monoidal toma la unión disjunta de los conjuntos de vértices de dos gráficos, conserva las aristas existentes en cada gráfico y dibuja nuevas aristas desde el primero hasta el segundo donde la relación de dependencia lo permite, ^{[1] : 14} ${\displaystyle (S_{12},R_{12})=(S_{1},R_{1})\bullet (S_{2},R_{2})}$ ${\displaystyle S_{12}=S_{1}\sqcup S_{2}}$

${\displaystyle R_{12}=R_{1}\sqcup R_{2}\sqcup \{(a,b)\mid a\in S_{1}\land b\in S_{2}\land (\phi (a),\phi (b))\in D\}}$

La identidad es el gráfico vacío.

Ejemplos

Los gráficos de dependencia se utilizan en:

• Instaladores de software automatizados : recorren el gráfico en busca de paquetes de software necesarios pero que aún no están instalados. La dependencia se da mediante el acoplamiento de los paquetes.
• Scripts de compilación de software como Unix Make , Node npm install, php composer, Twitter bower install o Apache Ant . Necesitan saber qué archivos han cambiado, por lo que solo es necesario volver a compilar los archivos correctos.
• En tecnología de compiladores e implementación de lenguaje formal :
  • Programación de instrucciones : se calculan gráficos de dependencia para los operandos de instrucciones de ensamblaje o intermedias y se utilizan para determinar un orden óptimo para las instrucciones.
  • Eliminación de código muerto : si ninguna operación con efectos secundarios depende de una variable, dicha variable se considera muerta y se puede eliminar.
• Análisis de gráficos dinámicos: GraphBolt ^[2] y KickStarter ^[3] capturan dependencias de valores para el cálculo incremental cuando cambia la estructura del gráfico.
• Calculadoras de hojas de cálculo . Deben derivar un orden de cálculo correcto similar al del ejemplo utilizado en este artículo.
• Estándares de formularios web como XForms para saber qué elementos visuales actualizar si cambian los datos en el modelo.
• Los videojuegos, especialmente los videojuegos de rompecabezas y aventuras , frecuentemente están diseñados como un gráfico de relaciones dependientes entre las acciones del juego. ^[4]

Los gráficos de dependencia son un aspecto de:

• Tipos de plantas de fabricación : Las materias primas se procesan en productos a través de varias etapas dependientes.
• Programación de talleres : una colección de problemas teóricos relacionados en informática.

Véase también

• Gráfico de llamadas
• Gráfico de precedencia
• Ordenación topológica
• Dependencia de datos

Referencias

1. Mazurkiewicz, Antoni (1995). "Introducción a la teoría de las trazas" (PDF) . En Rozenberg, G.; Diekert, V. (eds.). El libro de las trazas . Singapur: World Scientific. ISBN 981-02-2058-8. Recuperado el 18 de abril de 2021 .
2. Mugilan Mariappan; Keval Vora (2019). "GraphBolt: procesamiento sincrónico basado en dependencias de gráficos en streaming". En la Conferencia Europea sobre Sistemas Informáticos (EuroSys'19) . págs. 25:1–25:16. doi :10.1145/3302424.3303974.
3. Keval Vora; Rajiv Gupta; Guoqing Xu (2017). "KickStarter: cálculos rápidos y precisos en gráficos de transmisión mediante aproximaciones recortadas". En la Conferencia internacional sobre soporte arquitectónico para lenguajes de programación y sistemas operativos (ASPLOS'17) . págs. 237–251. doi : 10.1145/3093337.3037748 .
4. Gilbert, Ron. "Cuadros de dependencia de rompecabezas". Grumpy Gamer . Consultado el 11 de enero de 2020 .

• Balmas, Francoise (2001) Visualización de gráficos de dependencia: un enfoque jerárquico Archivado el 11 de febrero de 2012 en Wayback Machine , [1] wcre, p. 261, Octava Conferencia de Trabajo sobre Ingeniería Inversa (WCRE'01)