hpc_parabfs

#include<iostream>
#include<vector>
#include<omp.h>
#include<queue>
#include<bits/stdc++.h>
using namespace std;

queue<int>q;

void bfs(int start, int* arr, int n, int visit[])
{
    #pragma omp parallel for ordered
    for(int i=0; i<n; i++)
    {
        #pragma omp ordered
        if( ( *(arr + (n*start) + i)  == 1 ) && (visit[i] == 0) )
        {
            cout<<i<<" ";
            q.push(i);
            visit[i] = 1;
        }
    }

    q.pop();

    if(!q.empty()) bfs(q.front(), (int*)arr, n, visit);

}

int main()
{

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    //cout<<"BFS 0 1 2 3 4 5 6"<<endl;
    cout<<"Enter the number of vertices: ";
    int n;
    cin>>n;

    int arr[n][n] = {0};

    cout<<"Enter the number of edges: ";
    int edges;
    cin>>edges;

    for(int j=0; j<edges; j++)
    {
        int a, b;
        cout<<"Enter the two edges:"<<endl;
        cin>>a>>b;
        arr[a][b] = 1;
        arr[b][a] = 1;
    }

    int visit[n] = {0};

    cout<<"Enter the start vertex: ";
    int start;
    cin>>start;


    clock_t strt = clock();

    visit[start] = 1;
    cout<<start<<" ";
    q.push(start);

    bfs(start, (int*)arr, n, visit);

    clock_t stop = clock();

    cout<<"\nTime required : "<<(double)(stop-strt)<<" ms"<<endl;

    return 0;
}

/*

"Parallel Execution"
PS D:\C++> g++ -fopenmp parallel_bfs.cpp
PS D:\C++> ./a out
Enter the number of vertices: 7
Enter the number of edges: 6
Enter the two edges:
0 1
Enter the two edges:
0 2
Enter the two edges:
1 3
Enter the two edges:
1 4
Enter the two edges:
2 5
Enter the two edges:
2 6
Enter the start vertex: 0
0 1 2 3 4 5 6
Time required : 3 ms

"Serial Execution"
PS D:\C++> g++ parallel_bfs.cpp
PS D:\C++> ./a out
Enter the number of vertices: 7
Enter the number of edges: 6
Enter the two edges:
0 1
Enter the two edges:
0 2
Enter the two edges:
1 3
Enter the two edges:
1 4
Enter the two edges:
2 5
Enter the two edges:
2 6
Enter the start vertex: 0
0 1 2 3 4 5 6
Time required : 11 ms


*/

/*
This code implements a Breadth-First Search (BFS) algorithm for a graph represented as an adjacency matrix. Let's analyze it:

1. **`bfs` Function:**
   - The function `bfs` performs a Breadth-First Search traversal starting from a given vertex.
   - It iterates over the vertices adjacent to the `start` vertex in parallel using OpenMP directives.
   - Each thread checks if an adjacent vertex is reachable from the `start` vertex and if it has been
   visited before. If not visited, it prints the vertex, marks it as visited, and enqueues it.
   - The traversal continues by dequeuing the next vertex from the queue and recursively calling `bfs`
   until the queue is empty.

2. **`main` Function:**
   - It initializes the graph as an adjacency matrix `arr`, where `arr[i][j]` is 1 if there is an edge
   between vertices `i` and `j`.
   - User input is taken for the number of vertices `n`, the number of edges `edges`, and the edges themselves.
   - BFS traversal is initiated from a user-defined starting vertex.
   - The time taken for the BFS traversal is measured using the `clock` function.

3. **Parallel Execution:**
   - OpenMP directives (`#pragma omp parallel for ordered`) are used to parallelize the loop that iterates
   over adjacent vertices.
   - The `ordered` pragma ensures that the traversal order is maintained while still allowing parallel execution.

4. **Output:**
   - The BFS traversal sequence starting from the specified vertex is printed.
   - The time taken for the BFS traversal is also printed in milliseconds.

5. **Performance Consideration:**
   - Parallelizing BFS traversal can improve performance by utilizing multiple threads to explore adjacent
    vertices concurrently.
   - However, the efficiency of parallelization depends on factors such as the number of vertices, edges, and
   the distribution of edges in the graph.

6. **Time Complexity:**
   - The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges.
   - In this implementation, parallelization aims to improve performance but does not change the time complexity
    of the BFS algorithm.

Overall, this code demonstrates how Breadth-First Search can be implemented for graph traversal using OpenMP to
potentially improve performance through parallel execution.
*/