hpc_dfsbfs

#include <iostream>
#include <vector>
#include <queue>
#include <omp.h>

using namespace std;

// Graph class representing the adjacency list
class Graph {
    int V;  // Number of vertices
    vector<vector<int>> adj;  // Adjacency list

public:
    Graph(int V) : V(V), adj(V) {}
    // Add an edge to the graph
    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }
    // Parallel Depth-First Search
    void parallelDFS(int startVertex) {
        vector<bool> visited(V, false);
        parallelDFSUtil(startVertex, visited);
    }

    void parallelDFSUtil(int v, vector<bool>& visited) {
        visited[v] = true;
        cout << v << " ";
        // Iterate through adjacent vertices
        for (int i = 0; i < adj[v].size(); ++i) {
            int n = adj[v][i];
            // Check if the neighbor is unvisited
            if (!visited[n]) {
                // Ensure only one thread explores the unvisited neighbor
                {
                    if (!visited[n])
                        parallelDFSUtil(n, visited);
                }
            }
        }
    }

    // Parallel Breadth-First Search
    void parallelBFS(int startVertex) {
        vector<bool> visited(V, false);
        queue<int> q;
        visited[startVertex] = true;
        q.push(startVertex);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            cout << v << " ";
            // Iterate through adjacent vertices
            #pragma omp parallel for
            for (int i = 0; i < adj[v].size(); ++i) {
                int n = adj[v][i];
                // Check if the neighbor is unvisited
                if (!visited[n]) {
                    // Ensure only one thread updates the visited array
                    #pragma omp critical
                    {
                        if (!visited[n]) {
                            visited[n] = true;
                            q.push(n);
                        }
                    }
                }
            }
        }
    }
};

int main() {

    // Create a graph
    double start_time, end_time;

    Graph g(7);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    g.addEdge(2, 6);

    /*
              0      DFS - 0 1 3 4 2 5 6 🍾 | 0 2 6 5 1 4 3
            /   \    BFS - 0 1 2 3 4 5 6 🍾 | 0 2 1 6 5 4 3
           1     2
          / \   / \
         3   4 5   6
    */

    cout << "Depth-First Search (DFS): ";
    start_time = omp_get_wtime();
    g.parallelDFS(0);
    end_time = omp_get_wtime();
    cout << endl;
    cout << "Parallel DFS took : " << end_time - start_time << " seconds.\n";

    cout << "Breadth-First Search (BFS): ";
    start_time = omp_get_wtime();
    g.parallelBFS(0);
    end_time = omp_get_wtime();
    cout << endl;
    cout << "Parallel BFS took : " << end_time - start_time << " seconds.\n";

    return 0;
}



/*
This code implements parallel Depth-First Search (DFS) and parallel Breadth-First
Search (BFS) algorithms using OpenMP. Let's go through it:

**Graph Class:**
- The `Graph` class represents an undirected graph using an adjacency list.
- It has methods to add edges to the graph and to perform parallel DFS and parallel BFS.

**Parallel Depth-First Search (DFS):**
- The `parallelDFS` function initiates the DFS traversal from a specified start vertex.
- The `parallelDFSUtil` function is a recursive utility function that performs the DFS traversal.
- Inside `parallelDFSUtil`, the `visited` array is accessed to mark vertices as visited.
- Parallelism is introduced by OpenMP pragmas to explore adjacent vertices concurrently.
However, a critical section is used to ensure that only one thread updates the `visited` array.

**Parallel Breadth-First Search (BFS):**
- The `parallelBFS` function initiates the BFS traversal from a specified start vertex.
- It uses a queue to store vertices to be processed.
- Inside the BFS loop, OpenMP parallelism is introduced to explore adjacent vertices concurrently. Again,
    a critical section is used to ensure thread safety when updating the `visited` array and the queue.

**Main Function:**
- In the `main` function, a `Graph` object `g` is created with 7 vertices and edges connecting them.
- DFS and BFS are performed starting from vertex 0, and the time taken for each operation is measured and printed.

**Parallelism in DFS and BFS:**
- In both algorithms, OpenMP directives (`#pragma omp parallel for`) are used to parallelize the loop
    that iterates through adjacent vertices.
- The critical sections (`#pragma omp critical`) ensure that shared data structures (`visited` array and
    queue) are accessed safely by multiple threads.

**Output:**
- The DFS and BFS traversals are printed along with the time taken for each parallel traversal.

This code demonstrates how to parallelize graph traversal algorithms using OpenMP, improving performance
by leveraging multiple threads to explore vertices concurrently.

Depth-First Search (DFS):

Normal DFS: In the normal depth-first search, the time complexity depends on the number of vertices (
𝑉) and edges (𝐸) in the graph. In the worst-case scenario, where the graph is represented using
an adjacency list, and every vertex is visited exactly once, the time complexity is 𝑂(𝑉+𝐸).
This is because each vertex and each edge is visited once.

Parallel DFS: Parallel depth-first search can offer potential speedup by exploring different
branches of the search tree concurrently. However, the time complexity remains 𝑂(𝑉+𝐸) because the
fundamental operation of visiting each vertex and edge remains the same.

Breadth-First Search (BFS):

Normal BFS: Similar to DFS, the time complexity of normal breadth-first search depends on the number of vertices (
𝑉) and edges (𝐸) in the graph. In the worst-case scenario, where the graph is
represented using an adjacency list, and every vertex is visited exactly once, the time complexity is  𝑂(𝑉+𝐸).

Parallel BFS: Parallel breadth-first search explores different levels of the
search tree concurrently, potentially offering speedup. However, like the parallel DFS,
the time complexity remains 𝑂(𝑉+𝐸)
O(V+E) because each vertex and edge still need to be visited once.

In summary, while parallel DFS and BFS algorithms can improve performance by
exploiting concurrency, the fundamental time complexity remains the same as their
sequential counterparts. This is because the number of vertices and edges still
determine the overall computational cost of exploring the entire graph.
*/