Полиномиальное решение задачи изоморфизма графов
В этом докладе я предлагаю алгоритм решения задачи изоморфизма графов, который имеет полиномиальную оценку вычислительной сложности для худшего случая. Из существования такого алгоритма следует что задача изоморфизма графов принадлежит к классу вычислительной сложности P.
Оригинальная публикация, детали и обсуждения здесь:
O(N^5) алгоритм определения одинаковости графов
Приведённый ниже код программы на языке С++ решает задачу изоморфизма графов, выполняя O(N^5) операций в худшем случае. Очевидно, что графы с разным количеством вершин неизоморфны. Поэтому мы рассматриваем только графы с одинаковым количеством вершин.
Для двух графов, G1 и G2, входной файл “input.txt” должен содержать число N - количество вершин в каждом из графов, и матрицы смежности обоих графов, сначала G1, потом G2. Генератор тестов из последующей секции создаёт входной файл в описанном формате.
Если графы изоморфны, выходной файл “output.txt” в первой строке будет содержать число N (количество вершин в каждом из графов), а во второй строке будет содержать перестановку вершин G2 достаточную для того, чтобы граф G2 совпал с G1, т.е. матрицы смежности стали идентичны при перестановке строк и столбцов матрицы смежности G2 указанным образом.
// @Sarge Rogatch, September 8, 2011 #define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <map>
#include <set>
#include <time.h>
using namespace std;
const int MAXN = 100;
typedef enum {
cpv_impossible = 0,
cpv_possible = 1,
cpv_constructed = 2
} corPosVals;
typedef long long cellVal;
typedef map<cellVal, set<int> > samePathLen;
FILE *fpin, *fpout;
int N;
int lastPow; // the last power of matrices (max. path len) taken into account char A[2][MAXN+2][MAXN+2]; // G1 and G2 adjacency matrices char B[MAXN+2][MAXN+2]; // correspondence possibilities implied from the built part char C[MAXN+2][MAXN+2]; // experimental correspondence possibilities (for finding contradictions) // I expect overflow in the cells of these matrices, and C#(decimal) or long-arithmetic would // alleviate or eliminate the overflow, however, I expect little adverse effects of overflow // on the efficiency of the search of contradictions cellVal S[2][MAXN+2][MAXN+2][MAXN+2];
// oriG2v[j] contains the original number of vertex from G2 which currently (due to row exchanges) // stands in j-th row int oriG2v[MAXN+2];
int builtF[MAXN+2]; // the result: builtF[i] is the vertex in G2 which corresponds to vertex [i] in G1 inline bool must(bool c) {
if( !c ) {
printf(" #invariant_failed ");
}
return c;
}
void pathNumOverflow(void) {
static int happened = 0;
if( !happened ) {
printf(" #overflow ");
happened = 1;
}
}
inline cellVal checkProduct(cellVal a, cellVal b) {
static const cellVal maxCV = (((cellVal)1)<<(sizeof(cellVal)*8-1)) - 1;
//TODO: look in Debug whether maxCV gets the proper value if( b != 0 ) {
if( maxCV / b < a ) {
pathNumOverflow();
}
}
return a*b;
}
template <class T> inline void xchg(T& a, T&b) {
T t = a;
a = b;
b = t;
}
int main(void) {
double tmPrev = clock() / (double)CLOCKS_PER_SEC;
fpin = fopen("input.txt", "rt");
fpout = fopen("output.txt", "wt");
///// Input // the number of vertices fscanf(fpin, "%d", &N);
// then two adjacency matrices follow for(int g=0; g<=1; g++) {
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
int t;
fscanf(fpin, "%d", &t);
must( t == 1 || t == 0 );
A[g][i][j] = t;
S[g][1][i][j] = t; // power 1 of the adjacency matrices }
}
}
//// Initialization lastPow = N; // regard powers 1...N of the adjacency matrices // Precompute the powers of the matrices for(int g=0; g<=1; g++) { // for both matrices for(int p=1; p<=lastPow-1; p++) { // in each step, compute (p+1)-th power from p-th // Use the simplest matrix multiplication algorithm O(N^3), which can be improved to // about O(N^2.5) as a matter of craft for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
S[g][p+1][i][j] = 0;
for(int k=0; k<N; k++) {
cellVal inc = checkProduct(S[g][p][i][k], S[g][p][k][j]);
S[g][p+1][i][j] += inc;
}
}
}
}
}
printf("Matrix multiplication done in %.3lf sec.\n", clock()/(double)CLOCKS_PER_SEC-tmPrev);
tmPrev = clock()/(double)CLOCKS_PER_SEC;
// Fill the 1's the whole correspondence possibility matrix, // because there are no restrictions untill anything is built for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
B[i][j] = cpv_possible;
}
}
// Initially, vertices in rows of G2 matrices stand "as is" for(int j=0; j<N; j++) {
oriG2v[j] = j;
}
//// Build the non-contradicting solution step by step for(int i=0; i<N; i++) {
// All the previous vertices 0...i-1 are fixed. Iterate [j] starting with [i] int j;
for(j=i; j<N; j++) {
// A case when the impossibility of f(i)=j mapping was proved during construction of the former pieces if( B[i][j] == cpv_impossible ) continue;
//// Copy the bottom-right square of the built-part matrix of correspondence possibilities //// into the experimental matrix of correspondence possibilities //NOTE: I'm not sure whether it's sufficient to start from k=i for(int k=i; k<N; k++) {
for(int m=i; m<N; m++) {
C[k][m] = B[k][m];
}
}
//// Search for contradictions to f(i) = j, i.e. the correspondence of v[i] from G1 to v[j] from G2 // First, search only in the rows&columns of the mapping upon test: f(i) = j // It may be sufficient to search just in them, but I don't know how to prove this yet. for(int k=0; k<N; k++) {
for(int m=0; m<N; m++) {
// No need to look again at a known to be impossible option if( C[k][m] == cpv_impossible ) continue;
for(int p=1; p<=lastPow; p++) {
if( (S[0][p][i][k] != S[1][p][j][m]) // mismatch on the number of outgoing paths, disproving f(k)=m || (S[0][p][k][i] != S[1][p][m][j]) // mismatch on the number of incoming paths, disproving f(k)=m ) {
// C[k][m] must become 0, but first test whether it's in the unconstructed range. // If it's in the constructed range, we've got a contradiction to the non-contradictory built solution, // thus there is no point in considering f(i)==j any more, we can discard any further testing of // f(i)==j and proceed with f(i) == (j+1) if( (k == m && k < i) // a contradiction to the formerly built non-contradicting part || (k == i && m == j) // f(i)==j proved itself impossible )
{
goto mapping_i_to_j_failed;
}
C[k][m] = cpv_impossible;
break; // for(p), as we've disproved mapping f(k)=m }
}
}
}
// check that for each [k] there is at least one [m], which is a mapping possibility, i.e. f(k) may be [m] for(int k=i; k<N; k++) {
int nOptions = 0;
for(int m=i; m<N; m++) {
if( C[k][m] != cpv_impossible ) {
nOptions++;
//TODO: later, we can exit the cycle here, or use in-line statistics for the number of options }
}
if( nOptions == 0 ) {
goto mapping_i_to_j_failed;
}
}
// check that there is a reverse mapping possibility, i.e. for each [m] there exist [k] so that f(k) may be m for(int m=i; m<N; m++) {
int nOptions = 0;
for(int k=i; k<N; k++) {
if( C[k][m] != cpv_impossible ) {
nOptions++;
}
}
if( nOptions == 0 ) {
goto mapping_i_to_j_failed;
}
}
// if we come to this point, it means that no contradiction was found for f(i)=j break;
mapping_i_to_j_failed:
// We've tried the possibility f(i)=j in the this iteration over [j], // and as we're here (still searching for a correspondence to [i], knowing that // f(i)=i, f(i)=i+1, ..., f(i)=j do not work), we must record this fact in B. // P.S. "we" - the program and I. B[i][j] = cpv_impossible;
}
if( j >= N ) {
//No possible [j] is found, thus halt with "not isomorphic" result goto not_isomorphic;
}
//// A non-contradicting [j] is found, so that f(i)=j . Record the constructed piece. builtF[i] = oriG2v[j];
// Copy from matrix C into B for(int k=i; k<N; k++) {
for(int m=i; m<N; m++) {
B[k][m] = C[k][m];
}
}
//// Exchange in all the matrices of G2 rows [i] and [j], and/or columns [i] and [j], // and exchange items [i] and [j] of oriG2v array if( i != j ) {
// oriG2v xchg(oriG2v[i], oriG2v[j]);
// B, and C (cause part of C is not going to be overwritten in the next iteration) // In B and C matrices, exchange only columns, because // columns stand for G2 vertices, while rows stand for G1 vertices) for(int k=0; k<N; k++) {
xchg(B[k][i], B[k][j]);
xchg(C[k][i], C[k][j]);
}
// S[1] for(int p=1; p<=lastPow; p++) {
for(int k=0; k<N; k++) {
xchg( S[1][p][i][k], S[1][p][j][k] );
}
for(int k=0; k<N; k++) {
xchg( S[1][p][k][i], S[1][p][k][j] );
}
}
}
}
printf("Solution found in %.3lf sec.\n", clock()/(double)CLOCKS_PER_SEC-tmPrev);
// Output the built mapping fprintf(fpout, "%d\n", N);
// i-th number is the vertex of G2 that corresponds to vertex [i] of G1 for(int i=0; i<N; i++) {
fprintf(fpout, "%s%d", (i>0) ? " " : "",
builtF[i]+1 // 1-based vertex numbering in the output (but internal 0-bazed numbering) );
}
fprintf(fpout, "\n");
return 0;
not_isomorphic:
fprintf(fpout, "0\n");
printf("Non-isomorphism identified in %.3lf sec.\n", clock()/(double)CLOCKS_PER_SEC-tmPrev);
return 0;
}
Генератор тестов
Приведённая ниже программа на языке C++ генерирует два графа, которые гарантированно изоморфны, и поэтому отличаются разве что нумерацией вершин. Граф G1 получается из G2 путём перенумерации вершин G2. Это значит что матрица смежности G1 получается соответствующей перестановкой строк и столбцов матрицы смежности G2. Эта случайная перестановка генерируется и записывается во второй строке файла “answer.txt”. В первой строке файла “answer.txt” записывается количество вершин в графах G1 и G2, каждое из которых равно N.
