Добавил:
Tushkan
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:
#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"
#define ADDRESS_G "G.txt"
#define ADDRESS_H "H.txt"
#define ADDRESS_REPORT "report.txt"
int *P;
int counter = 0, n, procNum, myflag = 0;
int **tr;
//=======================================================================================
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, procRank;
int **g, **h;
double t1, t2, dt;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &procNum);
MPI_Comm_rank(MPI_COMM_WORLD, &procRank);
MPI_Status Status;
if (procRank == 0)
{
t1 = MPI_Wtime();
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;
}
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
if (n == 0)
{
if (procRank == 0)
{
printf("Inputed graphes are NOT isomorphic\n");
t2 = MPI_Wtime();
dt = t2 - t1;
FR = fopen(ADDRESS_REPORT, "a");
fprintf(FR, "\nSolving of problem isomorphic graphes takes %f sec.\n Number of processes = %d", dt, procNum);
fclose(FR);
}
MPI_Finalize();
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;
if (procRank == 0)
{
Init(FG, n, g);
Init(FH, n, h);
}
for (i = 0; i < n; i++)
{
MPI_Bcast(&g[i][0], n, MPI_INT, 0, MPI_COMM_WORLD);
MPI_Bcast(&h[i][0], n, MPI_INT, 0, MPI_COMM_WORLD);
}
N = fact(n);
unsigned int N1;
for (N1 = 0; procRank + N1 * procNum < 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;
}
if (procRank == 0)
{
int sum = myflag;
for (i = 1; i < procNum; i++)
{
MPI_Recv(&myflag, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &Status);
sum += myflag;
}
if (sum > 0)
printf("Inputed graphes are isomorphic\n");
else
printf("Inputed graphes are NOT isomorphic\n");
}
else
{
MPI_Send(&myflag, 1, MPI_INT, 0, procRank, MPI_COMM_WORLD);
}
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);
if (procRank == 0)
{
t2 = MPI_Wtime();
dt = t2 - t1;
FR = fopen(ADDRESS_REPORT, "a");
fprintf(FR, "\nSolving of problem isomorphic graphes takes %f sec.\nNumber of processes = %d\nNumber of vertexes = %d\n", dt, procNum, n);
fclose(FR);
}
MPI_Finalize();
return 0;
}
Соседние файлы в папке Проверка изоморфности пары графов (Буренков).source