私は、すべての可能な順列を生成し、一致するものがあるかどうかをチェックすることにより、「ブルート フォース」を使用する Java プログラムを作成しています。例: G1 = 「0-1 0-2 1-2 1-3 2-3」および G2 = 「1-3 2-0 0-3 1-2 1-0」の場合、順列 0123 → 2310 は一致しますが、0123 → 2013 は一致します。
グラフを 2 次元ブール配列として表すグラフ クラスを作成し、2 つの頂点がエッジであるかどうかを確認してグラフを出力するメンバー関数を持たせる必要があります。コンストラクターは、エッジのリストを表す上記の文字列を使用する必要があります。
その形式の文字列を取得して配列に入れる方法を知る必要があります。
全体として、2 つのグラフが同型かどうかを調べたいと思います。
以下のコードは順列ジェネレーターです。
// Generator of all permutations of: 0,1,2,...,n-1
public class PermutationGenerator
{
// private data
private int[] perm;
private boolean first;
// constructor
public PermutationGenerator (int n)
{
perm = new int [n];
first = true;
}
public int[] next ()
{
int n = perm.length;
// starting permutation: 0 1 2 3 ... n-1
if (first)
{
first = false;
for (int i = 0 ; i < n ; i++)
perm [i] = i;
return perm;
}
// construct the next permutation
// find largest k so that perm[k] < perm[k+1]; if none, finish
int i, j, k, l;
for (k = n - 2 ; k >= 0 && perm [k] >= perm [k + 1] ; k--)
;
if (k < 0)
return null; // no more
// find largest l so that perm[k] < perm[l]
for (l = n - 1 ; l >= 0 && perm [k] >= perm [l] ; l--)
;
// swap perm[k] and perm[l]
swap (perm, k, l);
// reverse perm[k+1]...perm[n-1]
for (i = k + 1, j = n - 1 ; i < j ; i++, j--)
swap (perm, i, j);
return perm;
}
// swap a[i] and a[j]
private static void swap (int a[], int i, int j)
{
int temp = a [i];
a [i] = a [j];
a [j] = temp;
}
}