問題タブ [isomorphism]

重複の可能性:
VF2 サブグラフ同型

Javaでグラフ同形アルゴリズムを実装したいのですが、プログラミング経験が少ないため（おそらくロジックも）、多くの問題に直面しています。調査の結果、Ullman、Nauty、および VF2 の 3 つのヒューリスティック アルゴリズムが利用可能であることがわかりました。VF2 は、博士課程の学生から言われたように、実装が最も高速で簡単であると考えられています。VF2 に専念する論文を読みましたが、残念ながらそれが (コードで) どのように機能するか、および実現可能性ルールをどうするかを理解していません。ここでは多くの人が C++ コードの実装について言及していますが、残念ながらリンクは開きません。さらに、1 人のユーザー (Rich Apodaca) は、化学者向けに VF2 の実装 (MX) を検討するよう提案しましたが、どのファイルかは指摘しませんでした。ただの大きなプロジェクトです... Javaで同形アルゴリズムを実装するのを手伝ってください（速度のためにVF2の方が優れています）、JavaまたはC ++（私にはわかりませんが、プロジェクト全体ではなく、構造を理解するのは難しいです）の作業コードを指摘してください少なくとも私は試すことができます）。ありがとうございました。

平面 3 連結グラフのグラフ同型のトピックについていくつかの調査を行いましたが、さまざまな制限、理論的複雑さ、および使用頻度のアルゴリズムが豊富にあり、次のように際立ったものを見つけるのに苦労しています。

• わかりやすい
• 最大限の明快さで実装可能
• 小さなグラフ (数十の頂点まで) での優れた実用的なパフォーマンス

さまざまなアルゴリズムを自分で理解しないと、この問題に特化した古いアルゴリズムの 1 つを使用する方がよいのか、より一般的な新しいアルゴリズムを使用する方がよいのかを知ることは困難です。考えられるすべての候補の中で、どれが最も適していますか?

サブグラフのセットがあり、それらが抽出されたグラフでそれらを一致させる必要があります。また、各サブグラフがそのようなグラフに表示される回数を数える必要があります（可能なすべての一致を保存する必要があります）。サブグラフとグラフの両方のエッジのラベルを考慮すると、完全に一致する必要がありますが、頂点のラベルは互いに一致する必要はありません。JUNG APIを使用してシステムを構築したので、JUNGが提供するグラフ構造を処理できるソリューション（API、アルゴリズムなど）が必要です。何かご意見は？

オートマトンとグラフ理論に関する科学プロジェクトを開始し、次のような機能をサポートするグラフライブラリを探しています。

• 有向/無向グラフ
• グラフ同型テスト（つまり、グラフg1はg2と同型ですか？）
• サブグラフ同型テスト（つまり、グラフg1はg2のサブグラフと同型ですか？）
• グラフ検索、訪問など
• おそらく、深刻な計算を行う必要があるため、非常に高速です

Boost Graph Libraryについては知っていますが、ドキュメントから理解できる限り、サブグラフのテストが不足しています。

だから、私の質問は：最高のc ++グラフライブラリはどれですか？彼らは私が必要とするすべての機能をサポートする必要はありません。既存のライブラリが私のニーズに完全に適合しない可能性は確かにあります。

Algorithm Design Manualでは、それは言う

2 つのツリーが同型かどうかをテストしていますか? – ツリーや平面グラフなど、特定のグラフ同形の特殊なケースでは、より高速なアルゴリズムが存在します。おそらく、最も重要なケースは、ツリー間の同型を検出することです。これは、言語パターン マッチングおよび解析アプリケーションで発生する問題です。構文木は、テキストの構造を記述するためによく使用されます。基礎となるテキストのペアが同じ構造を持つ場合、2 つの構文木は同形になります。

Tree Isomorphism を使用して言語パターン マッチングの問題を解決する方法の例を教えてください。つまり、言語パターン マッチングをツリー同型問題にどのようにマッピングできますか?

通常、文字列またはテキストをツリーとして構築し、それらの同一性を比較するにはどうすればよいでしょうか?

ありがとう

私は *.jar ファイルとグラフの同形を扱っています。2 つの *.jar ファイル間のグラフ同型性をチェックしたいと考えています。このためのpythonまたはrubyのライブラリはありますか。私はigraphまたは何でそれを行うことができますか?

ありがとう。

短い質問:プログラミング (つまり、関数型プログラミング) における同形関数の重要性は何ですか?

長い質問:関数型プログラミングと圏論の概念との間のいくつかの類推を、時々耳にする専門用語に基づいて描こうとしています。基本的に、私はその専門用語を具体的なものに「アンパッケージ」して、さらに拡張できるようにしようとしています。その後、私が話していることを理解して専門用語を使用できるようになります。これはいつもいいです。

私がよく耳にするこれらの用語の 1 つにIsomorphismがあります。これは、関数または関数合成間の同等性についての推論に関するものだと思います。同型のプロパティが (関数型プログラミングで) 役立ついくつかの一般的なパターンと、同型関数に関する推論からのコンパイラの最適化などの副産物について、誰かがいくつかの洞察を提供できるかどうか疑問に思っていました。

具体的には、J の共役演算子 (g&.f = (f inverse)(g)(f)) に触発されて、関数に追加情報を追加する方法が必要です。明白な方法は、ADT を使用することです。何かのようなもの：

しかし、ほとんどの場合 forward 関数だけが必要な場合、アプリケーション関数が必要になると、コードの可読性が大幅に低下します。非常に便利なのはクラスです：

( b は存在量指定子で暗黙的にできると思いますが、署名が間違っていないことを確認できるほど快適ではありません)

これで適用が暗黙的になるため、次のように書くことができます

他の機能と同じように。元：

次に、次のように記述できます。

理想的には、型シグネチャを推論できます

ただし、関数ではなく Applyable をサポートするには (.) も変更する必要があるため、これらのセマンティクスは複雑に見えます。型システムをだまして、適用可能なデータ型をすべての通常の目的で関数として扱うようにする方法はありますか? これが不可能/悪い考えである根本的な理由はありますか?

2 つのグラフ A と B があり、A が B のサブグラフかどうかを知りたいとします。ノードには、「サイズ」と「素材」などの属性が含まれています。

私が実行すると：

これは、エッジと属性ではなく、エッジのみによってグラフに一致します。

属性をチェックする方法の手がかりはありますか?

また、B に A の 2 つの連結グラフが含まれているとします。

私が実行すると：

これにより、A のサブグラフが 1 つだけ出力されます。すべてのサブグラフを出力する方法について何か考えはありますか?

たとえば、すべて青のノードと 1 つの赤のノードを持つグラフ G があるとします。また、すべて青で 1 つの赤のノードを持つグラフ F もありました。

これら 2 つのグラフが色付きのノードに関して同形であることを確認するために実行できるアルゴリズムは何ですか?