問題タブ [isomorphism]

VF2 アルゴリズムの実装に問題があります。多くの場合、すべてが完全に機能しているように見えますが、解決できない問題があります。

以下の例では、アルゴリズムは機能しません。この例では、2 つの同一のグラフを比較しています (下の画像を参照)。開始頂点は 0 です。s0 内で計算されるセット P は、頂点のすべてのペアのパワーセットを格納します。

以下は、実装のベースとなった VF2 に関する出版物に含まれている疑似コードです。

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B51AD0DAEDF60D6C8AB589A39A570257?doi=10.1.1.101.5342&rep=rep1&type=pdf

http://www.icst.pku.edu.cn/intro/leizou/teaching/2012-autumn/papers/part2/VF2%20A%20%28sub%29Graph%20Isomorphism%20Algorithm%20For%20Matching%20Large%20Graphs. pdf

/* の右側のコメントは、コードの理解方法を説明しています。

以下で説明するように、 P() セットの作成が有効かどうかはわかりません。ペアのべき集合は、ペアの最初の値、次に 2 番目の値によって、辞書式順序で反復されます。

アルゴリズムが s4 に進むと、関数から戻るときに、適切な頂点の一致に関する情報が失われます。グラフが同型であっても、サブグラフ同型 ({(0,0),(1,1),(2,2),(5,3),(6,4)}) を検索することになります。

ここで何が間違っていますか？

私はこれをインターネット上で2、3日連続で検索してきましたが、今のところうまくいきません.

サブグラフ同型のライブラリと実装が世の中にたくさんあることは知っていますが、それらはすべて重み付けされていないグラフで機能します。たとえば、最も普及している 2 つのアルゴリズムは、VF2 と Uleman のアルゴリズムです。ここで、私の質問は次のとおりです。グラフ (G) とクエリ グラフ (g) が与えられた場合、g が G のサブグラフ (および同形) であるかどうかを確認できるメソッドはありますか? (以下はグラフのエッジ リスト表現であることに注意してください。)

この場合、g は部分グラフであり、G と同型ですが、次のようなものがあるとします。

g はもはや G のサブグラフではなく、同型ではありません。

UPDATE : どちらのグラフも無向です。

私は、文字列の配列で同形のペアの数を返すことを含む、この Java の問題に固執しています。私が書いたコードは、間違った数の同型語ペアを返し続けます。

同形語の定義は次のとおりです。1 つの単語の文字を再マッピングして 2 番目の単語を取得できる場合、2 つの単語は同形語と呼ばれます。文字の再マッピングとは、出現するすべての文字を別の文字に置き換えることを意味します。文字の順序は変更されません。2 つの文字が同じ文字にマップされることはありませんが、文字がそれ自体にマップされる場合があります。たとえば、「abca」と「zbxz」という単語は、「a」を「z」に、「b」を「b」に、「c」を「x」にマッピングできるため、同形です。関数で呼び出す getMap メソッドは含まれていません。getMap メソッドは任意の文字列を入力として受け取り、キーが文字列内の文字であり、対応する値が文字列内の文字の出現回数であるマップを返します。

このコードについてフィードバックをいただければ幸いです。

ありがとう、ジュナイド

Chuusai のこのブログ投稿を読むと、次のように書かれています。

2 つの型とそれらの値の間に同型性があるため、[Int, String] はユニオン型 Int ∨ String をモデル化できます。

「2 つの型とその値の間に同形性がある」とはどういう意味ですか?

Subgraph Isomorphism (SI) 問題は、2 つのグラフ G と H が入力として与えられる計算タスクであり、G に H と同型のサブグラフが含まれているかどうかを判断する必要があります。

これはNP 完全問題です。

SAT問題との関係を知りたいです。特に、この問題のインスタンスを SAT ソルバー ( miniSAT
など) 全体で解決できるようにしたいと考えています。SI から SAT 問題へのマッピングを多項式時間で実行できるアルゴリズムが必要であり、SAT 割り当てを使用してノードからマッピングを見つけることができます。 G から H のノードへ。

何か案が ？？？

これはよく研究された問題でなければなりませんが、私はそれを研究するのに苦労しています。

ここから始めましたが、研究して実装するアルゴリズムを探しています。 http://en.wikipedia.org/wiki/Graph_isomorphism_problem

たとえば、これらの DAG (Directe Acyclic Graphs) が 2 つある場合、そのうちの 1 つをマークまたは削除する必要があります。これは、最初の DAG の回転/反射にすぎないためです。同じ自己同形グループに属しているということは、それらを回転/反射して、まったく同じ隣接行列を持つことができるということですか?

という名前の 2 つの関数がf :: a -> bあり、それが逆g :: b -> aであるとしf . g ≡ idます。

今じゃないg . f ≡ id？(したがって、同形性を意味します)

同様の例を書き込もうとしたところ、次のようになりました。

ghci で:

しかし、逆関数は同型を意味していないようです。だから、私がここで間違っていることを誰かに教えてもらえますか?

この質問は Hogan を例として使用していますが、どのテンプレートにも当てはまります。

私は同形のものを作ろうとしています(クライアントとサーバーの両方で動作します)。クライアントで口ひげファイルが必要な場合:

次に、 browserify + a transform は、これが拡張子によって口ひげファイルでtplあり、オブジェクトであり、関数の1つが.render.

上記の行を NodeJS で実行すると、まったく同じ結果が得られます。

デフォルトでは、Node はこのファイルが JavaScript ファイルであることを想定しているため、結果は次のようになり、エラーが発生します。

ノード/頂点をコンパクトで明確な方法で配置するためのライセンスのないアルゴリズムはありますか?ダイアグラム?

言い換えれば、最も明確に配置された位置でグラフを同形化するにはどうすればよいでしょうか?

ああ、ノードは長方形です (先ほど言ったように、これは図用です) 内容によってサイズが異なる場合があります

同型を削除したい 15M (Million) DAG (有向非巡回グラフ - 実際には有向ハイパーキューブ) のコレクションがあります。これの一般的なアルゴリズムは何ですか? 各グラフはかなり小さく、N が 3 から 6 (今のところ) である次元 N のハイバーキューブであり、N=6 の場合にそれぞれ 64 ノードのグラフになります。

networkx と python を使用して、このように実装しました。これは、300k (千) のような小さなセットで問題なく機能します (数日で実行されます)。

それを行うより良い方法の 1 つは、各グラフを正規の順序に変換し、コレクションを並べ替えてから、重複を削除することです。これは、バイナリ is_isomophic() テストで 15M グラフのそれぞれをチェックすることをバイパスします。上記の実装は O(N!N) (同形時間を考慮していない) のようなものであると思いますが、すべてを標準的な順序に変換してソートする必要があります。変換のための O(N) + 検索のための O(log(N)N) + 重複の除去のための O(N)。O(N!N) >> O(log(N)N)

Canonical グラフのラベル付けに関するこの論文を見つけましたが、疑似コードではなく数式で非常に簡潔に説明されています。

tldr:バイナリ同形チェックでチェックするグラフがありえないほど大量にあります。これが行われる一般的な方法は、正規の順序付けによるものだと思います。パッケージ化されたアルゴリズム、または公開されている簡単に実装できるアルゴリズム (つまり、疑似コードを含む) はありますか?