THMMY.gr

/*
Produces a random graph with N nodes and M edges and an isomorphic graph
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <algorithm>

#define MAXN 500

using namespace std;

char e1[MAXN+1][MAXN+1], e2[MAXN+1][MAXN+1];
vector<int> perm;

int main() {
	int i, j, N, M, v1, v2;
	srand(time(NULL));
	
	printf("Give number of nodes and number of edges :\n");
	scanf( "%d %d", &N, &M);
	
	freopen("input.txt","w",stdout);
	printf("%d\n\n", N);
	
	//Building first graph
	for ( i=1; i<=M; ++i ) {
		do{
			v1 = (rand() % N) + 1;
			v2 = (rand() % N) + 1;
		} while ( v1 == v2 || e1[v1][v2]);
		e1[v1][v2] = e1[v2][v1] = 1;
	}
	
	//Produce a random permutation for the second, isomorphic, graph
	perm.push_back(-53); //just to make it start from 1
	for(i=1; i<=N; ++i) {
		perm.push_back(i);
	}
	random_shuffle ( perm.begin()+1, perm.end());
	
	for ( i=1; i<=N; ++i ) {
		for ( j=1; j<=N; ++j ) {
			e2[ perm[i] ][ perm[j] ] = e1[i][j];
		}
	}
	
	//Print graphs
	for ( i=1; i<=N; ++i ) {
		for ( j=1; j<=N; ++j ) {
			printf("%d%c", e1[i][j], j==N?'\n':' ');
		}
	}
	printf("\n");
	for ( i=1; i<=N; ++i ) {
		for ( j=1; j<=N; ++j ) {
			printf("%d%c", e2[i][j], j==N?'\n':' ');
		}
	}
	
	//Print the isomorphism
	printf("\nThe isomorphism used was the following :\n");
	for ( i=1; i<=N; ++i ) {
		printf ("Node %d in graph1 corresponds to node %d in graph2\n", i, perm[i]);
	}
}