グラフ同型性判定プログラム

グラフ同型性判定の本を読んで書いてみました。

その本自体にはプログラムは載っていなかったので、間違っているかも・・・。

ちなみにC++です。

入力はN頂点M辺のグラフG1、G2

出力は同型ならYes、そうではないならばNo

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;

int main(){
//G1,G2の作成
int N1 = 0, M1 = 0;
cin >> N1 >> M1;
vector< vector<int> > G1(N1);
for(int i = 0; i < M1; i++){
 int a = 0, b = 0;
 cin >> a >> b;
 G1[a].emplace_back(b);
 G1[b].emplace_back(a);
}
int N2 = 0, M2 = 0;
cin >> N2 >> M2;
vector< vector<int> > G2(N2);
for(int ii = 0; ii < M2; ii++){
 int a = 0, b = 0;
 cin >> a >> b;
 G2[a].emplace_back(b);
 G2[b].emplace_back(a);
}
for(int i = 0; i < G1.size(); i++){
sort(G1[i].begin(), G1[i].end());
}
for(int ii = 0; ii < G2.size(); ii++){
 sort(G2[ii].begin(), G2[ii].end());
}
/*
cout << "G1" <<endl;
for(int i = 0; i < G1.size(); i++){
 for(int j = 0; j < G1[i].size(); j++){
  cout << G1[i][j] << " ";
 }cout << endl;
}cout << endl;

cout << "G2" <<endl;
for(int ii = 0; ii < G2.size(); ii++){
 for(int jj = 0; jj < G2[ii].size(); jj++){
  cout << G2[ii][jj] << " ";
 }cout << endl;
}cout << endl;
*/
//全順列用の頂点集合の作成
vector<int> perm(N1, 0);
for(int i = 0; i < N1; i++){
 perm[i] = i;
}

//同型性チャック用
bool check = true;
map<int, int> mp;
do{
for(int i = 0; i < perm.size(); i++){
 mp[i] = perm[i];
}
//G2からG3を作成する
vector< vector<int> > G3(N2);
for(int ii = 0; ii < G2.size(); ii++){
 for(int jj = 0; jj < G2[ii].size(); jj++){
  int a = mp[ii];
  int b = mp[G2[ii][jj]];
  G3[a].emplace_back(b);
 }
}
for(int iii = 0; iii < G3.size(); iii++){
 sort(G3[iii].begin(), G3[iii].end());
}
/*
cout << "G3" <<endl;
for(int iii = 0; iii < G3.size(); iii++){
 for(int jjj = 0; jjj < G3[iii].size(); jjj++){
  cout << G3[iii][jjj] << " ";
 }cout << endl;
}cout << endl;
*/
//同型性チャック
//G1とG2が同型ならば
//G2から作ったG3のどれかはG1と同じ
check = true;
if(G1.size() == G3.size()){
 for(int i = 0; i < G1.size(); i++){
  if(check == false){
   break;
  }
  if(G1[i].size() == G3[i].size()){
  for(int j = 0; j < G1[i].size(); j++){
   if(check == false){
    break;
   }
  if(G1[i][j] == G3[i][j]){

  }else{
   check = false;
  }
 }
}else{
 check = false;
}
}
}else{
 check = false;
}
//全ての辺が同じならばcheckはtrueになっている。
if(check == true){
 break;
}
}while(next_permutation(perm.begin(), perm.end()));

if(check == true){
 cout << "Yes" << endl;
}else{
 cout << "No" << endl;
}

 return 0;
}