Gráfico de dependencia

En matemáticas, informática y electrónica digital, un grafo de dependencias 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 dependencias.

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

Por ejemplo, asuma una calculadora simple. Esta calculadora soporta la asignación de valores constantes a variables y asignando 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${\displaystyle S=\{A,B,C,D}$ y ${\displaystyle R=\{(A,B),(A,C),(B,D)}$. Puede derivar esta relación directamente: A depende de B y C, porque puede añadir dos variables si y sólo si conoce los valores de ambas variables. Así, B debe calcularse antes A se puede calcular. Sin embargo, los valores de C y D son conocidos inmediatamente, porque son números literales.

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 del 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.

A orden de evaluación correcto es una numeración ${\displaystyle n:S\rightarrow \mathbb {N}$ de los objetos que forman los nodos del gráfico de dependencia para que la siguiente ecuación tenga: ${\displaystyle n(a) won(b)\Rightarrow (a,b)\notin R}$ con ${\displaystyle a,b\in S}$. Esto significa, si la numeración ordena dos elementos ${\displaystyle a}$ y ${\displaystyle b}$ así ${\displaystyle a}$ será evaluado antes ${\displaystyle b}$Entonces ${\displaystyle a}$ no debe depender de ${\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 derivará un orden de evaluación correcto.

Supongamos una vez más que utilizamos 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.

Un gráfico de dependencia acíclica corresponde a una traza de un monoide de traza de la siguiente manera:

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

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

La operación monoidal ${\displaystyle (S_{12},R_{12})=(S_{1},R_{1})\bullet (S_{2},R_{2})}$ toma la unión descomunal ${\displaystyle S_{12}=S_{1}\sqcup S_{2}$ de dos conjuntos de vértice de gráficos, conserva los bordes existentes en cada gráfico, y dibuja nuevos bordes del primero al segundo donde la relación de dependencia permite,

${\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.

Los gráficos de dependencia se utilizan en:

• instaladores de software automatizados: Caminan el gráfico buscando paquetes de software que son necesarios pero no instalados. La dependencia es dada por el acoplamiento de los paquetes.
• Software construye scripts como Unix Make, Node npm install, php composer, Twitter bower install, o Apache Ant. Necesitan saber qué archivos han cambiado así que sólo los archivos correctos necesitan ser recompilados.
• En la tecnología compiladora y la aplicación formal del lenguaje:
  • Programación de instrucciones: Los gráficos de dependencia se computan para el funcionamiento de las instrucciones de montaje o intermedia y se utilizan para determinar un orden óptimo para las instrucciones.
  • Eliminación del código muerto: Si ninguna operación de efecto secundario depende de una variable, esta variable se considera muerta y se puede eliminar.
• Análisis dinámico del gráfico: Las dependencias de valor de captura de GraphBolt y KickStarter para el cálculo incremental cuando la estructura de gráficos cambia.
• Calculadoras de hoja de cálculo. Necesitan derivar una orden de cálculo correcta similar a esa en el ejemplo utilizado en este artículo.
• Normas Web Forms como XForms para saber qué elementos visuales actualizar si los datos del modelo cambian.
• Videojuegos, especialmente rompecabezas y videojuegos de aventura, que son diseñados frecuentemente como un gráfico de relaciones dependientes entre acciones en el juego.

Los gráficos de dependencia son un aspecto de:

• Tipos de fábrica: Las materias primas se procesan en productos a través de varias etapas dependientes.
• Tienda de trabajo programando: Una colección de problemas teóricos relacionados en la informática.

• Llama al gráfico
• Tipo topológico
• Dependencia de datos

• Balmas, Francoise (2001) Mostrando gráficos de dependencia: un enfoque jerárquico Archived 2012-02-11 en la máquina Wayback, [1] wcre, p. 261, Octava Conferencia de Trabajo sobre Ingeniería Inversa (WCRE'01)