В информатике переписывание графов (также перезапись графов , преобразование графов , трансформация графов ) — техника по созданию нового графа из исходного графа алгоритмическим образом. Переписывание графов находит широкое применение в компьютерных науках, например, в конструировании программного обеспечения , в , в генерировании изображений, в компиляторах , в графовых базах данных .

Преобразования графов можно использовать в качестве абстракции вычислений. Основная идея заключается в том, что состояние вычисления может быть представлено в виде графа, дальнейшие шаги этого вычисления могут быть представлены как правила преобразования на этом графе. Такие правила состоят из исходного графа, который должен быть сопоставлен с подграфом полного состояния, и заменяющего графа, который заменит сопоставленный подграф.

Формально система переписывания графа обычно состоит из множества правил переписывания графа в форме ${\displaystyle L\rightarrow R}$ , где ${\displaystyle L}$ называется графом-образцом (или левой стороной), а ${\displaystyle R}$ называется заменяющим графом (или правой частью правила). Правило переписывания графа применяется к исходному графу путем поиска вхождения шаблонного графа ( сопоставление с образцом , тем самым решая проблему изоморфизма подграфа ) и замены найденного вхождения экземпляром заменяющего графа. Правила переписывания могут быть дополнительно упорядочены в случае помеченных графов , например, в графовых грамматиках, регулируемых строками.

Иногда понятие графовой грамматики используется в качестве синонима для системы переписывания графа, особенно в контексте формальных языков ; различные формулировки используются, чтобы подчеркнуть цель конструкций, таких как перечисление всех графов из некоторого начального графа, то есть генерация графового языка – вместо простого преобразования исходного состояния (хостового графа) в новое состояние.

Подходы к переписыванию графов

Алгебраический подход

Алгебраический подход к переписыванию графов основан на теории категории . Алгебраический подход подразделяется на субподходы, наиболее распространенными из которых являются подход и подход . Другие подходы включают sesqui-pushout и pullback .

С точки зрения подхода DPO правило переписывания графа это пара морфизмов в категории графов и гомоморфизмы графа между ними: ${\displaystyle r=(L\leftarrow K\rightarrow R)}$ (или ${\displaystyle L\supseteq K\subseteq R}$ ), где ${\displaystyle K\rightarrow L}$ инъективно . Граф ${\displaystyle K}$ называется инвариантным или иногда склеивающим графом . Шаг переписывания или применение правила ${\displaystyle r}$ к исходному графу ${\displaystyle G}$ определяется двумя диаграммами кодекартова квадрата , обе ведущими в один и тот же морфизм ${\displaystyle k\colon K\rightarrow D}$ , где ${\displaystyle D}$ это контекстный граф (откуда и происходит название double -pushout). Другой морфизм графа ${\displaystyle m\colon L\rightarrow G}$ моделирует вхождение ${\displaystyle L}$ в ${\displaystyle G}$ и называется сопоставлением . Практическим пониманием этого является то, что ${\displaystyle L}$ является подграфом, который сопоставляется из ${\displaystyle G}$ (смотри задачу поиска изоморфного подграфа ), и после того, как совпадение найдено, ${\displaystyle L}$ заменяется на ${\displaystyle R}$ в исходном графе ${\displaystyle G}$ , где ${\displaystyle K}$ служит интерфейсом, содержащим узлы и рёбра, которые при применении правила были сохранены. Граф ${\displaystyle K}$ необходим для того, чтобы присоединить образец, сопоставляющийся его контексту: если он пуст, совпадение может обозначать только весь связанный компонент графа ${\displaystyle G}$ .

Правило переписывания графа в подходе SPO это единственный морфизм в категории помеченных мультиграфов и частичных отображений, которые сохраняют структуру мультиграфа: ${\displaystyle r\colon L\rightarrow R}$ . Таким образом шаг переписывания определяется одной диаграммой кодекартова квадрата . Практическое понимание этого аналогично подходу DPO. Разница в том, что нет интерфейса между исходным графом ${\displaystyle G}$ и графом ${\displaystyle G'}$ , являющимся результатом шага переписывания.

С практической точки зрения ключевое различие между DPO и SPO заключается в том, как они относятся к удалению узлов со смежными рёбрами, в частности, как они избегают того, чтобы такие удаления могли оставить после "висячие рёбра". Подход DPO удаляет узел только тогда, когда правило определяет удаление всех смежных рёбер, а также (это условие для висячих может быть проверено для данного сопоставления), в то время как подход SPO просто размещает смежные рёбра, не требуя явной спецификации.

Существует также другой алгебраический подход к переписыванию графов, основанный в основном на булевой алгебре и алгебре матриц, называющийся матричными графовыми грамматиками .

Детерминированное переписывание графов

Еще один подход к переписыванию графов, известный как детерминированное переписывание графов, вышел из логики и . В этом подходе графы рассматриваются как экземпляры базы данных, а операции переписывания как механизм для определения запросов и представлений; поэтому всё переписывание требуется для получения уникальных результатов ( изоморфизма), и это достигается применением любого правила переписывания одновременно по всему графу, где бы оно ни применялось, таким образом, что результат действительно однозначно определен.

Переписывание абстрактного семантического графа

Другим подходом к переписыванию графов является переписывание абстрактного семантического графа (АСГ) , который предполагает обработку или преобразование АСГ посредством набора синтаксических правил переписывания.

Абстрактные семантические графы являются важным вопросом в исследованиях языков программирования, поскольку правила переписывания АСГ способны формально выражать операционную семантику компилятора. АСГ также используются в качестве приспособления абстрактной машины к моделированию химических и биологических вычислений, а также графических вычислений, таких как параллельные модели. АСГ может осуществлять автоматическую проверку (верификацию) и логическое программирование, так как они хорошо подходят к представлению количественных высказываний в логике первого порядка. Программное обеспечение для символического программирования -- другое приложение для АСГ, которое способно представлять и выполнять вычисления с абстрактными алгебраическими структурами, такими как группы, поля и кольца.

Конференция TERMGRAPH полностью фокусируется на исследованиях в области АСГ и их приложениях.

Классы графовых грамматик и систем переписывания графов

Системы переписывания графов, естественно, группируются в классы в зависимости от используемых видов представлений графов, и того как выражены переписывания. Грамматика абстрактного семантического графа, в противном случае эквивалентно системе переписывания графов или системе замены графов, наиболее часто используется в классификациях. Некоторые общие типы:

• Атрибутивные графовые грамматики , как правило, формализованы с помощью подхода single-pushout или подхода double-pushout к характеристике замен, указанных в предыдущем разделе об алгебраическом подходе к переписыванию графов.
• Грамматики гиперграфов, включая как более строгие подклассы портовые графовые грамматики, линейные графовые грамматики и взаимодействующие сети.

Реализации и применения

Графы являются выразительным, визуально и математически точным формализмом моделирования объектов (субъектов), связанных отношениями; объекты представлены в виде узлов, а отношения между ними рёбрами. Узлы и ребра обычно типизированы и атрибутированы. Вычисления описываются в этой модели как изменения в отношениях между субъектами или как изменения атрибутов элементов графа. Они кодируются в правилах переписывания графов или преобразования графов и исполняются с помощью инструментов переписывания графов/преобразования графов.

• Инструменты, нейтральные к предметной области приложения:
  • , система атрибутивной графовой грамматики ( Java ).
  • от 25 марта 2016 на Wayback Machine , язык программирования для вычислений на графах с непосредственным применением правил преобразования графов.
  • от 13 марта 2018 на Wayback Machine (Graph Matching and Transformation Engine) движок для сопоставления и преобразования графов. Является реализацией расширения алгоритма Messmer на C++ .
  • GrGen.NET (Graph rewrite Generator), инструмент преобразования графов с генерацией кода на C# или сборок .NET.
  • , набор инструментов на Java для редактирования графов и правил преобразования графов, для исследования пространств состояний граф-грамматик и проверки моделей этих пространств состояний; также может быть использован как движок преобразования графов.
  • , программная спецификация и система верификации, основанная на переписывании графов ( Haskell ).
• Инструменты для решения задач разработки программного обеспечения (в основном в рамках архитектуры, управляемой моделью (MDA) ) с использованием переписывания графов:
  • , инструмент преобразования моделей, совместимый с EMF и с поддержкой Story-Driven Modeling and тройственных графовых грамматик
    
  • система переписывания графов основанная на EMF и поддерживающая преобразования на месте и преобразования модель-модель.
  • использует моделирование управляемое сюжетом, язык переписывания графов основан на PROGRES
  • Графовые базы данных часто поддерживают динамическое переписывание графов.
  • GReAT
  • , язык программирования для работы с графами
  • , система переписывания графов на базе EMF , поддерживающая преобразования на месте и  преобразования модель-модель, анализ критических пар и проверку моделей
  • , интегрированная среда и очень высокоуровневый язык для программируемых систем переписывания графов.
  • VIATRA

• Инструменты для машиностроения:
  • представляет собой интерпретатор и пользовательскую среду языка для создания неограниченных графовых грамматик, а также тестирования и поиска равнодействующей. GraphSynth сохраняет графы и правила графовых грамматик в файлы XML и написан на языке C# .
  • , представляет собой интегрированную среду разработки для систем трансформации графов. Её основное применение фокусируется на анализе данных в области машиностроения.
• Применения в биологии:
• Искусственный интеллект, обработка естественного языка:
  • OpenCog предоставляет базовую поддержку сопоставления с образцом (на основе гиперграфов ), которая используется для реализации различных алгоритмов ИИ.
  • - парсер английского языка, который использует переписывание графов для преобразования ссылочного разбора в зависимости разбора .

См. также

• Теория категорий
• Теория графов
• Грамматика формы
• Формальная грамматика
• Абстрактный семантический граф

Примечания

Список литературы

• Rozenberg, Grzegorz (1997), , World Scientific Publishing, volumes 1–3, ISBN 9810228848 {{ citation }} : Указан более чем один параметр |ISBN= and |isbn= ( справка ) .
• Perez, P.P. (2009), Matrix Graph Grammars: An Algebraic Approach to Graph Dynamics , , ISBN 978-3-639-21255-6 {{ citation }} : Указан более чем один параметр |ISBN= and |isbn= ( справка ) .
• Геккель, Р. (2006). Преобразование графов в двух словах . 148 (1 спецификаций. МКС.), ПП. 187-198.
• Кёниг, Барбара (2004). Анализ и проверка систем с динамически меняющейся структурой . , ПП. 65-180.
• Lobo, Daniel. Graph grammars with string-regulated rewriting (англ.) // (англ.) ( . — 2011. — 1 October ( vol. 412 , no. 43 ). — P. 6101—6111 . — ISSN . — doi : .