# 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  
**Proposition 2**. : _Given a digraph \(\mathbf{G}=\{\mathbf{V},\mathbf{E},\mathbf{W},\mathbf{P}\}\), if \(\{v_{1},v_{2},\cdots,v_{k},v_{1}\}\) is a directed cycle, then these vertices belong to the same strongly connected components of \(\mathbf{G}\)._  
This is the basis of step 2 of Algorithm 1. There are several efficient algorithms to calculate strongly connected components (SCCs) of a digraph, so we do not discuss the detail of step 2 of Algorithm 1. After SCCs are obtained, the cycles can be detected in each SCC. The cycle calculation is the core of Algorithm 1. Because the problem needs visit the vertices according their priorities, cycle should be detected using DFS. For large-scale graphs, the recursive DFS will cause out-of-memory exception, so we need an iterative version. The following data structures are adopted. Stack \(S\) is used to store the visited sequence of vertices. Its interfaces include:  
* \(\texttt{Push}(S,v)\) to push \(v\) into \(S\). * \(\texttt{Pop}(S)\) to pop an element of \(S\). * \(\texttt{Peek}(S)\) to return the top element of \(S\) without popping out it. * \(\texttt{Search}(S,\ v)\) to return the index of \(v\) in \(S\), and it returns \(-1\) if \(v\) is not in \(S\). * \(\texttt{Clear}(S)\) to clear the \(S\) to empty. * \(\texttt{SubList}(S,m,n)\) to return the sub-sequence of \(S\) from index \(m\) to \(n\) (\(m\leq n\)). * \(\texttt{IsEmpty}(S)\) to return **false** if \(S\) is not empty, and return **true** if \(S\) is empty. Key-value pair table \(T\) is applied to record each neighbor vertex of a visited vertex is visited or not. As shown in Figure 2, each key (\(v_{i},i=1,2,\cdots,n\)) is a vertex that is unique in the whole table. Each \(v_{i}\) has a list of values, and each value is either 0 or 1 representing the corresponding neighboring vertex of \(v_{i}\) is unvisited or not. It has the following interfaces:  
* \(\texttt{Clear}(T,\ v)\) to reset all values of key \(v\) to 0. * \(\texttt{Sum}(T,\ v)\) to return the sum of values of key \(v\). The sum represents the number of neighboring vertices have been visited until now. * \(\texttt{GetFirst}(T,\ v)\) to return the first unvisited neighboring vertex of \(v\). * \(\texttt{Set}(T,\ v,u)\) to set the value of neighboring vertex \(u\) of \(v\) to 1. Minimum heap \(H\) is applied to store vertices based on their priorities, due to the high-efficiency of sorting and deleting members in heap. It only has one function, \(\texttt{GetFirst}(H)\), to get the vertex of the highest priority. Algorithm 4 gives the cycle detection algorithm. It is a multi-threading parallel algorithm. Line 2 forks threads, and all of the threads run in parallel (line 4). Each thread gets an SCC (line 5), and calls Fun to detect and remove cycles (line 6). The set of vertices \(\mathbf{V}^{\text{SCC}}\) is stored in a minimum heap \(H\). The outer _while_ loop (lines 12-40) detects cycles starting from each vertex of \(\mathbf{V}^{\text{SCC}}\). Lines 13-17 initialize variables. For a given vertex, \(u\), the inner _while_ loop (lines 18-36) detects all of the cycles including \(u\). Let \(v\) be the top element of \(S\). If all its neighbor vertices are visited (line 20), pop it out and clear the status of all its neighbor vertices. Otherwise, get the first unvisited neighbor vertex \(r\) of \(v\) and visit it. In further, if \(r\) is not in \(S\) (line 27), \(r\) is pushed into \(S\). If \(r\) is in \(S\) and \(r=u\) (line 29), than the sub-list of \(S\) from \(r\) to the top element is a cycle. If \(u\) cannot find any cycle, delete it from graph (line 38).