В информатике преобразование графов или переписывание графов относится к методу алгоритмического создания нового графа из исходного графа. Он имеет множество применений, начиная от разработки программного обеспечения ( создания программного обеспечения , а также проверки программного обеспечения ) до алгоритмов компоновки и генерации изображений.
Преобразования графов можно использовать в качестве абстракции вычислений. Основная идея заключается в том, что если состояние вычисления можно представить в виде графа, то дальнейшие шаги в этом вычислении можно представить в виде правил преобразования на этом графе. Такие правила состоят из исходного графа, который должен быть сопоставлен с подграфом в завершенном состоянии, и замещающего графа, который заменит совпавший подграф.
Формально система переписывания графов обычно состоит из набора правил перезаписи графов вида , которые называются графом шаблона (или левой частью) и графом замены (или правой частью правила). Правило перезаписи графа применяется к главному графу путем поиска вхождения графа-шаблона ( сопоставление с образцом , таким образом решая проблему изоморфизма подграфа ) и путем замены найденного вхождения экземпляром графа замены. Правила перезаписи можно дополнительно регулировать в случае помеченных графов , например, в грамматиках графов, регулируемых строками.
Иногда грамматика графа используется как синоним системы переписывания графов , особенно в контексте формальных языков ; другая формулировка используется для подчеркивания цели конструкций, таких как перечисление всех графов из некоторого начального графа, т.е. генерация языка графов – вместо простого преобразования данного состояния (главного графа) в новое состояние.
Алгебраический подход к переписыванию графов основан на теории категорий . Алгебраический подход далее делится на подподходы, наиболее распространенными из которых являются подход двойного выталкивания (DPO) и подход одиночного выталкивания (SPO) . Другие подподходы включают подход полуторного выталкивания и подход отката .
С точки зрения подхода DPO правило переписывания графов представляет собой пару морфизмов в категории графов и гомоморфизмов графов между ними: , также пишется , где – инъективный . Граф K называется инвариантным или иногда графом склейки . Шаг переписывания или применение правила r к хост-графу G определяется двумя диаграммами выталкивания , обе происходящими из одного и того же морфизма , где D — контекстный граф (отсюда и название double -pushout). Другой морфизм графа моделирует появление L в G и называется совпадением . Практическое понимание этого заключается в том, что это подграф, который сопоставляется с (см. проблему изоморфизма подграфов ) и после того, как совпадение найдено, заменяется на главный граф , который служит интерфейсом, содержащим узлы и ребра, которые сохраняются при применении правило. Граф нужен для привязки сопоставляемого шаблона к его контексту: если он пуст, совпадение может обозначать только целый связный компонент графа .
Напротив, правило переписывания графа подхода SPO представляет собой единственный морфизм в категории помеченных мультиграфов и частичных отображений , которые сохраняют структуру мультиграфа: . Таким образом, шаг перезаписи определяется одной диаграммой выталкивания . Практическое понимание этого похоже на подход DPO. Разница в том, что между главным графом G и графом G', являющимся результатом этапа перезаписи, нет интерфейса.
С практической точки зрения ключевое различие между DPO и SPO заключается в том, как они справляются с удалением узлов со смежными ребрами, в частности, как они избегают того, чтобы такие удаления могли оставить после себя «висячие ребра». Подход DPO удаляет узел только тогда, когда правило определяет также удаление всех соседних ребер (это условие висячего узла можно проверить на предмет заданного совпадения), тогда как подход SPO просто удаляет соседние ребра, не требуя явного указания.
Существует также другой алгебраический подход к переписыванию графов, основанный главным образом на булевой алгебре и алгебре матриц, называемый грамматиками матричных графов . [1]
Еще один подход к переписыванию графов, известный как детерминированное переписывание графов, возник из логики и теории баз данных . [2] В этом подходе графы рассматриваются как экземпляры базы данных, а операции перезаписи — как механизм определения запросов и представлений; следовательно, любая перезапись необходима для получения уникальных результатов ( с точностью до изоморфизма ), и это достигается путем одновременного применения любого правила перезаписи по всему графу, где бы оно ни применялось, таким образом, чтобы результат действительно был определен однозначно.
Другой подход к переписыванию графов — это переписывание графов терминов , которое включает обработку или преобразование графов терминов (также известных как абстрактные семантические графы ) с помощью набора правил синтаксической перезаписи.
Графы термов — важная тема в исследованиях языков программирования, поскольку правила переписывания графов термов способны формально выражать операционную семантику компилятора . Графы термов также используются в качестве абстрактных машин, способных моделировать химические и биологические вычисления, а также графические вычисления, такие как модели параллелизма. Графы термов могут выполнять автоматическую проверку и логическое программирование, поскольку они хорошо подходят для представления количественных утверждений в логике первого порядка. Программное обеспечение для символьного программирования — это еще одно приложение для графов термов, которые способны представлять и выполнять вычисления с помощью абстрактных алгебраических структур, таких как группы, поля и кольца.
Конференция TERMGRAPH [3] полностью посвящена исследованиям в области переписывания графов термов и их приложений.
Системы перезаписи графов естественным образом группируются в классы в зависимости от типа используемого представления графов и способа выражения перезаписи. Термин «грамматика графа», иначе эквивалентный системе переписывания графов или системе замены графов, чаще всего используется в классификациях. Некоторые распространенные типы:
Графы — выразительный, наглядный и математически точный формализм моделирования объектов (сущностей), связанных отношениями; объекты представлены узлами, а отношения между ними — ребрами. Узлы и ребра обычно типизируются и атрибутируются. Вычисления в этой модели описываются изменениями отношений между сущностями или изменениями атрибутов элементов графа. Они закодированы в правилах перезаписи/преобразования графов и выполняются системами перезаписи/инструментами преобразования графов.
