bfs1-rodinia-region1

In Graph Theory, Breadth-First Search (BFS) is strategy for searching a graph. BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. Unlike Depth First Search, BFS is not a recursive algorithm. It uses a queue as an auxiliary data structure. In essence, the way BFS is done is that first the source node is enqueued. Then, the queue is dequeued in a FIFO manner, and every time an element of the queue is dequeued, all of its neighbors that haven't been traversed so far are enqueued. In other variations, instead of always dequeuing the head of the queue, there might be a priority queue implemented, and the element with the lowest cost is dequeued (since we want to proceed with the lowest cost path).

A Breadth-first search between two points in a graph always gives us the shortest distance between them.

Code Snippet

// int no_of_nodes = 1000000
// bool array: h_graph_mask, h_updating_graph_mask, h_graph_visited (all three of size no_of_nodes with all elements initialized to false).
// for the source node, h_graph_mask and h_graph_visited is initialized to true, whereas h_updating_graph_mask is initialized to false.
// bool stop

do
{

stop = false;

for(int tid = 0; tid < no_of_nodes; tid++ ) {
   if (h_graph_mask[tid] == true) { 
      h_graph_mask[tid]=false;
      for(int i=h_graph_nodes[tid].starting; i < (h_graph_nodes[tid].no_of_edges + h_graph_nodes[tid].starting); i++) {	// This loop runs an average of 3 times per outer loop.
         int id = h_graph_edges[i];
         if(!h_graph_visited[id]) {
            h_cost[id]=h_cost[tid]+1;
            h_updating_graph_mask[id]=true;
         }
      }
   }
}

for(int tid=0; tid < no_of_nodes ; tid++ )
{
   if (h_updating_graph_mask[tid] == true)
   {
      h_graph_mask[tid]=true;
      h_graph_visited[tid]=true;
      stop=true;
      h_updating_graph_mask[tid]=false;
   }
}

}while (stop==true) // executes 12 times.