# MultiAspect Graphs: Algebraic Representation and Algorithms
## 4 MAG Algorithms
### Breadth-First Search (BFS)
#### 4.4.1 BFS for Composite Vertices  
The non sub-determined BFS in its combinational form is constructed directly upon the MAG's adjacency matrix, \(\mathbf{J}(H)\). ```
input :\(\mathbf{J}(H)\), \(\tau(H)\), and \(\mathbf{s}\in\mathbb{V}(H)\) output :vertices, distance, pred
1 BFS(\(H\)), \(\tau(H)\), \(\mathbf{s}\))
2\(n\leftarrow|\mathbb{V}(H)|\)vertices\(\leftarrow\) vector of \(n\) integers, all 0
3\(distance\leftarrow\) vector of \(n\) integers, all \(\infty\)
4\(pred\leftarrow\) vector of \(n\) integers, all \(Nil\)
5\(color\leftarrow\) vector of \(n\) integers, all 0 // set all vertices to white (unvisited)
6\(Q\leftarrow\) empty queue vertices[\(D(\mathbf{s},\tau(H))\)] \(\gets 1\)
7\(color[D(\mathbf{s},\tau(H))]\gets 1\)
8\(distance[D(\mathbf{s},\tau(H))]\gets 0\)
9\(Equeue(Q,D(\mathbf{s},\tau(H)))\)
10 while\(Q\) not emptydo
11\(u\gets head[Q]\)for each \(v\) successor of \(u\)do
12 if\(color[v]=0\)then
13\(color[v]\gets 1\)// set vertex v to gray (visited)
14\(vertices[v]\gets 1\)
15\(distance[v]\gets distance[u]+1\)
16\(pred[v]\gets u\)
17\(Equeue(Q,v)\)
18
19 end if
20
21 end for
22\(Dqueue(Q)\)\(color[u]\gets 2\)// set vertex u to black (closed)
23
24 end for returnvertices, distance, pred
```  
**Algorithm 11**BFS for composite vertices. Considering Algorithm 11 and the standard form of the BFS algorithm encountered in [5], it can be seen that the difference is that the starting composite vertex \(\mathbf{s}\) has to be transformed from its tuple representation to its numerical representation, as shown in lines 8, 9, and 10 of Algorithm 11. Therefore, from the analysis provided in [5], we can conclude that the time complexity of Algorithm 11 is \(\mathcal{O}(|\mathbb{V}(H)|+|E(H)|)\). BFS is also closely related to matrix multiplication. This stems from the well-known property of the powers of the adjacency matrix, in which the \((i,j)\) entry of the \(n\)-th power of the adjacency matrix shows the number of existing walks of length \(n\) from vertex \(i\) to vertex \(j\)[33]. From this, we could think that for a given MAG \(H\), the series  
\[\mathbf{B}=\sum_{i=0}^{\infty}\mathbf{J}(H)^{i}=\mathbf{I}+\mathbf{J}(H)+ \mathbf{J}(H)^{2}+\mathbf{J}(H)^{3}+\mathbf{J}(H)^{4}+\ldots \tag{51}\]  
would produce a matrix \(\mathbf{B}\), such that the entry \(\mathbf{B}_{ij}\) indicates the number of walks of any length from vertex \(i\) to vertex \(j\). This is indeed the case when \(H\) happens to be an acyclic MAG, making \(\mathbf{J}(H)\) a nilpotent matrix. The existence of cycles in \(H\) makes that, for some vertices, there will exist walks of arbitrary length connecting them (namely, the cycles), making the series of Equation (51) divergent. However, since the objective is not to know the number of walks between each pair of vertices, but simply to know which vertices are reachable from each other (i.e., there is at least a path between them), this technical problem can be solved by multiplying the adjacency matrix \(\mathbf{J}(H)\) by a scalar \(\rho_{H}\), such that  
\[\rho_{H}<\frac{1}{\rho(\mathbf{J}(H))}, \tag{52}\]  
where \(\rho(\mathbf{J}(H))\) is the spectral radius of the matrix \(\mathbf{J}(H)\). This leads to the matrix  
\[\mathbf{J}_{\rho}(H)=\rho_{H}\,\mathbf{J}(H), \tag{53}\]  
so that the spectral radius of the matrix \(\mathbf{J}_{\rho}(H)<1\). This results that Equation (51) constructed with the matrix \(\mathbf{J}_{\rho}(H)\) converges. Since the convergence of the series is assured, Equation (51) can be re-expressed as  
\[\mathbf{B}=(I-\mathbf{J}_{\rho}(H))^{-1}. \tag{54}\]  
The matrix \(\mathbf{B}\) defined in Equation (54) has the property that, for any given composite vertex \(\mathbf{v}\in\mathbb{V}(H)\), the row \(D(\mathbf{v})\) of \(\mathbf{B}\) has non-zero entries in every column that corresponds to a composite vertex \(\mathbf{u}\in\mathbb{V}(H)\), such that \(\mathbf{u}\) is reachable from \(\mathbf{v}\). Hence, for a given composite vertex \(\mathbf{v}\), the row \(D(\mathbf{v})\) corresponds to the result of a BFS started at that composite vertex.