グラフの書き換え

コンピュータサイエンスにおいて、グラフ変換またはグラフ書き換えは、アルゴリズムによって元のグラフから新しいグラフを作成する手法を指します。ソフトウェアエンジニアリング(ソフトウェア構築およびソフトウェア検証)からレイアウトアルゴリズムや画像生成まで、さまざまな用途があります。

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

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

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

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

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

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

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

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

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

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

項グラフはプログラミング言語研究の重要なトピックです。項グラフの書き換え規則はコンパイラの操作的意味を形式的に表現できるためです。項グラフは、化学計算や生物学計算、並行モデルなどのグラフィカル計算をモデル化できる抽象マシンとしても使用されます。項グラフは、一階述語論理で量化されたステートメントを表現するのに適しているため、自動検証や論理プログラミングを実行できます。記号プログラミング ソフトウェアは、項グラフのもう 1 つのアプリケーションであり、グループ、体、環などの抽象的な代数構造を表現して計算を実行できます。

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

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

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

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

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

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