-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfs.cpp
131 lines (114 loc) · 2.65 KB
/
bfs.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include "mpi.h"
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define MAX_QUEUE_SIZE 5
int areAllVisited(int visited[], int size)
{
for(int i = 0; i < size; i++)
{
if(visited[i] == 0)
return 0;
}
return 1;
}
int main(int argc, char *argv[])
{
//Variables and Initializations
int size, rank;
int adjacency_matrix[100];
int adjacency_queue[MAX_QUEUE_SIZE];
int source_vertex;
int no_of_vertices;
int adjacency_row[10];
int bfs_traversal[100];
int visited[100];
//MPI Code
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if(rank == 0)
{
//Entering the Number of vertices
cout<<"Enter the number of vertices\n";
cin>>no_of_vertices;
//Entering the Adjacency Matrix
cout<<"Enter the Adjacency Matrix\n";
for(int i = 0; i < no_of_vertices * no_of_vertices; i++)
{
cin>>adjacency_matrix[i];
}
cout<<endl;
//Entering the Source Vertex
cout<<"Enter the Source Vertex\n";
cin>>source_vertex;
cout<<endl;
}
//Broadcasting the Number of vertices and the source vertex;
MPI_Bcast(&no_of_vertices, 1, MPI_INT, 0, MPI_COMM_WORLD);
MPI_Bcast(&source_vertex, 1, MPI_INT, 0, MPI_COMM_WORLD);
//Scattering each row of the adjacency matrix to each of the processes
MPI_Scatter(adjacency_matrix, no_of_vertices, MPI_INT, adjacency_row, no_of_vertices, MPI_INT, 0, MPI_COMM_WORLD);
//Initializing The Adjacency Queue of each process
for(int i = 0; i < MAX_QUEUE_SIZE; i++)
{
adjacency_queue[i] = -1;
}
//BFS code
int index = 0;
if(rank >= source_vertex)
{
for(int i = 0; i < no_of_vertices; i++)
{
if(adjacency_row[i] == 1)
{
adjacency_queue[index++] = i;
}
}
}
//Each Process printing the adjacent nodes found
cout<<"Process "<<rank<<": ";
for(int i = 0; i < index; i++)
{
cout<<adjacency_queue[i]<<" ";
}
cout<<endl;
//For synchronization
MPI_Barrier(MPI_COMM_WORLD);
//Gathering all the nodes in BFS found by each process
MPI_Gather(adjacency_queue, MAX_QUEUE_SIZE, MPI_INT, bfs_traversal, MAX_QUEUE_SIZE, MPI_INT, 0, MPI_COMM_WORLD);
//Printing the Order of traversed nodes in root
for(int i = 0; i < no_of_vertices; i++)
{
visited[i] = 0;
}
if(rank == 0)
{
cout<<"\nBFS Traversal: "<<endl;
cout<<source_vertex;
for(int i = 0; i < MAX_QUEUE_SIZE * no_of_vertices; i++)
{
//Exit Condition
if(areAllVisited(visited, no_of_vertices))
{
break;
}
if(bfs_traversal[i] != -1)
{
if(visited[bfs_traversal[i]] == 0)
{
cout<<" -> "<<bfs_traversal[i];
visited[bfs_traversal[i]] = 1;
}
}
else
{
continue;
}
}
}
//End of BFS code
MPI_Finalize();
return 0;
}