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

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

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

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

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

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

С точки зрения подхода DPO правило переписывания графа это пара морфизмов в категории графов и гомоморфизмы графа между ними: (или ), где инъективно. Граф называется инвариантным или иногда склеивающим графом. Шаг переписывания или применение правила к исходному графу определяется двумя диаграммами кодекартова квадрата, обе ведущими в один и тот же морфизм , где это контекстный граф (откуда и происходит название double-pushout). Другой морфизм графа моделирует вхождение в и называется сопоставлением. Практическим пониманием этого является то, что является подграфом, который сопоставляется из (смотри задачу поиска изоморфного подграфа), и после того, как совпадение найдено, заменяется на в исходном графе , где служит интерфейсом, содержащим узлы и рёбра, которые при применении правила были сохранены. Граф необходим для того, чтобы присоединить образец, сопоставляющийся его контексту: если он пуст, совпадение может обозначать только весь связанный компонент графа .

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

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

Существует также другой алгебраический подход к переписыванию графов, основанный в основном на булевой алгебре и алгебре матриц, называющийся матричными графовыми грамматиками. covers this approach in detail.This topic is expanded at mat2gra.info .

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

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

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

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

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

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

Графы являются выразительным, визуально и математически точным формализмом моделирования объектов (субъектов), связанных отношениями; объекты представлены в виде узлов, а отношения между ними рёбрами. Узлы и ребра обычно типизированы и атрибутированы. Вычисления описываются в этой модели как изменения в отношениях между субъектами или как изменения атрибутов элементов графа. Они кодируются в правилах переписывания графов или преобразования графов и исполняются с помощью инструментов переписывания графов/преобразования графов. Инструменты, нейтральные к предметной области приложения: AGG, система атрибутивной графовой грамматики (Java). GP (Graph Programs) , язык программирования для вычислений на графах с непосредственным применением правил преобразования графов. GMTE (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 — парсер английского языка, который использует переписывание графов для преобразования ссылочного разбора в зависимости разбора.

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

Примечания

Список литературы . . Геккель, Р. (2006). Преобразование графов в двух словах. Электронные Примечания в теоретической информатике 148 (1 спецификаций. МКС.), ПП. 187—198. Кёниг, Барбара (2004). Анализ и проверка систем с динамически меняющейся структурой. Докторская диссертация, Университет Штутгарта, ПП. 65-180.

Категория:Операции над графами