Comments by sarge.r (Top 1 by date)

The C++ code of a test generator is given below. It generates 2 graphs which are guaranteed to be isomorphic.


//@Sarge Rogatch, September 7-8, 2011
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>

const int MAXN = 100;

//// Inputs
int N, chanceP, chanceQ;
//// Own reference
int perm[MAXN+2]; // the permutation of vertices
//// Outputs
char A1[MAXN+2][MAXN+2];
char A2[MAXN+2][MAXN+2];

int main(void) {
FILE *fptask = fopen("input.txt", "wt");
FILE *fpans = fopen("answer.txt", "wt");

//// hard-coded inputs for now
N = 100;
chanceP = 14;
chanceQ = 17;
srand( (unsigned)time(NULL) );
//// generate the permutation
for(int i=0; i<n; i++)="" {
="" perm[i]="i;
" }
="" for(int="" i="N-1;">=2; i--) {
int pos = rand()%i;
std::swap( perm[i], perm[pos] );
}
for(int i=0; i<n; i++)="" {
="" for(int="" j="0;" j<n;="" j++)="" if(="" i="=" )="" continue;
="" rand()%chanceq="">= chanceP ) continue;
A1[i][j] = 1;
A2[perm[i]][perm[j]] = 1;
}
}
//
fprintf(fptask, "%d\n", N);
for(int i=0; i<n; i++)="" {
="" for(int="" j="0;" j<n;="" j++)="" fprintf(="" fptask,="" "%s%d",="" (j="">0) ? " " : "", (int)A1[i][j] );
}
fprintf(fptask, "\n");
}
fprintf(fptask, "\n"); // separate the graphs
for(int i=0; i<n; i++)="" {
="" for(int="" j="0;" j<n;="" j++)="" fprintf(="" fptask,="" "%s%d",="" (j="">0) ? " " : "", (int)A2[i][j] );
}
fprintf(fptask, "\n");
}
fprintf(fpans, "%d\n", N);
for(int i=0; i<n; i++)="" {
="" fprintf(fpans,="" "%s%d",="" (i="">0) ? " " : "", (int)perm[i]+1); // 1-based indexing
}
fprintf(fpans, "\n");
return 0;
}