# A Multi-Threading Algorithm to Detect and Remove Cycles in Vertex- and Arc-Weighted Digraph
## 4 Cycle Detection and Removal with Vertex Priority
### Cycle Detection
```
1 FunctionDetectCycle(G)
2 Fork \(K\) threads
3 SC\(\leftarrow\Phi\)
4 for each thread do in parallel
5\(\mathbf{G}^{\text{SCC}}\leftarrow\text{ the next SCC to detect and remove cycle
6\(\mathbf{SC}\leftarrow\mathbf{SC}\cup\text{ Fun}(\mathbf{G}^{\text{SCC}})\)
7 endfor
8 returnSC
9 endfunction
10 FunctionFun(G\({}^{\text{SCC}}\))//G\({}^{\text{SCC}}=\{\mathbf{V}^{\text{SCC}},\mathbf{E}^{\text{SCC}},\mathbf{W}^{\text{SCC}},\mathbf{P}^{\text{SCC}}\}\) is a SCC of G, \(\mathbf{V}^{\text{SCC}}\) is in heap \(H\)
11 SSC\(\leftarrow\Phi\)
12 while\(\mathbf{V}^{\text{SCC}}\
eq\Phi\)do
13\(u\leftarrow\textsc{GetFirst}(H)\)
14 Clear(\(S\))
15 Clear(\(T,u\))
16 Push(\(S,u\))
17 flag\(\leftarrow\)false
18 while(flag=false and isEmpty(\(S\))=false)
19\(v\leftarrow\textsc{Peek}(S)\)
20 if\(\mid\)sum(\(T,v\))\(\mid=d_{v}^{\text{out}}\)then
21 Pop(S)
22 Clear(\(T,\,v\))
23 else
24\(r\leftarrow\textsc{GetFirst}(T,v)\)
25 Set(\(T,v,r\))
26\(k\)=Search(\(S,r\))
27 if\(k=-1\)then
28 Push(\(S,r\))
29 elseif\(r=u\)then
30C\(\leftarrow\textsc{SubList}(S,k,\mid\mid\mid\mid)//\mathbf{C}\) is a cycle
31 SSC\(\leftarrow\textsc{SSC}\cup\{\mathbf{C}\}\)
32 RemoveCycle(G\({}^{\text{SCC}}\),\(\mathbf{C}\))
33 flag\(\leftarrow\)true
34 endif
35 endif
36 endwhile
37 if flag=false then
38 Delete(G\({}^{\text{SCC}}\),\(u\))
39 endif
40 endwhile
41 returnSSC
42 endfunction
```  
**Algorithm 4**DetectCycle of a Weighted Directed GraphWhen a cycle is detected, it should be removed at once using RemoveCycle (line 32) shown in Algorithm 5. The first _for_ loop (lines 3-7) finds the cycle weight. The second _for_ loop (lines 8-20) decreases all of the arc weights of \(\mathbf{C}\) by \(w_{\mathbf{C}}\). If the weight of an arc becomes 0, delete this arc (line 11). In further, if the in-degree or out-degree of a vertex becomes 0, delete this vertex (lines 13 and 16). ```
1 FunctionRemoveCycle(\(\mathbf{G}^{\text{SCC}}\), \(\mathbf{C}\))//\(\mathbf{G}^{\text{SCC}}=\{\mathbf{V}^{\text{SCC}},\mathbf{E}^{\text{SCC}}, \mathbf{W}^{\text{SCC}},\mathbf{P}^{\text{SCC}}\}\), \(\mathbf{C}=\{v_{1},v_{2},\cdots,v_{k}\}\)
2\(w_{\mathbf{C}}\gets w_{k,1}\)
3 for i \(\gets 1\) to \(k-1\)do
4 if\(w_{i,j+1}<w_{\mathbf{C}}\)then
5\(w_{\mathbf{C}}\gets w_{i,j+1}\)
6 endif
7 endfor
8 for i \(\gets 1\) to \(k\)do
9\(j\gets 1+(i\bmod k)\)
10\(w_{i,j}\gets w_{i,j}-w_{\mathbf{C}}\)
11 if\(w_{i,j}\) = 0 then
12\(\mathbf{E}^{\text{SCC}}\leftarrow\mathbf{E}^{\text{SCC}}-\{v_{i},v_{j}\}\)
13 if\(d_{i}^{out}=0\)then
14\(\textsc{Delete}(\mathbf{G}^{\text{SCC}},v_{i})\)
15 endif
16 if\(d_{i}^{out}=0\)then
17\(\textsc{Delete}(\mathbf{G}^{\text{SCC}},v_{j})\)
18 endif
19 endif
20 endfor
21 endfunction
```  
**Algorithm 5**Remove a Cycle  
**Proposition 3**. : _Given a strongly connected component \(\mathbf{G}^{\text{SCC}}=\{\mathbf{V}^{\text{SCC}},\mathbf{E}^{\text{SCC}}, \mathbf{W}^{\text{SCC}},\mathbf{P}^{\text{SCC}}\}\), Algorithm 4 can terminate with \(\mathbf{V}^{\text{SCC}}=\Phi\)._  
Let \(u\) be the vertex with the highest priority in SCC \(\mathbf{G}^{\text{SCC}}\), i.e., \(p_{u}\) is the minimal. From \(u\), DFS is used to visit this SCC. Let \(v\) be the current visiting vertex. Case 1. \(v\) has no outgoing arc or all its neighbor vertices are visited in previous steps. In this case, \(|\text{Sum}(T,v)|=d_{v}^{out}\), and \(v\) should be popped out from \(S\). Case 1-1. If \(v=u\), \(S\) becomes empty, so the inner _while_ (line 18) exits and _flag_=**false**. This result means no cycle can be detected from \(u\), so \(u\) is deleted (line 38). Case 1-2. If \(v\
eq u\), the inner _while_ (line 18) goes on checking the top element of \(S\). Case 2. \(v\) has at least one unvisited outgoing arc. In this case, we select one unvisited neighbor vertex \(r\) to continue searching. Figure 2: An example of key-vale pair table. Case 2-1. If \(r=u\), a cycle \(\mathbf{C}\) is detected (line 29). This cycle is removed by Algorithm 5. Because \(w_{\mathbb{C}}\) equals to at least one arc's weight, Algorithm 5 deletes at least one arc.