Gráfico de dependencia

Este artículo incluye una lista de referencias generales , pero carece de suficientes citas en línea correspondientes . Por favor, ayude a mejorar este artículo introduciendo citas más precisas. ( Junio ​​de 2013 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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.

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.${\estilo de visualización S}$ ${\displaystyle R\subseteq S\times S}$${\displaystyle (a,b)\en 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)\}}$

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.

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)\Flecha derecha (a,b)\no en R}$${\displaystyle a,b\en S}$${\estilo de visualización a}$${\estilo de visualización b}$${\estilo de visualización a}$${\estilo de visualización b}$${\estilo de visualización a}$${\estilo de visualización 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.

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 }$${\estilo de visualización \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))}$ ${\estilo de visualización 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\en S_{1}\land b\en S_{2}\land (\phi (a),\phi (b))\en D\}}$

La identidad es el gráfico vacío.

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.

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

• 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)