fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <omp.h>
  4. #include <time.h>
  5.  
  6. #define MAX_VERTICES 100
  7.  
  8. struct Node {
  9.     int vertex;
  10.     struct Node* next;
  11. };
  12.  
  13. struct Graph {
  14.     int numVertices;
  15.     struct Node* adjLists[MAX_VERTICES];
  16.     int* visited;
  17. };
  18.  
  19. struct Node* createNode(int v) {
  20.     struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  21.     newNode->vertex = v;
  22.     newNode->next = NULL;
  23.     return newNode;
  24. }
  25.  
  26. struct Graph* createGraph(int n) {
  27.     struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
  28.     graph->numVertices = n;
  29.     graph->visited = (int*)malloc(n * sizeof(int));
  30.  
  31.     for (int i = 0; i < n; i++) {
  32.         graph->adjLists[i] = NULL;
  33.         graph->visited[i] = 0;
  34.     }
  35.     return graph;
  36. }
  37.  
  38. void addEdge(struct Graph* graph, int src, int dest) {
  39.     struct Node* newNode = createNode(dest);
  40.     newNode->next = graph->adjLists[src];
  41.     graph->adjLists[src] = newNode;
  42.  
  43.     newNode = createNode(src);
  44.     newNode->next = graph->adjLists[dest];
  45.     graph->adjLists[dest] = newNode;
  46. }
  47.  
  48. void parallelDFS(struct Graph* graph, int vertex) {
  49.     graph->visited[vertex] = 1;
  50.     printf("%d ", vertex);
  51.  
  52.     #pragma omp parallel
  53.     {
  54.         #pragma omp single nowait
  55.         {
  56.             #pragma omp taskloop grainsize(4) shared(graph)
  57.             for (int i = 0; i < graph->numVertices; ++i) {
  58.                 if (graph->visited[i] == 0) {
  59.                     parallelDFS(graph, i);
  60.                 }
  61.             }
  62.         }
  63.     }
  64. }
  65.  
  66. void DFS(struct Graph* graph, int vertex) {
  67.     graph->visited[vertex] = 1;
  68.     printf("%d ", vertex);
  69.  
  70.     for (int i = 0; i < graph->numVertices; ++i) {
  71. 	if (graph->visited[i] == 0) {
  72. 	   parallelDFS(graph, i);
  73. 	}
  74.     }
  75. }
  76.  
  77. int main() {
  78.     int numVertices, numEdges;
  79.     printf("Enter the number of vertices: ");
  80.     scanf("%d", &numVertices);
  81.  
  82.     struct Graph* graph_parallel = createGraph(numVertices);
  83.     struct Graph* graph = createGraph(numVertices);
  84.  
  85.     printf("Enter the number of edges: ");
  86.     scanf("%d", &numEdges);
  87.  
  88.     printf("Enter the edges (source destination):\n");
  89.     for (int i = 0; i < numEdges; i++) {
  90.         int src, dest;
  91.         scanf("%d %d", &src, &dest);
  92.         addEdge(graph, src, dest);
  93. 	addEdge(graph_parallel, src, dest);
  94.     }
  95.  
  96.     printf("Depth First Traversal (Sequential):\n");
  97.     clock_t start_time = clock();
  98.     DFS(graph, 0);
  99.     printf("\n");
  100.     clock_t end_time = clock();
  101.     double duration = ((double)(end_time - start_time)) / CLOCKS_PER_SEC;
  102.     printf("\nTime taken: %lf seconds\n\n", duration);
  103.  
  104.     printf("Depth First Traversal (Parallel):\n");
  105.     clock_t start_time_parallel = clock();
  106.     parallelDFS(graph_parallel	, 0);
  107.     printf("\n");
  108.     clock_t end_time_parallel = clock();
  109.     double duration_parallel = ((double)(end_time_parallel - start_time_parallel)) / CLOCKS_PER_SEC;
  110.     printf("\nTime taken: %lf seconds\n", duration_parallel);
  111.     return 0;
  112. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
45
stdout
copy 
Enter the number of vertices: Enter the number of edges: Enter the edges (source destination):
Depth First Traversal (Sequential):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 

Time taken: 0.000000 seconds

Depth First Traversal (Parallel):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 

Time taken: 0.000000 seconds
https://ideone.com/PPGV7X
language:
C++14 (gcc 8.3)
created:
9 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!