source: proiecte/pgraph/Code/Dijkstra/pdikstra.c @ 129

//Author Antonio-Gabriel Sturzu

#include<stdio.h>
#include<mpi.h>
#include<string.h>
#include<stdlib.h>
#define inf 50000001

int main(int argc,char *argv[])
{
        int rc,numtasks,rank,**m,n,*line,dim,next=0,strip,*d,minl,ming,iminl,iming,prod;
        int i,j,temp;
        char *viz;
        double time1,time2;
        FILE *f;
        MPI_Status status;

        //MPI Initialization
        rc = MPI_Init(&argc,&argv);
        if (rc != MPI_SUCCESS) 
        {
                printf ("Error starting MPI program. Terminating.\n");
                MPI_Abort(MPI_COMM_WORLD, rc);
        }
        MPI_Comm_size(MPI_COMM_WORLD,&numtasks);
        MPI_Comm_rank(MPI_COMM_WORLD,&rank);

        //Reading from file is done by process 0
        if(rank==0)
        {       
                f=fopen("dijkstra.in","r");
                fscanf(f,"%i",&n);
        }
        //Broadcast n's value to all processes
        MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);
        dim=n/numtasks;
        strip=dim;
        if(rank==numtasks-1 && n%numtasks!=0)
                dim=n-dim*(numtasks-1);
        
        //Partition the data

        m=(int **) calloc(n*dim,sizeof(int *));
        for(i=0;i<n;i++)
                        m[i]=(int *) calloc(dim,sizeof(int));
        if(rank==0)
        {
                line=(int *) calloc(n,sizeof(int));
                for(i=0;i<n;i++)
                {
                        next=dim;
                        for(j=0;j<n;j++)
                                fscanf(f,"%i",line+j);
                        memmove(m[i],line,dim*sizeof(int));
                        for(j=1;j<numtasks-1;j++)
                        {
                                MPI_Send(&line[next],dim,MPI_INT,j,1,MPI_COMM_WORLD);
                                next+=dim;
                        }
                        if(numtasks>1)
                                MPI_Send(&line[next],n-next,MPI_INT,numtasks-1,1,MPI_COMM_WORLD);
                }
        }               
        else
                for(i=0;i<n;i++)
                        MPI_Recv(m[i],dim,MPI_INT,0,1,MPI_COMM_WORLD,&status);

        d=(int *) calloc(dim,sizeof(int));
        viz=(char *) calloc(dim,sizeof(char));

        MPI_Barrier(MPI_COMM_WORLD);
        time1 = MPI_Wtime();

        //Initialize local distance vectors

        if(rank!=0)
        {
                for(i=0;i<dim;i++)
                        d[i]=inf;
        }
        else
        {
                for(i=1;i<dim;i++)
                        d[i]=inf;
                d[0]=0;
        }
        MPI_Barrier(MPI_COMM_WORLD);

        //Distributed Dijkstra's algorithm
        for(;;)
        {
                minl=inf;
                for(i=0;i<dim;i++)
                        if(viz[i]==0 && d[i]<minl)
                        {
                                minl=d[i];
                                iminl=i;
                        }
                //Determine the global minimum distance from a node to the source
                MPI_Allreduce(&minl,&ming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
                if(ming==inf)
                        break;
        
                if(minl==ming)
                {
                        if(rank!=numtasks-1)
                                temp=iminl+rank*dim;
                        else
                                temp=iminl+rank*strip;
                        MPI_Allreduce(&temp,&iming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
                }
                else
                        MPI_Allreduce(&n,&iming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
        
                //If the node with the minimum distance is owned by this process
                //mark it as visited
                
                if(rank!=numtasks-1)
                {
                        if(iming>=rank*dim && iming<(rank+1)*dim)
                                viz[iming-rank*dim]=1;
                }
                else
                {
                        if(iming>=rank*strip && iming<n)
                                viz[iming-rank*strip]=1;
                }
                for(i=0;i<dim;i++)
                {
                        if(m[iming][i]+ming<d[i] && m[iming][i]!=-1)
                                d[i]=m[iming][i]+ming;
                }
                MPI_Barrier(MPI_COMM_WORLD);
        }
        MPI_Barrier(MPI_COMM_WORLD);
        time2 = MPI_Wtime();
        if(rank==0)
                printf("Au trecut %f secunde\n",time2-time1);

        if(rank==0)
                printf("The minimum distances are :\n");
        MPI_Barrier(MPI_COMM_WORLD);
        if(rank!=numtasks-1)
                prod=rank*dim;
        else
                prod=rank*strip;

        for(i=0;i<dim;i++)
        {
                if(d[i]==inf)
                        d[i]=0;
                printf("%i %i\n",i+prod+1,d[i]);
        }
        for(i=0;i<n;i++)
                free(m[i]);
        free(m);
        free(d);
        free(viz);
        if(rank==0)
                free(line);
        MPI_Finalize(); 
        return 0;
}