# MultiAspect Graphs: Algebraic Representation and Algorithms
## 4 MAG Algorithms
### Depth-First Search (DFS)
#### 4.5.2 Sub-Determined DFS  
The sub-determined DFS algorithm is presented in Algorithm 14 and is similar to the non sub-determined one. The main differences are at the Procedure Visit-DFS-Sub and the call to a sub-determined BFS at line 15 of the DFS-Sub function. This version for a sub-determined BFS is considered to determine the reachability of sub-determined vertices from the root of each sub-determined DFS tree. This is necessary to prevent including vertices not reachable from the tree root in the non sub-determined MAG into the DFS trees constructed by Procedure Visit-DFS-Sub. An example of this is provided in Equation (71). The difference in Procedure Visit-DFS-Sub is that in addition to the root vertex for the DFS tree it also receives the reachability vector produced by the BFS. This reachability vector has one entry for each sub-determined vertex. This entry has value 1 when corresponding to a reachable vertex, while entries corresponding to unreachable vertices carry value 0. ```
input :J(\(H\)), \(\tau(H)\) output :\(\mathit{discTime}\), \(\mathit{finTime}\), \(\mathit{pred}\)
1 DFS(\(\mathsf{J}(H)\)), \(\tau(H)\)
2\(n\leftarrow|\mathbb{V}(H)|\)
3 for\(u=1\) to \(n\)do
4\(\mathit{color}[u]\gets 0\)// set all vertices to white (unvisited)
5\(\mathit{discTime}[u]\leftarrow-1\)// set discovery times to nil
6\(\mathit{finTime}[u]\leftarrow-1\)// set finish times to nil
7\(\mathit{pred}[u]\leftarrow-1\)// set predecessors to nil
8
9 end for
10\(time\gets 0\)
11 for\(u=1\) to \(n\)do
12 if\(\mathit{color}[u]=0\)then
13\(\mathit{DFS}\)-\(\mathit{Visit}(u)\)
14
15 end if
16
17 end for
18 return\(\mathit{discTime}\), \(\mathit{finTime}\), \(\mathit{pred}\)
19
20 Procedure\(\mathit{DFS}\)-\(\mathit{Visit}(u)\)\(\mathit{color}[u]\gets 1\)// set vertex u to gray (visited)
21\(\mathit{discTime}[u]\leftarrow\mathit{time}\)
22\(time\gets time+1\)
23 foreach\(\mathit{v}\) successor of \(u\)do
24 if\(\mathit{color}[v]=0\)then
25\(\mathit{pred}[v]\gets u\)\(\mathit{DFS}\)-\(\mathit{Visit}(v)\)
26
27 end if
28
29 end for
30\(\mathit{color}[u]\gets 2\)// set vertex u to black (closed)
31\(\mathit{finTime}[u]\gets time\)
32\(time\gets time+1\)
```  
**Algorithm 13**DFS for composite vertices. To determine the time complexity of Algorithm 14, we consider that the sub-determined BFS executed at line 15 of Function DFS-Sub is done once for the root vertex of each sub-determined DFS tree. Since it is executed only once for each DFS tree, we conclude that the total time expended in the sub-determined BFS algorithm is \(O(|\mathbb{V}(H)|+|E(H)|)\). Since the reachability check included in Function Visit-DFS-Sub is done by verifying the content of one entry of the reachability vector, it is done in \(O(1)\) and therefore does not affect the overall time complexity of the Visit-DFS-Sub Function. Therefore, since the DFS is run upon the sub-determined MAG, it follows that the time complexity of doing the DFS part of the Algorithm is \(O(|\mathbb{V}_{\xi}(H)|+|E_{\xi}(H)|)\). Since \(|\mathbb{V}_{\xi}(H)|<|\mathbb{V}(H)|\) and \(|E_{\xi}(H)|<|E(H)|\), we conclude that the time complexity is dominated by the BFS used for the reachability determination, making the overall time complexity of Algorithm 14 to be \(O(|\mathbb{V}(H)|+|E(H)|)\).