Переписывание графов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример правила переписывания графа (оптимизация из построения компиляторов: умножение на 2 заменяется сложением)

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

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

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

См. также

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

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

• Rozenberg, Grzegorz (1997), Handbook of Graph Grammars and Computing by Graph Transformations, World Scientific Publishing, volumes 1–3, ISBN 9810228848, <http://www.informatik.uni-trier.de/~ley/db/conf/gg/handbook1997.html> .
• Perez, P.P. (2009), Matrix Graph Grammars: An Algebraic Approach to Graph Dynamics, VDM Verlag, ISBN 978-3-639-21255-6 .
• Геккель, Р. (2006). Преобразование графов в двух словах. Электронные Примечания в теоретической информатике 148 (1 спецификаций. МКС.), ПП. 187-198.
• Кёниг, Барбара (2004). Анализ и проверка систем с динамически меняющейся структурой. Докторская диссертация, Университет Штутгарта, ПП. 65-180.
• Lobo, Daniel. Graph grammars with string-regulated rewriting (англ.) // Theoretical Computer Science. — 2011. — 1 October (vol. 412, no. 43). — P. 6101—6111. — ISSN 0304-3975. — doi:10.1016/j.tcs.2011.07.004.