## 6 BFS-Based Implementation of RDF Graph Traversals over MapReduce  
There exist in literature two well-known approaches for representing a graph: through an _adjacency matrix_, and through _adjacency lists_. The former has the advantage of \(\mathrm{O}\left(1\right)\) constant lookup over graph data, with the drawback of an increased usage of memory (\(\mathrm{n}\times\mathrm{n}\), where \(\mathrm{n}\) represents the number of vertices), also for sparse graphs. In practice, while the majority of graphs are not so dense, we end with a waste of space having a big matrix with few values (not all the cells of the matrix will be used to store a value). The latter stores, for every vertex, a list of vertices connected to it (called _adjacent nodes_), thus reducing the overall memory requirement. This representation has also the advantage of being suited to feed a MapReduce job. As regards the proper RDF graph implementation as _Abstract Data Type_ (ADT), we exploited the well-known _Apache Jena RDF API_[74], which models the target RDF graph in terms of collection of _RDF nodes_, which are connected via a _direct graph_ by means of _labelled relations_. There are several algorithms for visiting a graph, but BFS (see Algorithm 1) has been proven to be more suited for parallel processing. BFS algorithm cannot be expressed into a single MapReduce job directly, because the while construct at every step increments the _frontier_ of exploration in the graph. Moreover, this frontier expansion permits the finding of the paths to _every_ node explored from the source node. Since the BFS algorithm cannot be codified within a MapReduce job, we propose a novel approach to coordinate a series of MapReduce jobs that check when to stop the execution of these jobs. This is called _convergence criterion_. To this end, we propose feeding the output of a job as the input of the successive one, and to apply a way to count if further nodes must be explored via maintaining a _global counter_ updated at each iteration that, in the standard BFS, is represented by the iterator's position in the queue itself. In our proposed implementation, the only convergence criterion that we make use of is thus represented by counting the jobs that terminate (to this end, MapReduce's _DistributedCache_ is exploited), but of course other more complex criteria may be adopted in future research efforts (e.g., based on _load balancing issues_). ```
Input:\(u\) - source node from which the visit starts;\(n\) - number of vertices; \(L\) - adjacency lists Output:\(Q\) - list of visited nodes Begin \(Q\leftarrow\varnothing\);  visited \(\leftarrow\)\(\emptyset\); for(\(i\) = 0 to \(n\) - 1) do  visited[\(i\)] = 0;  endfor;  visited[\(u\)] = 1; 0 \(\leftarrow\)\(u\);  while(\(Q\) + \(\varnothing\)) do \(u\) - 0;  for(each \(v\) \(\in\)\(L_{u}\)) do // \(L_{u}\) is the adjacency list of \(u\) if(visited[\(v\)] == 0) then  visited[\(v\)] = 1; 0 \(\leftarrow\)\(v\);  endif;  endfor;  endwhile;  return 0;  End;
```  
**Algorithm 1**BFS(\(u,n,L\))  
Basically, in order to control the algorithmic flow and safely achieve the convergence criterion, the proposed algorithm adopts the well-known _colorability programming metaphor_. According to this programming paradigm, graph processing algorithms can be implemented by assigning a color-code to each possible node's state (in the _proper_ semantics of the target algorithm) and then superimposing certain actions for each specific node's state. This paradigm is, essentially, an enriched _visiting strategy_ over graphs, and, in fact, BFS is only a possible instance of such strategy. To this end, the proposed approach makes use of suitable _metadata information_ (stored into text files), which models, for each node of the graph stored in a certain Cloud node, its adjacent list plus additional information about the node's state. An example of these metadata is as follows:  
```
1 3,2,|GREY|1 1 10 12,|WHITE|? 11 10,|WHITE|? 12 NULL,|WHITE|? 13 NULL,|WHITE|? 146,12,|WHITE|?