I can only write through all bijections. I used VF2, but I could not understand it completely and I could not write it myself. What other algorithms are there for checking graphs for isomorphism? It is desirable that this algorithm could be easily modified to fit your needs.
- And what is the size of the graph about? - pavel
- @pavel, it doesn't matter. The main thing that the implementation of the algorithm was not very difficult. - pank
- busting for N! * N is the easiest. - pavel
- @pavel, can you write? and then my search is somehow crooked - pank
|
1 answer
The most naive solution that you can think of. The complexity is O(N!*N^2) .
const int N = 3; char A[N][N] = { {0,1,1},{1,0,0},{1,0,0} }; char B[N][N] = { {0,0,1},{0,0,1},{1,1,0} }; int P[N] = {0,1,2}; bool match(){ for (int i=0;i<N;i++) for (int j=0;j<N;j++) if (A[i][j] != B[ P[i] ][ P[j] ]) return false; return true; } int main() { do { if (match()){ for (int i=0;i<N;i++) cout << P[i] << " "; return 0; } } while (next_permutation(P, P+N)); } 
αλεχολυτ
21.1k 9 39 92
pavel pavel
8,454 3 22 39
- And if I know in advance that some vertices may coincide with isomorphism, and some not. This usually reduces brute force significantly. What to do in this case? - pank
- then it makes sense to fully articulate what is known about the graph. You can significantly speed up the match method and iterate (of course it won't be so beautiful) not through next_permutation but by your own method. - pavel
|