fork download
copy 
  1. #include <iostream>
  2. #include <omp.h>
  3. #include <vector>
  4. #include <queue>
  5. #include <chrono>
  6. using namespace std;
  7.  
  8. class Graph {
  9.     vector<vector<int>> adjMatrix;
  10.     vector<int> visited;
  11.     int n;
  12.  
  13. public:
  14.     void accept();
  15.     void display();
  16.     void reset();
  17.     void parallelDFS(int v);
  18.     void parallelBFS(int v);
  19.     void normalDFS(int v);
  20.     void normalBFS(int v);
  21. };
  22.  
  23. void Graph::accept() {
  24.     cout << "\nEnter the number of vertices: ";
  25.     cin >> n;
  26.     adjMatrix.resize(n, vector<int>(n, 0));
  27.     visited.resize(n, 0);
  28.     cout << "\nEnter the adjacency matrix:\n";
  29.     for (int i = 0; i < n; i++) {
  30.         for (int j = 0; j < n; j++) {
  31.             cin >> adjMatrix[i][j];
  32.         }
  33.     }
  34. }
  35.  
  36. void Graph::display() {
  37.     cout << "\nThe Adjacency Matrix is:\n";
  38.     for (int i = 0; i < n; i++) {
  39.         for (int j = 0; j < n; j++) {
  40.             cout << adjMatrix[i][j] << " ";
  41.         }
  42.         cout << endl;
  43.     }
  44. }
  45.  
  46. void Graph::reset() {
  47.     fill(visited.begin(), visited.end(), 0);
  48. }
  49.  
  50. void Graph::normalDFS(int v) {
  51.     cout << v << " ";
  52.     visited[v] = 1;
  53.  
  54.     for (int i = 0; i < n; i++) {
  55.         if (adjMatrix[v][i] == 1 && visited[i] == 0) {
  56.             normalDFS(i);
  57.         }
  58.     }
  59. }
  60.  
  61. void Graph::parallelDFS(int v) {
  62.     cout << v << " ";
  63.     visited[v] = 1;
  64.  
  65.     #pragma omp parallel for
  66.     for (int i = 0; i < n; i++) {
  67.         if (adjMatrix[v][i] == 1 && visited[i] == 0) {
  68.             #pragma omp critical
  69.             {
  70.                 if (visited[i] == 0) {
  71.                     parallelDFS(i);
  72.                 }
  73.             }
  74.         }
  75.     }
  76. }
  77.  
  78. void Graph::normalBFS(int v) {
  79.     queue<int> q;
  80.     visited[v] = 1;
  81.     q.push(v);
  82.  
  83.     while (!q.empty()) {
  84.         int curr = q.front();
  85.         q.pop();
  86.         cout << curr << " ";
  87.  
  88.         for (int i = 0; i < n; i++) {
  89.             if (adjMatrix[curr][i] == 1 && visited[i] == 0) {
  90.                 visited[i] = 1;
  91.                 q.push(i);
  92.             }
  93.         }
  94.     }
  95. }
  96.  
  97. void Graph::parallelBFS(int v) {
  98.     queue<int> q;
  99.     visited[v] = 1;
  100.     q.push(v);
  101.  
  102.     while (!q.empty()) {
  103.         int curr = q.front();
  104.         q.pop();
  105.         cout << curr << " ";
  106.  
  107.         #pragma omp parallel for
  108.         for (int i = 0; i < n; i++) {
  109.             if (adjMatrix[curr][i] == 1 && visited[i] == 0) {
  110.                 #pragma omp critical
  111.                 {
  112.                     if (visited[i] == 0) {
  113.                         visited[i] = 1;
  114.                         q.push(i);
  115.                     }
  116.                 }
  117.             }
  118.         }
  119.     }
  120. }
  121.  
  122. int main() {
  123.     Graph g;
  124.     int choice;
  125.     char cont;
  126.  
  127.     do {
  128.         cout << "\nMenu\n1: Accept & Display\n2: DFS Comparison\n3: BFS Comparison\nEnter your choice: ";
  129.         cin >> choice;
  130.  
  131.         switch (choice) {
  132.         case 1:
  133.             g.accept();
  134.             g.display();
  135.             break;
  136.         case 2: {
  137.             g.reset();
  138.             cout << "\nNormal DFS starting from vertex 0:\n";
  139.             auto startNormalDFS = chrono::high_resolution_clock::now();
  140.             g.normalDFS(0);
  141.             auto endNormalDFS = chrono::high_resolution_clock::now();
  142.             chrono::duration<double> normalDFSTime = endNormalDFS - startNormalDFS;
  143.  
  144.             g.reset();
  145.             cout << "\n\nParallel DFS starting from vertex 0:\n";
  146.             auto startParallelDFS = chrono::high_resolution_clock::now();
  147.             g.parallelDFS(0);
  148.             auto endParallelDFS = chrono::high_resolution_clock::now();
  149.             chrono::duration<double> parallelDFSTime = endParallelDFS - startParallelDFS;
  150.  
  151.             cout << "\n\nTime taken for Normal DFS: " << normalDFSTime.count() << " seconds";
  152.             cout << "\nTime taken for Parallel DFS: " << parallelDFSTime.count() << " seconds\n";
  153.             break;
  154.         }
  155.         case 3: {
  156.             g.reset();
  157.             cout << "\nNormal BFS starting from vertex 0:\n";
  158.             auto startNormalBFS = chrono::high_resolution_clock::now();
  159.             g.normalBFS(0);
  160.             auto endNormalBFS = chrono::high_resolution_clock::now();
  161.             chrono::duration<double> normalBFSTime = endNormalBFS - startNormalBFS;
  162.  
  163.             g.reset();
  164.             cout << "\n\nParallel BFS starting from vertex 0:\n";
  165.             auto startParallelBFS = chrono::high_resolution_clock::now();
  166.             g.parallelBFS(0);
  167.             auto endParallelBFS = chrono::high_resolution_clock::now();
  168.             chrono::duration<double> parallelBFSTime = endParallelBFS - startParallelBFS;
  169.  
  170.             cout << "\n\nTime taken for Normal BFS: " << normalBFSTime.count() << " seconds";
  171.             cout << "\nTime taken for Parallel BFS: " << parallelBFSTime.count() << " seconds\n";
  172.             break;
  173.         }
  174.         default:
  175.             cout << "Invalid choice!";
  176.         }
  177.  
  178.         cout << "\nDo you want to continue? (y/n): ";
  179.         cin >> cont;
  180.     } while (cont == 'y' || cont == 'Y');
  181.  
  182.     return 0;
  183. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Menu
1: Accept & Display
2: DFS Comparison
3: BFS Comparison
Enter your choice: Invalid choice!
Do you want to continue? (y/n):
https://ideone.com/0XRkFp
language:
C++ (gcc 8.3)
created:
3 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!