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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

[править | править код]

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

[править | править код]

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

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

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

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

Примечания

[править | править код]
  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 года.

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

[править | править код]
  • Rozenberg, Grzegorz (1997), Handbook of Graph Grammars and Computing by Graph Transformations, 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, VDM Verlag, 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 (англ.) // Theoretical Computer Science[англ.]. — 2011. — 1 October (vol. 412, no. 43). — P. 6101—6111. — ISSN 0304-3975. — doi:10.1016/j.tcs.2011.07.004.