Reescritura de gráficos

En informática , la transformación de gráficos o reescritura de gráficos se refiere a la técnica de crear un nuevo gráfico a partir de un gráfico original de forma algorítmica. Tiene numerosas aplicaciones, que van desde la ingeniería de software ( construcción de software y también verificación de software ) hasta algoritmos de diseño y generación de imágenes.

Las transformaciones de grafos se pueden utilizar como una abstracción computacional. La idea básica es que si el estado de un cómputo se puede representar como un grafo, los pasos posteriores de ese cómputo se pueden representar como reglas de transformación en ese grafo. Dichas reglas consisten en un grafo original, que se debe hacer coincidir con un subgrafo en el estado completo, y un grafo de reemplazo, que reemplazará al subgrafo coincidente.

Formalmente, un sistema de reescritura de grafos suele constar de un conjunto de reglas de reescritura de grafos de la forma , siendo llamado grafo de patrón (o lado izquierdo) y siendo llamado grafo de reemplazo (o lado derecho de la regla). Una regla de reescritura de grafos se aplica al grafo anfitrión buscando una ocurrencia del grafo de patrón ( coincidencia de patrones , resolviendo así el problema de isomorfismo de subgrafos ) y reemplazando la ocurrencia encontrada por una instancia del grafo de reemplazo. Las reglas de reescritura se pueden regular aún más en el caso de grafos etiquetados , como en las gramáticas de grafos reguladas por cadenas. ${\displaystyle L\rightarrow R}$${\estilo de visualización L}$${\estilo de visualización R}$

A veces, la gramática de gráficos se utiliza como sinónimo de sistema de reescritura de gráficos , especialmente en el contexto de lenguajes formales ; la redacción diferente se utiliza para enfatizar el objetivo de las construcciones, como la enumeración de todos los gráficos a partir de un gráfico inicial, es decir, la generación de un lenguaje de gráficos, en lugar de simplemente transformar un estado dado (gráfico anfitrión) en un nuevo estado.

El enfoque algebraico para la reescritura de grafos se basa en la teoría de categorías . El enfoque algebraico se divide a su vez en subenfoques, los más comunes de los cuales son el enfoque de doble empuje (DPO) y el enfoque de empuje simple (SPO) . Otros subenfoques incluyen el enfoque de sesqui-pushout y el enfoque de pullback .

Desde la perspectiva del enfoque DPO, una regla de reescritura de grafos es un par de morfismos en la categoría de grafos y homomorfismos de grafos entre ellos: , también escrito , donde es inyectivo . El grafo K se llama invariante o, a veces, grafo de unión . Un paso de reescritura o aplicación de una regla r a un grafo anfitrión G se define por dos diagramas de expulsión , ambos originados en el mismo morfismo , donde D es un grafo de contexto (de aquí proviene el nombre de doble expulsión). Otro morfismo de grafo modela una ocurrencia de L en G y se llama coincidencia . La comprensión práctica de esto es que es un subgrafo que se empareja desde (ver problema de isomorfismo de subgrafo ), y después de que se encuentra una coincidencia, se reemplaza con en el grafo anfitrión donde sirve como una interfaz, que contiene los nodos y los bordes que se conservan al aplicar la regla. El grafo es necesario para adjuntar el patrón que se está emparejando a su contexto: si está vacío, la coincidencia solo puede designar un componente conectado completo del grafo . ${\displaystyle r=(L\leftarrow K\rightarrow R)}$${\displaystyle L\supseteq K\subseteq R}$${\displaystyle K\rightarrow L}$ ${\displaystyle k\colon K\rightarrow D}$${\displaystyle m\colon L\rightarrow G}$${\estilo de visualización L}$${\estilo de visualización G}$${\estilo de visualización L}$${\estilo de visualización R}$${\estilo de visualización G}$${\estilo de visualización K}$${\estilo de visualización K}$${\estilo de visualización G}$

En contraste, una regla de reescritura de grafos del enfoque SPO es un único morfismo en la categoría de multigrafos etiquetados y mapeos parciales que preservan la estructura del multigrafo: . Por lo tanto, un paso de reescritura se define mediante un único diagrama de expulsión . La comprensión práctica de esto es similar al enfoque DPO. La diferencia es que no hay una interfaz entre el grafo anfitrión G y el grafo G' que es el resultado del paso de reescritura. ${\displaystyle r\colon L\rightarrow R}$

Desde una perspectiva práctica, la distinción clave entre DPO y SPO es cómo tratan la eliminación de nodos con aristas adyacentes, en particular, cómo evitan que dichas eliminaciones puedan dejar "aristas colgantes". El enfoque DPO solo elimina un nodo cuando la regla especifica también la eliminación de todas las aristas adyacentes (esta condición de aristas colgantes se puede comprobar para una coincidencia determinada), mientras que el enfoque SPO simplemente elimina las aristas adyacentes, sin requerir una especificación explícita.

Existe también otro enfoque de tipo algebraico para la reescritura de gráficos, basado principalmente en el álgebra de Boole y un álgebra de matrices, llamadas gramáticas de gráficos matriciales . ^[1]

Otro enfoque para la reescritura de gráficos, conocido como reescritura de gráficos determinada , surgió de la lógica y la teoría de bases de datos . ^[2] En este enfoque, los gráficos se tratan como instancias de bases de datos y las operaciones de reescritura como un mecanismo para definir consultas y vistas; por lo tanto, se requiere que toda reescritura produzca resultados únicos ( hasta el isomorfismo ), y esto se logra aplicando cualquier regla de reescritura simultáneamente en todo el gráfico, donde sea que se aplique, de tal manera que el resultado esté realmente definido de manera única.

Otro enfoque para la reescritura de gráficos es la reescritura de gráficos de términos , que implica el procesamiento o la transformación de gráficos de términos (también conocidos como gráficos semánticos abstractos ) mediante un conjunto de reglas de reescritura sintáctica.

Los gráficos de términos son un tema destacado en la investigación de lenguajes de programación, ya que las reglas de reescritura de gráficos de términos son capaces de expresar formalmente la semántica operacional de un compilador . Los gráficos de términos también se utilizan como máquinas abstractas capaces de modelar cálculos químicos y biológicos, así como cálculos gráficos como los modelos de concurrencia. Los gráficos de términos pueden realizar verificación automatizada y programación lógica, ya que son adecuados para representar declaraciones cuantificadas en lógica de primer orden. El software de programación simbólica es otra aplicación para los gráficos de términos, que son capaces de representar y realizar cálculos con estructuras algebraicas abstractas como grupos, campos y anillos.

La conferencia TERMGRAPH ^[3] se centra enteramente en la investigación sobre la reescritura de gráficos de términos y sus aplicaciones.

Los sistemas de reescritura de grafos se agrupan naturalmente en clases según el tipo de representación de grafos que se utilizan y cómo se expresan las reescrituras. El término gramática de grafos, que también es equivalente a sistema de reescritura de grafos o sistema de reemplazo de grafos, se utiliza con más frecuencia en las clasificaciones. Algunos tipos comunes son:

• Gramáticas de gráficos atribuidas , generalmente formalizadas mediante el enfoque de expulsión simple o el enfoque de expulsión doble para caracterizar los reemplazos, mencionados en la sección anterior sobre el enfoque algebraico para la reescritura de gráficos.
• Gramáticas de hipergrafos, incluidas como subclases más restrictivas las gramáticas de gráficos de puertos, las gramáticas de gráficos lineales y las redes de interacción .

Los grafos son un formalismo expresivo, visual y matemáticamente preciso para modelar objetos (entidades) vinculados por relaciones; los objetos se representan mediante nodos y las relaciones entre ellos mediante aristas. Los nodos y las aristas suelen estar tipificados y atribuidos. Los cálculos se describen en este modelo mediante cambios en las relaciones entre las entidades o mediante cambios de atributos de los elementos del grafo. Se codifican en reglas de reescritura/transformación de grafos y se ejecutan mediante sistemas de reescritura/herramientas de transformación de grafos.

• Herramientas que son neutrales en cuanto al dominio de la aplicación:
  • AGG, el sistema de gramática de gráficos atribuidos ( Java ).
  • GP 2 es un lenguaje de programación de gráficos basado en reglas visuales diseñado para facilitar el razonamiento formal sobre programas de gráficos.
  • GMTE Archivado el 13 de marzo de 2018 en Wayback Machine , el motor de transformación y emparejamiento de grafos . Es una implementación de una extensión del algoritmo de Messmer que utiliza C++ .
  • GrGen.NET , el generador de reescritura de gráficos, una herramienta de transformación de gráficos que emite código C# o ensamblajes .NET.
  • GROOVE, un conjunto de herramientas basado en Java para editar gráficos y reglas de transformación de gráficos, explorar los espacios de estados de las gramáticas de gráficos y verificar modelos de esos espacios de estados; también se puede utilizar como motor de transformación de gráficos.
  • Verigraph, un sistema de especificación y verificación de software basado en la reescritura de gráficos ( Haskell ).
• Herramientas que resuelven tareas de ingeniería de software (principalmente MDA ) con reescritura de gráficos:
  • eMoflon, una herramienta de transformación de modelos compatible con EMF con soporte para modelos basados ​​en historias y gramáticas de triple gráfico.
  • EMorF Archivado el 22 de abril de 2016 en Wayback Machine, un sistema de reescritura de gráficos basado en EMF , que admite la transformación in situ y de modelo a modelo .
  • Fujaba utiliza modelos basados ​​en historias, un lenguaje de reescritura de gráficos basado en PROGRES.
  • Las bases de datos de gráficos a menudo admiten la reescritura dinámica de gráficos.
  • Excelente .
  • Gremlin, un lenguaje de programación basado en gráficos (ver Reescritura de gráficos).
  • Henshin, un sistema de reescritura de gráficos basado en EMF , que admite la transformación in situ y de modelo a modelo , el análisis de pares críticos y la verificación de modelos .
  • PROGRES, un entorno integrado y lenguaje de muy alto nivel para sistemas de reescritura de gráficos programados.
  • Viatra .
• Herramientas de ingeniería mecánica
  • GraphSynth es un intérprete y un entorno de interfaz de usuario para crear gramáticas de gráficos sin restricciones, así como para probar y buscar la variante de lenguaje resultante. Guarda gráficos y reglas gramaticales de gráficos como archivos XML y está escrito en C# .
  • Soley Studio, es un entorno de desarrollo integrado para sistemas de transformación de grafos. Su principal foco de aplicación es el análisis de datos en el ámbito de la ingeniería.
• Aplicaciones de la biología
  • Modelado funcional-estructural de plantas con un lenguaje basado en gramática de grafos
  • Modelado del desarrollo multicelular con gramáticas de grafos reguladas por cadenas
  • Kappa es un lenguaje basado en reglas para modelar sistemas de agentes interactuantes, motivado principalmente por la biología de sistemas moleculares.
• Inteligencia artificial/procesamiento del lenguaje natural
  • OpenCog proporciona un comparador de patrones básico (en hipergrafos ) que se utiliza para implementar varios algoritmos de IA.
  • RelEx es un analizador en idioma inglés que emplea la reescritura de gráficos para convertir un análisis de enlace en un análisis de dependencia .
• Lenguaje de programación informática
  • El lenguaje de programación Clean se implementa utilizando reescritura de gráficos.

• Teoría de grafos
• Gramática de formas
• Gramática formal
• Reescritura abstracta : una generalización de la reescritura de gráficos