# A Multi-Threading Algorithm to Detect and Remove Cycles in Vertex- and Arc-Weighted Digraph
## 3 Problem Statements  
A digraph or directed graph \(\mathbf{G}\) consists of a finite set of vertices \(\mathbf{V}=\{v_{1},v_{2},\cdots\}\), and a set of directed arcs \(\mathbf{E}=\{\langle v_{i},v_{j}\rangle|v_{i}\in\mathbf{V},v_{j}\in\mathbf{V}, i\
eq j\}\) that each connects an ordered pair of vertices. Each arc \(\langle v_{i},v_{j}\rangle\in\mathbf{E}\) is associated with a numerical weight \(w_{ij}\). Each vertex \(v_{i}\) is also associated with an integer priority \(p_{i}\), and for any \(i\
eq j\), \(p_{i}\
eq p_{j}\). We denote the set of arc weights and vertex priorities by \(\mathbf{W}\) and \(\mathbf{P}\), respectively. Given \(\langle v_{i},v_{j}\rangle\in\mathbf{E}\), \(v_{i}\) is called the tail, and \(v_{j}\) is called the head of the arc. For a vertex \(v_{i}\), the number of head ends adjacent to \(v_{i}\) is called its in-degree, and the number of tail ends adjacent to \(v_{i}\) is its out-degree. In a digraph, a directed path is a sequence of vertices in which there is an arc pointing from each vertex in the sequence to its successor in the sequence. _A simple directed cycle_ is a directed path where the first and last vertices are the same, and there are no repeated arcs or vertices (except the requisite repetition of the first and last vertices). Let \(\mathbf{C}=\{v_{1},v_{2},\cdots,v_{k},v_{1}\}\) be a simple directed cycle, we define _its cycle weight_\(w_{C}\) as  
\[w_{C}=min\{w_{ij}\big{|}\langle v_{i},v_{j}\rangle\in\mathbf{C}\,\}. \tag{1}\]  
The problem of detecting cycles in such a vertex- and arc-weighted digraph is defined as follows. Given a digraph \(\mathbf{G}=(\mathbf{V},\mathbf{E},\mathbf{W},\mathbf{P})\), the vertex  
\[v_{beg}=\operatorname*{argmin}_{v_{i}\in\mathbf{V}}\{\,p_{i}|p_{i}\in\mathbf{ P}\,\}, \tag{2}\]  
is chosen as the beginning vertex to detect cycle. \"argmin\" gets the vertex with the minimal weight. Suppose \(v_{cur}\) is the current visiting vertex, the next vertex to visit should be  
\[v_{next}=\operatorname*{argmin}_{v_{cur},\,v_{i}\in\mathbf{E}}\{\,p_{i}|p_{i} \in\mathbf{P}\,\}. \tag{3}\]  
Once \(v_{beg}\) is visited again, a cycle \(\mathbf{C}_{beg}\) is detected whose first and last vertices are both \(v_{beg}\). Next, this cycle's weight \(w_{C_{beg}}\) is calculated by Equation (1). Finally, \(\mathbf{C}_{beg}\) is removed by subtracting \(w_{C_{beg}}\) from all arcs of this cycle, so that the arcs of weight \(w_{C_{beg}}\) are deleted from \(\mathbf{G}\). Repeat this procedure until there are no cycles in \(\mathbf{G}\). The characteristics of this problem are:  
* The cycles are detected according to the vertex priority. The first and last vertices of the cycle should be the vertexes of minimal priority, and the next vertex to visit from current one should be the one with minimal priority in all of the direct successors. * The cycles are removed according to the arc weight. The arcs with cycle weight are deleted to destroy the cycle. This problem stems from removing the dependency chain in weighted dependency graph [18] and debt chain in financial field. Taking debt chain as an example, the debt relationship among enterprises can be formulated as a weighted digraph, as defined above. In a graph \(\mathbf{G}\), (1) each vertex \(v\in\mathbf{V}\) stands for an enterprise; (2) each arc \(\langle v_{i},v_{j}\rangle\in\mathbf{E}\) stands for a debt relationship between corresponding enterprises and means \(v_{i}\) owes \(v_{j}\); (3) \(w_{ij}\) associated with \(\langle v_{i},v_{j}\rangle\) is the amount of debt of corresponding enterprises; and, (4) \(p_{i}\) of vertex \(v_{i}\) represents the importance of the corresponding enterprises, and the smaller \(p_{i}\) has the higher priority. This kind of digraph is called a debt graph for convenience. Figure 1 illustrates an example including 12 enterprises. Debt cycle is a simple directed cycle in a given debt graph. It is very useful to solve the debt problem, because the enterprises belonging to a debt cycle can solve their debts without transferring capital. Figure 1: An example of debt graph.