# On Finding Optimal (Dynamic) Arborescences
## 2 Optimal Arborescences
### Tarjan Algorithm
#### 2.2.2 Contraction Phase  
The contraction phase proceeds while _roots_\(\
eq\emptyset\) as follows; the while loop body is detailed in Algorithms 2-4. It pops a vertex \(r\) from _roots_, and it verifies if there are incident edges in \(r\) such that they do not belong to a contracted strongly connected component. If there are such edges, then it extracts the one with minimum weight; otherwise, it stops and it continues with another vertex in _roots_. See Algorithm 2 for the detailed pseudocode. ```
\(r\leftarrow\textsc{POP}(roots)\) if\(queues[r]\
eq\emptyset\)then \((u,r)\leftarrow\textsc{EXTRACT-MIN}(queues[r])\) while\(queues[r]\
eq\emptyset\) and \(\textsc{SFIND}(u)=\textsc{SFIND}(r)\)do \((u,r)\leftarrow\textsc{EXTRACT-MIN}(queues[r])\) endwhile if\(\textsc{SFIND}(u)=\textsc{SFIND}(r)\)then \(\mathit{rset}\leftarrow\mathit{rset}\cup\{r\}\) continue endif else \(\mathit{rset}\leftarrow\mathit{rset}\cup\{r\}\) continue endif
```  
**Algorithm 2** Main loop body of the contraction phase. Once an incident edge on \(r\) is found that does not lie within a strongly connected component, i.e., that is incident on a contracted strongly connected component, we must update forest \(F\). Hence, we create a new node \(\mathit{minNodeF}\) in forest \(F\) that is associated with edge \((u,r)\). If \(r\) is not part of a strongly connected component, i.e., \(r\) is not part of a cycle, then \(\mathit{minNodeF}\) becomes a leaf of \(F\). Otherwise, \(F\) must be updated by making \(\mathit{minNodeF}\) a parent of the trees of \(F\) that are part of the strongly connected component. Algorithm 3 details this updating of forest \(F\). ```
Create the node \(\mathit{minNodeF}\) in forest \(F\) associated with the edge \((u,r)\) if\(\mathit{cycleEdgeNode}[r]=\emptyset\)then \(\pi[r]\leftarrow\mathit{minNodeF}\) else for each \(n\in\mathit{cycleEdgeNode}[r]\)do \(\textsc{PARENT}(n)\leftarrow\mathit{minNodeF}\) \(\textsc{CHILDREN}(\mathit{minNodeF})\leftarrow\textsc{CHILDREN}(\mathit{minNodeF}) \cup\{n\}\) endfor endif
```  
**Algorithm 3** Continuation of the main loop body of the contraction phase. The next step is to verify if \((u,r)\) forms a cycle with the minimum weight edges formerly selected. It is enough to check if \((u,r)\) connects the vertices in the same weakly connected components. Note that \((u,r)\) is incident on a root and, if \(u\) lies in the same weakly connected component as \(r\), then adding \((u,r)\) necessarily forms a cycle. Assuming that adding \((u,r)\) does not form a cycle, we perform the union of the sets representing the two weakly connected components to which \(u\) and \(r\) belong, i.e., \(\textsc{WUNION}(u,r)\). We also update the \(\mathit{inEdgeNode}[r]\) array, as \(r\) now has an incident edge selected. If adding \((u,r)\) forms a cycle, a contraction is performed. The contraction procedure starts firstly by finding the edges involved in the cycle by using a backward depth-first search. During this process, a \(map\) is initialized, where the edge is associated to its \(F\) node (the map key). Then the maximum weight edge in the cycle is found, the reduced costs are computed, and the weight of the edges is updated. Note that the min-heap property is always maintained when reducing the costs without running any kind of procedure to ensure it, since the constant \(reduced\) is added to every edge in a given priority queue. The arrays \(\mathit{inEdgeNode}\) and \(\mathit{cycleEdgeNode}\) are updated, and the heaps involved in the cycle are merged. See Algorithm 4 for detailed pseudocode. ```
if\(\texttt{WFIND}(u)\
eq\texttt{WFIND}(r)\)then \(inEdgeNode[r]\gets minNodeF\) \(\texttt{WUNION}(u,r)\) else \(inEdgeNode[r]\gets null\) \(cycle\leftarrow\{minNodeF\}\) \(\texttt{Let}\ nmap\) denote a map.