fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <mpi.h>
  4.  
  5. #define ROOT 0
  6.  
  7. void parallel_bfs(int **graph, int vertices, int root, int rank, int size) {
  8.     int *visited = (int *)calloc(vertices, sizeof(int));
  9.     int *local_queue = (int *)malloc(vertices * sizeof(int));
  10.     int local_frontier_size = 0;
  11.  
  12.     // Initialize local queue with root vertex
  13.     if (rank == ROOT) {
  14.         local_queue[local_frontier_size++] = root;
  15.         visited[root] = 1;
  16.     }
  17.  
  18.     MPI_Bcast(&local_frontier_size, 1, MPI_INT, ROOT, MPI_COMM_WORLD);
  19.     MPI_Bcast(visited, vertices, MPI_INT, ROOT, MPI_COMM_WORLD);
  20.  
  21.     // BFS loop
  22.     while (local_frontier_size > 0) {
  23.         int next_frontier_size = 0;
  24.         int *next_frontier = (int *)malloc(vertices * sizeof(int));
  25.  
  26.         // Explore local frontier
  27.         for (int i = 0; i < local_frontier_size; i++) {
  28.             int current_vertex = local_queue[i];
  29.             for (int j = 0; j < vertices; j++) {
  30.                 if (graph[current_vertex][j] && !visited[j]) {
  31.                     next_frontier[next_frontier_size++] = j;
  32.                     visited[j] = 1;
  33.                 }
  34.             }
  35.         }
  36.  
  37.         // Gather next frontier sizes from all processes
  38.         int *all_frontier_sizes = (int *)malloc(size * sizeof(int));
  39.         MPI_Allgather(&next_frontier_size, 1, MPI_INT, all_frontier_sizes, 1, MPI_INT, MPI_COMM_WORLD);
  40.  
  41.         // Calculate total size of next frontier
  42.         int total_next_frontier_size = 0;
  43.         for (int i = 0; i < size; i++) {
  44.             total_next_frontier_size += all_frontier_sizes[i];
  45.         }
  46.  
  47.         // Gather next frontier from all processes
  48.         int *all_next_frontiers = (int *)malloc(total_next_frontier_size * sizeof(int));
  49.         MPI_Allgather(next_frontier, next_frontier_size, MPI_INT, all_next_frontiers, next_frontier_size, MPI_INT, MPI_COMM_WORLD);
  50.  
  51.         // Update local frontier
  52.         local_frontier_size = all_frontier_sizes[rank];
  53.         for (int i = 0; i < local_frontier_size; i++) {
  54.             local_queue[i] = all_next_frontiers[i + rank * vertices];
  55.         }
  56.  
  57.         // Free dynamically allocated memory
  58.         free(next_frontier);
  59.         free(all_frontier_sizes);
  60.         free(all_next_frontiers);
  61.     }
  62.  
  63.     // Cleanup
  64.     free(visited);
  65.     free(local_queue);
  66. }
  67.  
  68. int main(int argc, char *argv[]) {
  69.     MPI_Init(&argc, &argv);
  70.     int rank, size;
  71.     MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  72.     MPI_Comm_size(MPI_COMM_WORLD, &size);
  73.  
  74.     // Define the graph (adjacency matrix)
  75.     int vertices = 6;
  76.     int **graph = (int **)malloc(vertices * sizeof(int *));
  77.     for (int i = 0; i < vertices; i++) {
  78.         graph[i] = (int *)malloc(vertices * sizeof(int));
  79.     }
  80.     // Initialize the graph (for simplicity, hardcoded here)
  81.     int adj_matrix[6][6] = {
  82.         {0, 1, 1, 0, 0, 0},
  83.         {1, 0, 0, 1, 1, 0},
  84.         {1, 0, 0, 0, 1, 0},
  85.         {0, 1, 0, 0, 0, 1},
  86.         {0, 1, 1, 0, 0, 1},
  87.         {0, 0, 0, 1, 1, 0}
  88.     };
  89.     // Copy adjacency matrix to the graph
  90.     for (int i = 0; i < vertices; i++) {
  91.         for (int j = 0; j < vertices; j++) {
  92.             graph[i][j] = adj_matrix[i][j];
  93.         }
  94.     }
  95.  
  96.     // Perform parallel BFS
  97.     parallel_bfs(graph, vertices, 0, rank, size);
  98.  
  99.     // Cleanup
  100.     for (int i = 0; i < vertices; i++) {
  101.         free(graph[i]);
  102.     }
  103.     free(graph);
  104.  
  105.     MPI_Finalize();
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout #stderr 0.3s 40536KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Error: unexpected symbol in "void parallel_bfs"
Execution halted
https://ideone.com/oKxo2L
language:
R (R 3.5.2)
created:
15 days 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!