/* perm.c: answers the question given a graph, * are there hamiltonian paths? * if so, how many distinct paths * are there? * */
#include <stdio.h> #include "mpi.h"
#define DEBUG 0
int NN; int num_procs; int my_rank;
/* * btoi - takes an exponent of a binary number to set to 1 * and returns the corresponding integer. */ int btoi(int exp) int i,retInt=1;
if(exp == 0) return 1; else for(i=1;i<exp;i++) retInt *= 2;
return retInt;
void exch(int p[], int i,int j) int temp=p[i]; // printf("exch(p[i]=p[j]; p[j]=temp;
void doItR(int adj[], int p[],int ind,int j) int k; int isHamP=0; // array to temporalily store the whole // permutation. int perm[NN+3];
// fill up perm perm[1] = ind; for(k=2;k<=NN+1;k++) // index ind is the first numer, yet // the node in middle has it, so swap if(ind == p[k-1]) perm[k] = 1; // same for index j as ind else if(j == p[k-1]) perm[k] = NN+2; // no change else perm[k] = p[k-1]; perm[NN+2] = j;
// now check if the edges exist. // // checking the first two nodes if((adj[perm[1]] & btoi(perm[2])) > 0) isHamP = 1; else isHamP = 0;
//checking the rest of the nodes for(k=2;k<=NN+1;k++) if((adj[perm[k]] & btoi(perm[k+1])) > 0 && isHamP == 1) isHamP = 1; else isHamP = 0;
if(isHamP == 1) for(k=1; k<=NN+2; k++) printf(" printf(" ham path");
void generateR(int adj[], int p[], int N,int i, int j) int c; if(N<=1) return; for(c=1; c<=N; c++) generateR(adj,p, N-1,i,j); if(c!=N) doItR(adj,p,i,j); exch(p, N
/* findi: here, we exploit the relationship between i and k * (notion of i and k is described in generateRStart * comment) * k = 1+(i-1)*(i-2)/2 * because the sequencing of a_n = a_n-1 + i-1; * or an = a0 + Sum of i from 1 to n i-1 * or an = 1 + (i-1)*(i-2)/2 */ int findi(int count) int i;
for(i=2;i<=NN+2;i++) if((i-1)*(i-2)/2+1 <= count && i*(i-1)/2+1 > count) return i;
return i-1;
/* * mpi_strategy: break the jobs that are based on i,j index * i: the starting node * j: the ending node * however, the code would not know which i and j to * start and to stop. so we introduce the notion of * k-indexing where k is the kth combination using * i and j to express k in terms of i and j: * k = (i-1)*(i-2)/2 + j; * also, just ith index can be traced using the findi * function. the jth index we'll just subtract the * k value at the desired index with the * (i-1)*(i-2)/2+1 which i is the ith row in question * * first, each processors are subject to completing * the same number of jobs for simplicity, but the * processors which satisfys * if(totalComb* on an extra i,j namely, kth index of * totalComb-my_rank or corresponding i,jth index */ void generateRStart(int N,int *adj) int p[N-1]; int i_min,i_max,i; int j_min,j_max,j; int totalComb=0,my_count; int jtmp_min,jtmp_max;
// initialize the vertices for(i=1; i<= N-1; i++) p[i-1]=i;
// how much is my share? totalComb = (N * (N-1)) / 2;
// evenly distribute the jobs my_count = totalComb/num_procs;
// find the index where to start and stop i_min=findi(my_rank*my_count+1); i_max=findi((my_rank+1)*my_count); // in order to find index j, we use the relationship // between i, j and k j_min=my_rank*my_count+1 - (i_min-1)*(i_min-2)/2; j_max=(my_rank+1)*my_count - (i_max-1)*(i_max-2)/2;;
for(i=i_min; i<=i_max; i++) if(i==i_min) jtmp_min = j_min; else jtmp_min = 1;
if(i==i_max) jtmp_max = j_max+1; else jtmp_max = i;
for(j=jtmp_min; j<jtmp_max; j++) generateR(adj,p,N-2,j,i); doItR(adj,p,j,i); // printf("
// any more jobs for me? if(totalCombi=findi(totalComb-my_rank); j=totalComb-my_rank - (i-1)*(i-2)/2; //printf("proc#:generateR(adj,p,N-2,j,i); doItR(adj,p,j,i);
int main(int argc, char *argv[]) int N,i; char *NStr; double wall_time; FILE *fp; int *adj;
MPI_Init(&argc,&argv); wall_time = MPI_Wtime(); MPI_Comm_size(MPI_COMM_WORLD, &num_procs); MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
if(argc != 2) fprintf(stderr,"usage: hamP <graph file name>"); return -1;
if((fp = fopen(argv[1],"r")) == NULL) fprintf(stdout,"file open failed"); return -1;
fscanf(fp,"
adj = (int *)calloc(N+1,sizeof(int)); NN=N-2;
for(i=0;i<N;i++) fscanf(fp,"
if(my_rank == 0) printf("Computing possible ham.paths..."); printf("number of nodes in the graph = printf("number of procs = // for(i=0;i<N+1;i++) // printf("adj[
generateRStart(N,adj);
wall_time = MPI_Wtime() - wall_time; if(my_rank == 0) printf("running time - MPI_Finalize();
free(adj); return 0;