# MultiAspect Graphs: Algebraic Representation and Algorithms
## 4 MAG Algorithms
### Breadth-First Search (BFS)
#### 4.4.2 Sub-Determined BFS
\right] \tag{64}\]  
and  
\[\left(\mathbf{I}_{3}-\mathbf{J}_{\zeta_{R}}(R)\right)^{-1}=\left[ \begin{array} []{cccc}1&1&\mathbf{1}\\ 0&1&1\\ 0&0&1\\ \end{array} \right]. \tag{65}\]  
Remembering that the entries of the matrices in Equations (63)-(65) are to be considered only as zero or non-zero, it can be seen that the matrix at Equation (63) has a \(0\) at entry \((1,3)\), while the matrices at Equations (64) and (65) have a non-zero entry at this same position. This illustrates the situation in which a BFS is done on the sub-determined (aggregated) MAG, as in Equations (64) and (65), i.e., paths that are not present on the original MAG can appear on the sub-determined form, potentially altering the results obtained by algorithms applied to it. For instance, considering the MAG \(T\), depicted in Figure 3, for a sub-determination \(\zeta_{t}=\texttt{011}_{2}\), which drops the time aspect, and considering \(\rho_{H}=0.5\) so that \(\mathbf{J}_{\rho}(T)=0.5\ \mathbf{J}(T)\), we have that  
\[\mathbf{M}_{\zeta t}(T)\ \left(\sum_{i=0}^{\infty}\mathbf{J}_{\rho}(T)^{i} \right)\ \mathbf{M}_{\zeta t}(T)^{T}=\left[ \begin{array}{cccccc}3&0&0&0&0&0\\ 0&7.8&2.2&1.3&5.2&0\\ 0&2.2&4.6&0.2&1.3&0\\ 0&1.3&0.2&4.6&2.2&0\\ 0&5.2&1.3&2.2&7.8&0\\ 0&0&0&0&3\\ \end{array} \right]. \tag{66}\]  
Algorithm 12 shows a combinational version of the sub-determined BFS. This procedure ensures that only paths present on the original MAG are considered on the sub-determined BFS. The sub-determination of the results obtained from the BFS is done in the internal **if**, comprising lines 21 to 25 of Algorithm 12. ```
input :\(\mathbf{J}(H)\), \(\tau(H)\), \(\zeta\) and \(\mathbf{s}\in\mathbb{V}_{\zeta}(H)\) output :vertices, distance, pred
1 BFS-Sub(\(\mathbf{J}(H),\tau(H),\zeta,\mathbf{s}\))
2\(n\leftarrow|\mathbb{V}(H)|\)\(nS\leftarrow|\mathbb{V}_{\zeta}(H)|\) \(T_{\zeta}\leftarrow\tau_{\zeta}(H)\) // \(\zeta\) sub-determined companion tuple vertices \(\leftarrow\) vector of \(nS\) integers, all \(0\) distance \(\leftarrow\) vector of \(nS\) integers, all \(\infty\) pred \(\leftarrow\) vector of \(nS\) integers, all \(Nil\) colorS \(\leftarrow\) vector of \(nS\) integers, all \(0\) // set all sub-determined vertices to white (unvisited) (unvisited) color \(\leftarrow\) vector of \(n\) integers, all \(0\) // set all vertices to white (unvisited) \(Q\leftarrow\) empty queue for every \(\mathbf{v}\in\mathbb{V}(H)\) where \(D(\mathbf{v},\tau_{\zeta}(H))=D(\mathbf{s},\tau_{\zeta}(H))\)do
3\(Enqueue(Q,D(\mathbf{v},\tau(H)))\)\(\leftarrow\) \(1\) \(color[D(\mathbf{v},\tau(H))]\gets 1\)
4 end for
5 vertices[\(D(\mathbf{s},\tau_{\zeta})-1\)]\(\leftarrow\) \(1\) distance[\(D(\mathbf{s},T_{\zeta})\)]\(\leftarrow\) \(0\) while\(Q\) not emptydo
6\(u\gets head[Q]\) for each \(v\) successor of \(u\)do
7 if\(color[v]=0\)then
8\(color[v]\gets 1\)// set vertex v to gray (visited) \(Enqueue(Q,v)\) if\(color[D(v,T_{\zeta})]=0\)then
9\(colorS[D(v,T_{\zeta})]\gets 1\) // set sub-determined vertex \(D(v,T_{\zeta})\) to gray (visited) \(vertices[D(v,T_{\zeta})]\gets 1\) \(distance[D(v,T_{\zeta})]\gets distance[D(u,T_{\zeta})]+1\) \(pred[D(v,T_{\zeta})]\gets D(u,T_{\zeta})\)
10 end for
11
12 end for
13\(color[u]\gets 2\) // set vertex u to black (closed) \(Dequeue(Q)\)
14 end for
15 returnvertices, distance, pred
```  
**Algorithm 12**Sub-determined BFS. After applying Algorithm 12 to the MAG \(R\) with initial vertex \(s=1\) and sub-determination \(\zeta_{R}=\texttt{01}_{2}\), the obtained result is  
\[vertices =[1,2] \tag{67}\] \[distances =[0,1,\infty]\] \[pred =[Nil,1,Nil],\]  
which is consistent with the result obtained by Equation (63). Further, applying Algorithm 12 to MAG \(T\), shown in Figure 3, with starting composite vertex \(s=(2,Bus)\) and applying the sub-determination \(\zeta_{t}=011_{2}\), which drops the time aspect, the obtained result is  
\[ \begin{split} vertices&=[2,5,3,4]\\ distances&=[\infty,0,1,2,1,\infty]\\ pred&=[Nil,Nil,2,5,2,Nil].\end{split}