Лабораторные работы / Лабораторная работа 2 / Проверка изоморфности пары графов (Буренков).source / lab2 - копия

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ADDRESS_G "G.txt"
#define ADDRESS_H "H.txt"
#define ADDRESS_REPORT "report.txt"

// Число потоков
#define MAX_THREADS 2

int *P;
int counter = 0, n, myflag = 0;
int **tr;

int **g, **h;

//=======================================================================================
void Show(int str, int col, int **a)
{
	int i, j;
	printf("\n");
	for (i = 0; i < str; i++)
	{
		for (j = 0; j < col; j++)
			printf("%d ", a[i][j]);
		printf("\n");
	}
}

void Init(FILE *F, int N, int **G)
{
	int i, j;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
			fscanf(F, "%d", &G[i][j]);
		fscanf(F, "\n");
	}
	fclose(F);
}

unsigned long long int fact(int k)
{
	unsigned long long int res = 1;
	int i;
	for (i = 2; i <= k; i++)
		res *= i;
	return res;
}

void reverse(int m)
{
	int i = 1, j = m, buf;
	for (; i < j;)
	{
		buf = P[i];
		P[i] = P[j];
		P[j] = buf;
		i++; j--;
	}
}

void antylex(int m)
{
	int i, buf;
	if (m == 1)
	{
		// вывести перестановку
		if (counter % procNum == 0)
			for (i = 1; i <= n; i++)
				tr[counter / procNum][i - 1] = P[i];
		else
			MPI_Send(&P[1], n, MPI_INT, counter % procNum, 99, MPI_COMM_WORLD);
		counter++;
	}
	else
	{
		for (i = 1; i <= m; i++)
		{
			antylex(m - 1);
			if (i < m)
			{
				buf = P[i];
				P[i] = P[m];
				P[m] = buf;
				reverse(m - 1);
			}
		}
	}
}

void rearrange(int N, int **G, int k1, int k2)
{
	// Переставляем строки
	int i, buf;
	for (i = 0; i < N; i++)
	{
		buf = G[k1][i];
		G[k1][i] = G[k2][i];
		G[k2][i] = buf;
	}
	// Переставляем столбцы
	for (i = 0; i < N; i++)
	{
		buf = G[i][k1];
		G[i][k1] = G[i][k2];
		G[i][k2] = buf;
	}
	return;
}

void copy(int N, int **G, int **CLONE)
{
	int i, j;
	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			CLONE[i][j] = G[i][j];
	return;
}

int equal(int N, int **G, int **H)
{
	int i, j;
	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			if (G[i][j] != H[i][j])
				return 0;
	return 1;
}

//=======================================================================================
int main(int argc, char* argv[])
{
	FILE *FG, *FH, *FR;
	int i, j;
	double t1, t2, dt;

    int threads = MAX_THREADS;
    
    PTDATA pDataArray[threads];
    DWORD  dwThreadIdArray[threads];
    HANDLE hThreadArray[threads];
    
    t1 = (double) clock();
    FG = fopen(ADDRESS_G, "r");
    fscanf(FG, "%d\n", &i);
    FH = fopen(ADDRESS_H, "r");
    fscanf(FH, "%d\n", &j);

    if (i == j)
        n = i;
    else 
        n = 0;

	if (n == 0)
	{
        printf("Inputed graphes are NOT isomorphic\n");
        t2 = (double) clock();
        dt = (t2 - t1) / CLOCKS_PER_SEC;
        FR = fopen(ADDRESS_REPORT, "a");
        fprintf(FR, "\nSolving of problem isomorphic graphes takes %f sec.\n Number of threads = %d", dt, threads);
        fclose(FR);
		return 0;
	}

	g = (int**)malloc(n * sizeof(int*));
	h = (int**)malloc(n * sizeof(int*));
	P = (int*)malloc((n + 1) * sizeof(int));
	for (i = 0; i < n; i++)
	{
		g[i] = (int*)malloc(n * sizeof(int));
		h[i] = (int*)malloc(n * sizeof(int));
	}

	unsigned long long int N;

    Init(FG, n, g);
    Init(FH, n, h);
	
    N = fact(n);
    
    ////// ----
	unsigned int N1;
	for (N1 = 0; t + N1 * threads < N; N1++)	{}
	tr = (int**)malloc(N1 * sizeof(int*));
	for (i = 0; i < N1; i++)
		tr[i] = (int*)calloc(n, sizeof(int));
    ////// -----
	
	// Генерация перестановок
	if (procRank == 0)
	{
		for (i = 1; i <= n; i++)
			P[i] = i;
		antylex(n);
	}
	else
	{
		for (i = 0; i < N1; i++)
			MPI_Recv(&tr[i][0], n, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &Status);
	}

	int **clone;
	clone = (int**)malloc(n * sizeof(int*));
	for (i = 0; i < n; i++)
		clone[i] = (int*)malloc(n * sizeof(int));
	for (i = 0; i < N1; i++)
	{
		copy(n, g, clone);
		for (j = 0; j < n; j++)
			if (tr[i][j] != j + 1)
				rearrange(n, clone, j, tr[i][j] - 1);
		if (equal(n, h, clone) == 1)
			myflag += 1;
	}
	
    
    
    
    
    int sum = dwThreadIdArray[0];
    for(i = 1; i < threads; i++)
        sum += dwThreadIdArray[i];
    if (sum > 0)
        printf("Inputed graphes are isomorphic\n");
    else
        printf("Inputed graphes are NOT isomorphic\n");
	
	for (i = 0; i < N1; i++)
		free(tr[i]);
	free(tr);

	for (i = 0; i < n; i++)
	{
		free(g[i]);
		free(h[i]);
		free(clone[i]);
	}
	free(g);
	free(h);
	free(clone);
	free(P);

    t2 = (double) clock();
    dt = (t2 - t1) / CLOCKS_PER_SEC;
    FR = fopen(ADDRESS_REPORT, "a");
    fprintf(FR, "\nSolving of problem isomorphic graphes takes %f sec.\nNumber of threads = %d\nNumber of vertexes = %d\n", dt, threads, n);
    fclose(FR);
	return 0;
}