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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Атрибутивные графовые грамматики, как правило, формализованы с помощью подхода 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 - парсер английского языка, который использует переписывание графов для преобразования ссылочного разбора в зависимости разбора.

См. такжеПравить

ПримечанияПравить

↑ Perez, 2009 covers this approach in detail.
↑ This topic is expanded at mat2gra.info Архивная копия от 7 марта 2018 на Wayback Machine.
↑ TERMGRAPH (неопр.). Дата обращения: 20 февраля 2018. Архивировано 8 марта 2018 года.

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

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.

[1] Perez, 2009 covers this approach in detail.

[2] This topic is expanded at mat2gra.info Архивная копия от 7 марта 2018 на Wayback Machine.

[3] TERMGRAPH (неопр.). Дата обращения: 20 февраля 2018. Архивировано 8 марта 2018 года.

[1]

[2]

[3]