hpc_paradfs

#include <iostream>
#include <vector>
#include <stack>
#include <omp.h>
#include <bits/stdc++.h>

using namespace std;

void dfs(int start, int* arr, int n, int visited[]) {

    #pragma omp parallel for ordered
    for(int i = 0; i < n; i++) {
        #pragma omp ordered
        if( (*(arr + (start*n) + i) == 1) && (!visited[i]) )
        {
            visited[i] = 1;
            cout<<i<<" ";
            dfs(i, (int*)arr, n, visited);
        }
    }
}

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

    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 visited[n] = {0};

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

    clock_t strt = clock();

    cout<<start<<" ";
    visited[start] = 1;
    dfs(start, (int *)arr, n, visited);

    clock_t stop = clock();

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


    return 0;
}


/*

"Parallel Execution"
PS D:\C++> g++ -fopenmp parallel_dfs.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 3 4 2 5 6
Time required : 9 ms

"Serial Execution"
PS D:\C++> g++ parallel_dfs.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 3 4 2 5 6
Time required : 12 ms


*/

/*
This code implements Depth-First Search (DFS) for a graph represented as an adjacency matrix. Let's break it down:

1. **`dfs` Function:**
   - This function performs a Depth-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 marks it as visited, prints the vertex, and recursively calls `dfs` with it as the starting vertex.

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.
   - DFS traversal is initiated from a user-defined starting vertex.
   - The time taken for the DFS traversal is measured using the `clock` function.

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

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

5. **Performance Comparison:**
   - The code demonstrates the difference in execution time between parallel and serial DFS traversal.
   - Parallel execution is expected to be faster than serial execution due to concurrent processing of vertices.

6. **Sample Output:**
   - For the given input graph with vertices `{0, 1, 2, 3, 4, 5, 6}` and edges `{(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)}`,
   starting from vertex 0, the DFS traversal sequence is `{0, 1, 3, 4, 2, 5, 6}`.
   - The time required for parallel execution is 9 milliseconds, while for serial execution, it is 12 milliseconds.

Overall, this code showcases how Depth-First Search can be implemented for graph traversal using OpenMP parallelization,
potentially improving performance by leveraging multiple threads to process vertices concurrently.
*/