fork download
copy 
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <mpi.h>
  6. #define MAX_STRING 10000
  7. #define INFINITY 1000000
  8. int Read_n(int my_rank, MPI_Comm comm);
  9. MPI_Datatype Build_blk_col_type(int n, int loc_n);
  10. void Read_matrix(int loc_mat[], int n, int loc_n,
  11.  MPI_Datatype blk_col_mpi_t, int my_rank, MPI_Comm comm);
  12. void Print_local_matrix(int loc_mat[], int n, int loc_n, int my_rank);
  13. void Print_matrix(int loc_mat[], int n, int loc_n,
  14.  MPI_Datatype blk_col_mpi_t, int my_rank, MPI_Comm comm);
  15. void Dijkstra(int mat[], int dist[], int pred[], int n, int loc_n, int my_rank,
  16.  MPI_Comm comm);
  17. void Initialize_matrix(int mat[], int loc_dist[], int loc_pred[], int known[],
  18.  int loc_n, int my_rank);
  19. int Find_min_dist(int loc_dist[], int known[], int loc_n, int my_rank,
  20.  MPI_Comm comm);
  21. int Global_vertex(int loc_u, int loc_n, int my_rank);
  22. void Print_dists(int loc_dist[], int n, int loc_n, int my_rank, MPI_Comm comm);
  23. void Print_paths(int loc_pred[], int n, int loc_n, int my_rank, MPI_Comm comm);
  24. int main(int argc, char* argv[]) {
  25.  int *loc_mat, *loc_dist, *loc_pred;
  26.  int n, loc_n, p, my_rank;
  27.  MPI_Comm comm;
  28.  MPI_Datatype blk_col_mpi_t;
  29.  MPI_Init(&argc, &argv);
  30.  comm = MPI_COMM_WORLD;
  31.  MPI_Comm_size(comm, &p);
  32.  MPI_Comm_rank(comm, &my_rank);
  33.  n = Read_n(my_rank, comm);
  34.  loc_n = n/p;
  35.  loc_mat = malloc(n*loc_n*sizeof(int));
  36.  loc_dist = malloc(n*loc_n*sizeof(int));
  37.  loc_pred = malloc(n*loc_n*sizeof(int));
  38.  blk_col_mpi_t = Build_blk_col_type(n, loc_n);
  39.  Read_matrix(loc_mat, n, loc_n, blk_col_mpi_t, my_rank, comm);
  40.  Dijkstra(loc_mat, loc_dist, loc_pred, n, loc_n, my_rank, comm);
  41.  Print_dists(loc_dist, n, loc_n, my_rank, comm);
  42.  Print_paths(loc_pred, n, loc_n, my_rank, comm);
  43.  free(loc_mat);
  44.  free(loc_dist);
  45.  free(loc_pred);
  46.  MPI_Type_free(&blk_col_mpi_t);
  47.  MPI_Finalize();
  48.  return 0;
  49. }
  50. int Read_n(int my_rank, MPI_Comm comm) {
  51.  int n;
  52.  if (my_rank == 0)
  53.  printf("Enter number of vertices in the matrix: \n");
  54.  scanf("%d", &n);
  55.  MPI_Bcast(&n, 1, MPI_INT, 0, comm);
  56.  return n;
  57. }
  58. MPI_Datatype Build_blk_col_type(int n, int loc_n) {
  59.  MPI_Aint lb, extent;
  60.  MPI_Datatype block_mpi_t;
  61.  MPI_Datatype first_bc_mpi_t;
  62.  MPI_Datatype blk_col_mpi_t;
  63.  MPI_Type_contiguous(loc_n, MPI_INT, &block_mpi_t);
  64.  MPI_Type_get_extent(block_mpi_t, &lb, &extent);
  65.  MPI_Type_vector(n, loc_n, n, MPI_INT, &first_bc_mpi_t);
  66.  MPI_Type_create_resized(first_bc_mpi_t, lb, extent,
  67.  &blk_col_mpi_t);
  68.  MPI_Type_commit(&blk_col_mpi_t);
  69.  MPI_Type_free(&block_mpi_t);
  70.  MPI_Type_free(&first_bc_mpi_t);
  71.  return blk_col_mpi_t;
  72. }
  73. void Read_matrix(int loc_mat[], int n, int loc_n,
  74.  MPI_Datatype blk_col_mpi_t, int my_rank, MPI_Comm comm) {
  75.  int* mat = NULL, i, j;
  76.  if (my_rank == 0) {
  77.  mat = malloc(n*n*sizeof(int));
  78.  for (i = 0; i < n; i++)
  79.  for (j = 0; j < n; j++)
  80.  scanf("%d", &mat[i*n + j]);
  81.  }
  82.  MPI_Scatter(mat, 1, blk_col_mpi_t,
  83.  loc_mat, n*loc_n, MPI_INT, 0, comm);
  84.  
  85.  if (my_rank == 0) free(mat);
  86. }
  87. void Print_local_matrix(int loc_mat[], int n, int loc_n, int my_rank) {
  88.  char temp[MAX_STRING];
  89.  char *cp = temp;
  90.  int i, j;
  91.  sprintf(cp, "Proc %d >\n", my_rank);
  92.  cp = temp + strlen(temp);
  93.  for (i = 0; i < n; i++) {
  94.  for (j = 0; j < loc_n; j++) {
  95.  if (loc_mat[i*loc_n + j] == INFINITY)
  96.  sprintf(cp, " i ");
  97.  else
  98.  sprintf(cp, "%2d ", loc_mat[i*loc_n + j]);
  99.  cp = temp + strlen(temp);
  100.  }
  101.  sprintf(cp, "\n");
  102.  cp = temp + strlen(temp);
  103.  }
  104.  printf("%s\n", temp);
  105. }
  106. void Print_matrix(int loc_mat[], int n, int loc_n,
  107.  MPI_Datatype blk_col_mpi_t, int my_rank, MPI_Comm comm) {
  108.  int* mat = NULL, i, j;
  109.  
  110.  if (my_rank == 0) mat = malloc(n*n*sizeof(int));
  111.  MPI_Gather(loc_mat, n*loc_n, MPI_INT,
  112.  mat, 1, blk_col_mpi_t, 0, comm);
  113.  if (my_rank == 0) {
  114.  for (i = 0; i < n; i++) {
  115.  for (j = 0; j < n; j++)
  116.  if (mat[i*n + j] == INFINITY)
  117.  printf(" i ");
  118.  else
  119.  printf("%2d ", mat[i*n + j]);
  120.  printf("\n");
  121.  }
  122.  free(mat);
  123.  }
  124. }
  125. void Dijkstra(int mat[], int loc_dist[], int loc_pred[], int n, int loc_n,
  126.  int my_rank, MPI_Comm comm) {
  127.  int i, u, *known, new_dist;
  128.  int loc_u, loc_v;
  129.  known = malloc(loc_n*sizeof(int));
  130.  Initialize_matrix(mat, loc_dist, loc_pred, known, loc_n, my_rank);
  131.  for (i = 1; i < n; i++) {
  132.  loc_u = Find_min_dist(loc_dist, known, loc_n, my_rank, comm);
  133.  int my_min[2], glbl_min[2];
  134.  int g_min_dist;
  135.  if (loc_u < INFINITY) {
  136.  my_min[0] = loc_dist[loc_u];
  137.  my_min[1] = Global_vertex(loc_u, loc_n, my_rank);
  138.  } else {
  139.  my_min[0] = INFINITY;
  140.  my_min[1] = INFINITY;
  141.  } 
  142.  MPI_Allreduce(my_min, glbl_min, 1, MPI_2INT, MPI_MINLOC, comm);
  143.  u = glbl_min[1];
  144.  g_min_dist = glbl_min[0];
  145.  if (u/loc_n == my_rank) {
  146.  loc_u = u % loc_n;
  147.  known[loc_u] = 1;
  148.  }
  149.  for (loc_v = 0; loc_v < loc_n; loc_v++)
  150.  if (!known[loc_v]) {
  151.  new_dist = g_min_dist + mat[u*loc_n + loc_v];
  152.  if (new_dist < loc_dist[loc_v]) {
  153.  loc_dist[loc_v] = new_dist;
  154.  loc_pred[loc_v] = u;
  155.  }
  156.  }
  157.  }
  158.  free(known);
  159. }
  160. void Initialize_matrix(int mat[], int loc_dist[], int loc_pred[], int known[],
  161.  int loc_n, int my_rank) {
  162.  for (int v = 0; v < loc_n; v++) {
  163.  loc_dist[v] = mat[0*loc_n + v];
  164.  loc_pred[v] = 0;
  165.  known[v] = 0;
  166.  }
  167.  if (my_rank == 0) {
  168.  known[0] = 1;
  169.  }
  170. }
  171. int Find_min_dist(int loc_dist[], int loc_known[], int loc_n, int my_rank,
  172.  MPI_Comm comm) {
  173.  int loc_v, loc_u;
  174.  int loc_min_dist = INFINITY;
  175.  loc_u = INFINITY;
  176.  for (loc_v = 0; loc_v < loc_n; loc_v++)
  177.  if (!loc_known[loc_v])
  178.  if (loc_dist[loc_v] < loc_min_dist) {
  179.  loc_u = loc_v;
  180.  loc_min_dist = loc_dist[loc_v];
  181.  }
  182.  return loc_u;
  183. }
  184. int Global_vertex(int loc_u, int loc_n, int my_rank) {
  185.  int global_u = loc_u + my_rank*loc_n;
  186.  return global_u;
  187. }
  188. void Print_dists(int loc_dist[], int n, int loc_n, int my_rank, MPI_Comm comm) {
  189.  int v;
  190.  int* dist = NULL;
  191.  if (my_rank == 0) {
  192.  dist = malloc(n*sizeof(int));
  193.  }
  194.  MPI_Gather(loc_dist, loc_n, MPI_INT, dist, loc_n, MPI_INT, 0, comm);
  195.  if (my_rank == 0) {
  196.  printf("The distance from 0 to each vertex is:\n");
  197.  printf(" v dist 0->v\n");
  198.  printf("---- ---------\n");
  199.  for (v = 1; v < n; v++)
  200.  printf("%3d %4d\n", v, dist[v]);
  201.  printf("\n");
  202.  free(dist);
  203.  }
  204. }
  205. void Print_paths(int loc_pred[], int n, int loc_n, int my_rank, MPI_Comm comm) {
  206.  int v, w, *path, count, i;
  207.  int* pred = NULL;
  208.  if (my_rank == 0) {
  209.  pred = malloc(n*sizeof(int));
  210.  }
  211.  MPI_Gather(loc_pred, loc_n, MPI_INT, pred, loc_n, MPI_INT, 0, comm);
  212.  if (my_rank == 0) {
  213.  path = malloc(n*sizeof(int));
  214.  printf("The shortest path from 0 to each vertex is:\n");
  215.  printf(" v Path 0->v\n");
  216.  printf("---- ---------\n");
  217.  for (v = 1; v < n; v++) {
  218.  printf("%3d: ", v);
  219.  count = 0;
  220.  w = v;
  221.  while (w != 0) {
  222.  path[count] = w;
  223.  count++;
  224.  w = pred[w];
  225.  }
  226.  printf("0 ");
  227.  for (i = count-1; i >= 0; i--)
  228.  printf("%d ", path[i]);
  229.  printf("\n");
  230.  }
  231.  free(path);
  232.  free(pred);
  233.  }
  234. }
Success #stdin #stdout #stderr 0.21s 38900KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "int Read_n"
Execution halted
https://ideone.com/dUlc1z
language:
R (R 3.5.2)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!