Sequnetial vs Parallel Computing for Breadth-First Search (BFS)

parallel_bfs.cpp

/*
How Parallel Computing Works for Breadth-First Search (BFS)
(Level-by-Level Parallel BFS Using OpenMP)

Problem:
Given an unweighted graph and a source vertex,
perform Breadth-First Search (BFS) and compute the
distance (level) of each vertex from the source.

---------------------------------------------------
SEQUENTIAL BFS
---------------------------------------------------
- Uses a queue
- Processes vertices one by one
- Naturally level-ordered

---------------------------------------------------
PARALLEL BFS STRATEGY (LEVEL-SYNCHRONOUS)
---------------------------------------------------
1. BFS proceeds LEVEL BY LEVEL
2. All vertices in the current frontier (same level)
   can be processed in parallel
3. For each vertex in the frontier:
   - Explore all its neighbors
   - Unvisited neighbors form the next frontier
4. Synchronization occurs at the end of each level

---------------------------------------------------
KEY PARALLEL CHALLENGES
---------------------------------------------------
- Avoid visiting a node multiple times
- Safely update visited[] and distance[]
- Efficient construction of next frontier

This program compares:
- Sequential BFS
- Parallel BFS using OpenMP

Compile:
>>> g++ -fopenmp -O2 -o parallel_bfs parallel_bfs.cpp
Run:
>>> ./parallel_bfs
*/

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

int main()
{
    const int V = 1000000;  // 1 million vertices
    const int E = 10000000; // 10 million edges

    const int SRC = 0;

    vector<vector<int>> adj(V);
    vector<int> dist_seq(V, -1), dist_par(V, -1);

    // ---------------------------
    // Graph Initialization
    // ---------------------------
    srand(0);
    for (int i = 0; i < E; i++)
    {
        int u = rand() % V;
        int v = rand() % V;
        if (u != v)
        {
            adj[u].push_back(v);
            adj[v].push_back(u); // Undirected graph
        }
    }

    // ---------------------------
    // 1. Sequential BFS
    // ---------------------------
    double start_seq = omp_get_wtime();

    queue<int> q;
    dist_seq[SRC] = 0;
    q.push(SRC);

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int v : adj[u])
        {
            if (dist_seq[v] == -1)
            {
                dist_seq[v] = dist_seq[u] + 1;
                q.push(v);
            }
        }
    }

    double end_seq = omp_get_wtime();
    double seq_time = end_seq - start_seq;

    // ---------------------------
    // 2. Parallel BFS (Level-by-Level)
    // ---------------------------
    double start_par = omp_get_wtime();

    vector<int> frontier, next_frontier;
    vector<char> visited(V, 0);

    frontier.push_back(SRC);
    visited[SRC] = 1;
    dist_par[SRC] = 0;

    int level = 0;

    while (!frontier.empty())
    {
        next_frontier.clear();

#pragma omp parallel
        {
            vector<int> local_next;

#pragma omp for nowait
            for (int i = 0; i < (int)frontier.size(); i++)
            {
                int u = frontier[i];

                for (int v : adj[u])
                {
                    // Atomic check-and-set
                    if (!visited[v])
                    {
                        bool take = false;

#pragma omp critical
                        {
                            if (!visited[v])
                            {
                                visited[v] = 1;
                                take = true;
                                dist_par[v] = level + 1;
                            }
                        }

                        if (take)
                        {
                            local_next.push_back(v);
                        }
                    }
                }
            }

#pragma omp critical
            next_frontier.insert(next_frontier.end(),
                                 local_next.begin(),
                                 local_next.end());
        }

        frontier.swap(next_frontier);
        level++;
    }

    double end_par = omp_get_wtime();
    double par_time = end_par - start_par;

    // ---------------------------
    // Verification
    // ---------------------------
    bool correct = true;
    for (int i = 0; i < V; i++)
    {
        if (dist_seq[i] != dist_par[i])
        {
            correct = false;
            break;
        }
    }

    // ---------------------------
    // Print Results
    // ---------------------------
    cout << "Parallel BFS (Level-by-Level)\n\n";

    cout << "Sequential Time: " << seq_time << " sec\n";
    cout << "Parallel Time:   " << par_time << " sec\n";

    cout << "\nSpeedup = " << (seq_time / par_time) << "x\n";

    if (correct)
    {
        cout << "\nBFS traversal is correct.\n";
    }
    else
    {
        cout << "\nMismatch detected in BFS results!\n";
    }

    return 0;
}

/*
Output Example:
Parallel BFS (Level-by-Level)

Sequential Time: 0.0349998 sec
Parallel Time:   0.0120001 sec

Speedup = 2.91663x

BFS traversal is correct.

## Performance depends heavily on graph structure.
*/