HighPerformanceComputing/Codes/Code-1.cpp

// Code-1 (Parallel BFS and DFS)

/*
 * THIS CODE HAS BEEN TESTED AND IS FULLY OPERATIONAL.
 *
 * Problem Statement: 
 *  Design and implement Parallel Breadth First Search and
 *  Depth First Search based on existing algorithms using OpenMP.
 *  Use a Tree or an undirected graph for BFS and DFS.
 *
 * Code from HighPerformanceComputing (SPPU - Final Year - Computer Engineering - Content)
 * repository on KSKA Git: https://git.kska.io/sppu-be-comp-content/HighPerformanceComputing
 **/

/*
 * EXECUTION INSTRUCTIONS (Debian-based distributions):
 *
 * i) Install g++ with OpenMP support:
 *   sudo apt update
 *   sudo apt install g++
 *
 * ii) Compile:
 *   g++ -fopenmp Code-1.cpp -o Code-1
 *
 * iii) Execute:
 *   ./Code-1
 **/

// BEGINNING OF CODE
#include <iostream>
#include <vector>
#include <omp.h>

using namespace std;

// Undirected graph with parallel BFS and DFS traversal via OpenMP.
class Graph {
    int V;
    vector<vector<int>> adj;

public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Level-synchronous BFS: all nodes at the current depth (the "frontier")
    // are expanded in parallel before moving to the next level. This is the
    // natural unit of parallelism for BFS, processing individual nodes is too
    // fine-grained for threads to be useful.
    void parallelBFS(int start) {
        vector<bool> visited(V, false);
        vector<int> frontier;

        visited[start] = true;
        frontier.push_back(start);

        cout << "Parallel BFS from node " << start << ": ";

        while (!frontier.empty()) {
            for (int u : frontier)
                cout << u << " ";

            vector<int> next_frontier;

            // Each thread accumulates its own local candidates to avoid
            // contention on a shared next_frontier vector.
            #pragma omp parallel
            {
                vector<int> local_next;

                // nowait: threads that finish early skip the implicit barrier
                // and proceed directly to the merge below.
                // schedule(dynamic): faster threads pick up remaining chunks
                // when adjacency list sizes vary across nodes.
                #pragma omp for nowait schedule(dynamic)
                for (int i = 0; i < (int)frontier.size(); i++) {
                    for (int v : adj[frontier[i]]) {
                        // The check-and-set on visited[] must be a single
                        // critical section — without it, two threads could
                        // both see visited[v]==false and both enqueue v,
                        // producing duplicates in the next frontier.
                        bool should_visit = false;
                        #pragma omp critical
                        {
                            if (!visited[v]) {
                                visited[v] = true;
                                should_visit = true;
                            }
                        }
                        // local_next is thread-private so no lock needed here.
                        if (should_visit)
                            local_next.push_back(v);
                    }
                }

                // Merge: one thread at a time appends its local results.
                // This is a separate critical section from the one above
                // so the two do not serialize against each other.
                #pragma omp critical
                {
                    next_frontier.insert(next_frontier.end(),
                                         local_next.begin(),
                                         local_next.end());
                }
            } // implicit barrier: all threads finish before frontier is swapped

            frontier = next_frontier;
        }

        cout << endl;
    }

    // Iterative DFS using a vector as a stack (push_back/pop_back).
    // vector is used instead of std::stack because std::stack cannot be
    // safely shared across threads.
    void parallelDFS(int start) {
        vector<bool> visited(V, false);
        vector<int> stack;

        stack.push_back(start);

        cout << "Parallel DFS from node " << start << ": ";

        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();

            // A node may be pushed multiple times before it is marked visited
            // (two threads can both see visited[v]==false). This guard ensures
            // it is processed only once.
            if (visited[u]) continue;
            visited[u] = true;
            cout << u << " ";

            vector<int> to_push;

            #pragma omp parallel
            {
                vector<int> local_push;

                #pragma omp for nowait schedule(dynamic)
                for (int i = 0; i < (int)adj[u].size(); i++) {
                    // visited[] is only read here, not written, so no critical
                    // section is needed. Stale reads may cause duplicates but
                    // the guard above handles that safely.
                    if (!visited[adj[u][i]])
                        local_push.push_back(adj[u][i]);
                }

                #pragma omp critical
                {
                    to_push.insert(to_push.end(),
                                   local_push.begin(),
                                   local_push.end());
                }
            }

            for (int v : to_push)
                stack.push_back(v);
        }

        cout << endl;
    }
};

int main() {
    Graph g(6);

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

    g.parallelBFS(0);
    g.parallelDFS(0);

    return 0;
}
// END OF CODE

/*
EXAMPLE OUTPUT:

$ ./Code-1 
Parallel BFS from node 0: 0 1 2 5 3 4 
Parallel DFS from node 0: 0 2 5 1 4 3 
*/