グラフ書き換え

コンピュータサイエンスにおいて、グラフ変換、あるいはグラフ書き換えとは、元のグラフからアルゴリズム的に新しいグラフを作成する手法を指します。ソフトウェア工学（ソフトウェア構築およびソフトウェア検証）から設計アルゴリズム、画像生成に至るまで、幅広い応用があります。

グラフ変換は計算の抽象化として利用できます。基本的な考え方は、計算の状態をグラフとして表現できる場合、その計算における以降のステップをそのグラフ上の変換規則として表現できるというものです。このような規則は、完全な状態におけるサブグラフと一致する元のグラフと、一致したサブグラフを置き換える置換グラフで構成されます。

正式には、グラフ書き換えシステムは通常、という形式のグラフ書き換え規則の集合から構成され、はパターングラフ（または規則の左側）と呼ばれ、は置換グラフ（または規則の右側）と呼ばれる。グラフ書き換え規則は、パターングラフの出現を検索し（パターンマッチング、つまり部分グラフ同型性問題の解決）、見つかった出現を置換グラフのインスタンスに置き換えることによって、ホストグラフに適用される。文字列調整グラフ文法など、ラベル付きグラフの場合、書き換え規則はさらに調整される。 $L\rightarrow R$ $L$ $R$

グラフ文法は、特に形式言語の文脈では、グラフ書き換えシステムの同義語として使用されることがあります。異なる言い回しは、特定の状態 (ホストグラフ) を単に新しい状態に変換するのではなく、ある開始グラフからすべてのグラフを列挙する、つまりグラフ言語を生成するなど、構築の目的を強調するために使用されます。

グラフ書き換えアプローチ

代数的アプローチ

グラフ書き換えに対する代数的アプローチは圏論に基づいています。代数的アプローチはさらにサブアプローチに分かれており、最も一般的なのはダブルプッシュアウト（DPO）アプローチとシングルプッシュアウト（SPO）アプローチです。その他のサブアプローチには、セスキプッシュアウトとプルバックアプローチがあります。

DPO アプローチの観点から見ると、グラフ書き換え規則はグラフのカテゴリにおける1 組の射とそれらの間のグラフ準同型であり、はとも表記され、は単射です。グラフ K は不変グラフまたは接着グラフと呼ばれることもあります。書き換えステップ、つまり規則 r のホストグラフG への適用は、同じ射に由来する 2 つのプッシュアウト図によって定義されます。ここで、 D はコンテキストグラフです (これが二重プッシュアウトという名前が由来する所以です)。別のグラフ射は G における L の発生をモデル化し、マッチと呼ばれます。これを実際に理解すると、はからマッチするサブグラフであり(サブグラフ同型性の問題を参照)、マッチが見つかった後、ホストグラフ内でに置き換えられます。ここではインターフェイスとして機能し、規則の適用時に保持されるノードとエッジが含まれます。グラフは、マッチするパターンをそのコンテキストに結び付けるために必要です。グラフが空の場合、マッチはグラフの連結されたコンポーネント全体しか指定できません。 $r=(L\leftarrow K\rightarrow R)$ $L\supseteq K\subseteq R$ $K\rightarrow L$ $k\colon K\rightarrow D$ $m\colon L\rightarrow G$ $L$ $G$ $L$ $R$ $G$ $K$ $K$ $G$

対照的に、SPOアプローチのグラフ書き換え規則は、ラベル付き多重グラフと多重グラフ構造を保持する部分写像の圏における単一の射である：。したがって、書き換えステップは単一のプッシュアウト図によって定義されます。これの実際的な理解はDPOアプローチと同様です。違いは、ホストグラフGと書き換えステップの結果であるグラフG'の間にインターフェースがないことです。 $r\colon L\rightarrow R$

実用的な観点から見ると、DPOとSPOの主な違いは、隣接するエッジを持つノードの削除をどのように処理するか、特に、そのような削除によって「ぶら下がりエッジ」が残るのをどのように回避するかです。DPOアプローチは、ルールですべての隣接エッジも削除するように指定されている場合にのみノードを削除します（このぶら下がりエッジの状態は、特定のマッチに対して確認できます）。一方、SPOアプローチは、明示的な指定を必要とせずに、隣接エッジを単純に破棄します。

グラフ書き換えには、ブール代数と行列代数に基づいた代数的なアプローチもあり、行列グラフ文法と呼ばれます。^[1]

決定的グラフ書き換え

決定的グラフ書き換えとして知られるグラフ書き換えへのさらに別のアプローチは、論理とデータベース理論から生まれました。^[2] このアプローチでは、グラフはデータベースインスタンスとして扱われ、書き換え操作はクエリとビューを定義するメカニズムとして扱われます。したがって、すべての書き換えは（同型性まで）一意の結果を生成する必要があり、これは、適用される場所に関係なく、結果が実際に一意に定義されるように、グラフ全体で任意の書き換えルールを同時に適用することによって実現されます。

項グラフ書き換え

グラフ書き換えのもう 1 つのアプローチは、用語グラフ書き換えです。これは、一連の構文書き換えルールによる用語グラフ (抽象意味グラフとも呼ばれます) の処理または変換を伴います。

項グラフは、項グラフの書き換え規則がコンパイラの操作的意味論を形式的に表現できるため、プログラミング言語研究における重要なトピックです。項グラフは、化学計算や生物学計算、並行性モデルなどのグラフィカル計算をモデル化できる抽象機械としても用いられています。項グラフは、一階述語論理における量化文の表現に適しているため、自動検証や論理プログラミングを実行できます。記号プログラミングソフトウェアは、項グラフのもう一つの応用分野であり、群、体、環といった抽象的な代数構造を用いた計算を表現および実行できます。

TERMGRAPHカンファレンス^[3]は、項グラフの書き換えとその応用に関する研究に特化しています。

グラフ文法とグラフ書き換えシステムのクラス

グラフ書き換えシステムは、使用されるグラフの表現の種類と書き換えの表現方法に応じて、自然にクラスに分類されます。グラフ文法という用語は、グラフ書き換えシステムまたはグラフ置換システムと同義であり、分類において最もよく使用されます。一般的なタイプには以下のものがあります。

属性付きグラフ文法は、通常、グラフ書き換えへの代数的アプローチに関する上記のセクションで言及されている、置換を特徴付けるためのシングルプッシュアウトアプローチまたはダブルプッシュアウトアプローチのいずれかを使用して形式化されます。
ハイパーグラフ文法には、より制限的なサブクラスとして、グラフ文法、線形グラフ文法、相互作用ネットが含まれます。

実装とアプリケーション

グラフは、関係によって結び付けられたオブジェクト（エンティティ）をモデル化するための、表現力豊かで視覚的、かつ数学的に正確な形式です。オブジェクトはノードで、それらの間の関係はエッジで表されます。ノードとエッジは一般的に型付けされ、属性が付与されます。このモデルにおける計算は、エンティティ間の関係の変化、またはグラフ要素の属性の変化によって記述されます。これらの計算はグラフ書き換え/グラフ変換規則に符号化され、グラフ書き換えシステム/グラフ変換ツールによって実行されます。

アプリケーションドメインに依存しないツール:
- AGG、属性付きグラフ文法システム ( Java )。
- GP 2 は、グラフプログラムでの形式的な推論を容易にするために設計された、視覚的なルールベースのグラフプログラミング言語です。
- GMTE（2018年3月13日、 Wayback Machineにアーカイブ）は、グラフマッチングと変換のためのグラフマッチング・変換エンジンです。メスマーアルゴリズムの拡張をC++で実装したものです。
- GrGen.NET はグラフ書き換えジェネレーターであり、C#コードまたは .NET アセンブリを生成するグラフ変換ツールです。
- GROOVE は、グラフとグラフ変換ルールの編集、グラフ文法の状態空間の探索、およびそれらの状態空間のモデルチェックを行う Java ベースのツールセットであり、グラフ変換エンジンとしても使用できます。
- Verigraph は、グラフ書き換え ( Haskell )に基づいたソフトウェア仕様および検証システムです。
グラフ書き換えによってソフトウェアエンジニアリングタスク (主にMDA )を解決するツール:
- eMoflon は、ストーリー駆動型モデリングとトリプルグラフグラマーをサポートする EMF 準拠のモデル変換ツールです。
- EMorF はEMFに基づくグラフ書き換えシステムであり、インプレースおよびモデル間変換をサポートします。
- Fujaba は、PROGRES に基づいたグラフ書き換え言語であるストーリー駆動型モデリングを使用します。
- グラフデータベースは、多くの場合、グラフの動的な書き換えをサポートします。
- 素晴らしい。
- Gremlin、グラフベースのプログラミング言語 (グラフ書き換えを参照)。
- Henshin は、 EMFに基づくグラフ書き換えシステムであり、インプレースおよびモデル間変換、クリティカルペア分析、モデルチェックをサポートします。
- PROGRES は、プログラムされたグラフ書き換えシステム用の統合環境および非常に高水準の言語です。
- ヴィアトラ。
機械工学ツール
- GraphSynthは、制約のないグラフ文法を作成し、生成された言語バリアントをテストおよび検索するためのインタープリタおよびUI環境です。グラフとグラフ文法規則をXMLファイルとして保存し、 C#で記述されています。
- Soley Studioは、グラフ変換システムのための統合開発環境です。主な用途は、エンジニアリング分野におけるデータ分析です。
生物学への応用
- グラフ文法ベースの言語による機能構造植物モデリング
- 文字列制御グラフ文法を用いた多細胞発生モデリング
- Kappa は、主に分子システム生物学に基づいて、相互作用するエージェントのシステムをモデル化するためのルールベースの言語です。
人工知能/自然言語処理
- OpenCog は、さまざまな AI アルゴリズムを実装するために使用される基本的なパターンマッチャー (ハイパーグラフ上) を提供します。
- RelEx は、グラフの書き換えを使用してリンク解析を依存関係解析に変換する英語のパーサーです。
コンピュータプログラミング言語
- Cleanプログラミング言語は、グラフ書き換えを使用して実装されています。

参照

グラフ理論
形状文法
正式な文法
抽象書き換え— グラフ書き換えの一般化

参考文献

引用

^ Perez 2009 ではこのアプローチについて詳しく説明しています。
^ 「データベースエンドユーザーインターフェースのためのグラフ指向オブジェクトモデル」(PDF)。
^ 「TERMGRAPH」.

出典

Rozenberg, Grzegorz (1997)、「グラフ文法とグラフ変換による計算ハンドブック」第 1～ 3巻、World Scientific Publishing、ISBN 9810228848、2013年10月4日にオリジナルからアーカイブされ、2012年7月11日に取得。
Perez, PP (2009)、「行列グラフ文法：グラフダイナミクスへの代数的アプローチ」、VDM Verlag、ISBN 978-3-639-21255-6。
Heckel, R. (2006).グラフ変換の要点. 電子計算機科学理論ノート 148 (1 SPEC. ISS.), pp. 187–198.
ケーニヒ、バーバラ (2004).動的に進化する構造を持つシステムの分析と検証. シュトゥットガルト大学資格取得論文, 2007年6月25日アーカイブ, pp. 65–180.
ロボ, ダニエル; ヴィコ, フランシスコ J.; ダッソウ, ユルゲン (2011年10月1日). 「文字列制御書き換えを用いたグラフ文法」.理論計算機科学. 412 (43): 6101– 6111. doi : 10.1016/j.tcs.2011.07.004 . hdl : 10630/6716 . ISSN 0304-3975.
Grzegorz Rozenberg編 (1997年2月). 基礎. グラフ文法とグラフ変換による計算ハンドブック. 第1巻. World Scientific. doi :10.1142/3303. ISBN 978-981-02-2884-2。
Hartmut Ehrig、Gregor Engels、Hans-Jörg Kreowski、Grzegorz Rozenberg編 (1999年10月). アプリケーション、言語、ツール. グラフ文法とグラフ変換による計算ハンドブック. 第2巻. World Scientific. doi :10.1142/4180. ISBN 978-981-02-4020-2。
Hartmut Ehrig、Hans-Jörg Kreowski、Ugo Montanari、Grzegorz Rozenberg編（1999年8月）。並行性、並列性、分散処理。グラフ文法とグラフ変換による計算ハンドブック。第3巻。World Scientific。doi : 10.1142 /4181。ISBN 978-981-02-4021-9。