A Multi-Threading Algorithm to Detect and Remove Cycles in Vertex- and Arc-Weighted Digraph
<p>An example of debt graph. (<b>a</b>) A debt graph; (<b>b</b>) legend.</p> "> Figure 2
<p>An example of key-vale pair table.</p> "> Figure 3
<p>Impacts of number of vertices on execution time of each algorithm.</p> "> Figure 4
<p>Impacts of average degree of vertices on execution time of each algorithm.</p> "> Figure 5
<p><math display="inline"> <semantics> <mrow> <msub> <mi>R</mi> <mn>3</mn> </msub> </mrow> </semantics> </math> and <math display="inline"> <semantics> <mrow> <msub> <mi>R</mi> <mn>4</mn> </msub> </mrow> </semantics> </math> under different out-degree.</p> "> Figure 6
<p>Ratio of number of residual vertices and arcs after simplification.</p> "> Figure 7
<p>A real debt graph after simplification.</p> "> Figure 8
<p>Execution time of four algorithms.</p> "> Figure 9
<p>Execution time of different algorithms on different CPU.</p> ">
Abstract
:1. Introduction
- It defines a new problem of detecting and removing cycles in a vertex- and arc-weighted digraph according to vertices’ priority.
- It presents a multi-threading parallel and iterative algorithm to solve the problem. The algorithm avoids the out-of-memory exception by simplification and iteration, and it leverages the advantage of multicore computers by multithreading parallelism.
- It performs thorough experiments to show the performance of the proposed algorithm.
2. Related Work
3. Problem Statements
- 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.
4. Cycle Detection and Removal with Vertex Priority
Algorithm 1. Detect and Remove Cycles of a Weighted Digraph |
Step1: Simplify . |
Step2: Divide into strongly connected components. |
Step3: Detect, output and remove cycles of each strongly connected component. |
4.1. Graph Simplification
Algorithm 2. Simplify a Weighted Digraph | |
1. | Function Simplify() |
2. | for all do |
3. | in degree of |
4. | out degree of |
5. | end for |
6. | |
7. | while do |
8. | |
9. | for to do |
10. | if then |
11. | |
12. | break |
13. | end if |
14. | end for |
15. | if then |
16. | Delete() |
17. | end if |
18. | end while |
19. | return |
20. | end function |
Algorithm 3. Delete a Vertex from a Weighted Digraph | |
1. | Function Delete(, ) |
2. | for all do |
3. | |
4. | |
5. | end for |
6. | for all do |
7. | |
8. | |
9. | end for |
10. | |
11. | end function |
4.2. Cycle Detection
- Push() to push into .
- Pop() to pop an element of .
- Peek() to return the top element of without popping out it.
- Search() to return the index of in , and it returns −1 if is not in .
- Clear() to clear the to empty.
- SubList() to return the sub-sequence of from index to ().
- IsEmpty() to return false if is not empty, and return true if is empty.
- Clear() to reset all values of key to 0.
- Sum() to return the sum of values of key . The sum represents the number of neighboring vertices have been visited until now.
- GetFirst() to return the first unvisited neighboring vertex of .
- Set() to set the value of neighboring vertex of to 1.
Algorithm 4. Detect Cycles of a Weighted Directed Graph | |
1. | Function DetectCycle() |
2. | Fork K threads |
3. | |
4. | for each thread do in parallel |
5. | the next SCC to detect and remove cycle |
6. | Fun() |
7. | end for |
8. | return |
9. | end function |
10. | Function Fun() // is a SCC of , is in heap H |
11. | |
12. | while do |
13. | GetFirst(H) |
14. | Clear() |
15. | Clear() |
16. | Push() |
17. | flag false |
18. | while (flag=false and isEmpty()=false) |
19. | Peek() |
20. | if |sum| then |
21. | Pop() |
22. | Clear() |
23. | else |
24. | GetFirst() |
25. | Set() |
26. | k=Search() |
27. | if then |
28. | Push() |
29. | else if then |
30. | SubList()// is a cycle |
31. | |
32. | RemoveCycle(,) |
33. | flag true |
34. | end if |
35. | end if |
36. | end while |
37. | if flag=false then |
38. | Delete() |
39. | end if |
40. | end while |
41. | return |
42. | end function |
Algorithm 5. Remove a Cycle | |
1. | Function RemoveCycle(,)//, |
2. | |
3. | for to do |
4. | if then |
5. | |
6. | end if |
7. | end for |
8. | for to do |
9. | |
10. | |
11. | if then |
12. | |
13. | if then |
14. | Delete() |
15. | end if |
16. | if then |
17. | Delete() |
18. | end if |
19. | end if |
20. | end for |
21. | end function |
4.3. Time Complexity Analysis
4.4. An Example
5. Experiments and Analysis
- Recursion without simplification (RWOS). It detects cycle recursively without simplification. It is the popular algorithm used by many literatures.
- Recursion with simplification (RWS). It detects cycle recursively after simplification.
- Iteration without simplification (IWOS). It detects cycle iteratively without simplification.
- Iteration with simplification (IWS). It detects cycle iteratively after simplification.
- Multi-thread parallel IWS (MPIWS). It detects cycle in parallel with IWS using multi-threads.
5.1. Experiments with Randomly Generated Digraphs
5.2. Experiments with SNAP Datasets
5.3. Experiments with Real Dept Graphs
5.4. Performance Comparisons on Different Computers
6. Conclusion and Discussion
Acknowledgments
Author Contributions
Conflicts of Interest
References
- Kühn, D.; Osthus, D. A survey on hamilton cycles in directed graphs. Eur. J. Combin. 2012, 33, 750–766. [Google Scholar] [CrossRef]
- Silva, J.L.C.; Rocha, L.; Silva, B.C.H. A new algorithm for finding all tours and hamiltonian circuits in graphs. IEEE Lat. Am. Trans. 2016, 14, 831–836. [Google Scholar] [CrossRef]
- Lv, X.; Zhu, D. An approximation algorithm for the shortest cycle in an undirected unweighted graph. In Proceedings of the International Conference on Computer, Mechatronics, Control and Electronic Engineering, Changchun, China, 24–26 August 2010; IEEE: New York, NY, USA, 2010; pp. 297–300. [Google Scholar]
- Yuster, R. A shortest cycle for each vertex of a graph. Inform. Process. Lett. 2011, 111, 1057–1061. [Google Scholar] [CrossRef]
- Paulusma, D.; Yoshimoto, K. Cycles through specified vertices in triangle-free graphs. Discuss. Math. Gr. Theory 2007, 27, 179–191. [Google Scholar] [CrossRef]
- Li, B.; Zhang, S. Heavy subgraph conditions for longest cycles to be heavy in graphs. Discuss. Math. Gr. Theory 2016, 36, 383–392. [Google Scholar] [CrossRef]
- Li, B.; Xiong, L.; Yin, J. Large degree vertices in longest cycles of graphs, I. Discuss. Math. Gr. Theory 2016, 36, 363–382. [Google Scholar] [CrossRef]
- Gerbner, D.; Keszegh, B.; Palmer, C.; Patkos, B. On the Number of Cycles in a Graph with Restricted Cycle Lengths. Available online: https://arxiv.org/abs/1610.03476 (accessed on 9 October 2017).
- Sankar, K.A.; Sarad, V. A time and memory efficient way to enumerate cycles in a graph. In Proceedings of the International Conference on Intelligent and Advanced Systems, Kuala Lumpur, Malaysia, 25–28 November 2007; IEEE: New York, NY, USA, 2007; pp. 498–500. [Google Scholar]
- Haeupler, B.; Kavitha, T.; Mathew, R.; Sen, S.; Tarjan, R.E. Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance. Available online: https://arxiv.org/abs/1105.2397 (accessed on 9 October 2017).
- Bender, M.A.; Fineman, J.T.; Gilbert, S.; Tarjan, R.E. A new approach to incremental cycle detection and related problems. ACM Trans. Algorithms 2016, 12. [Google Scholar] [CrossRef]
- Reif, J.H. Depth-first search is inherently sequential. Inform. Process. Lett. 1985, 20, 229–234. [Google Scholar] [CrossRef]
- Karimi, M.; Banihashemi, A.H. Message-passing algorithms for counting short cycles in a graph. IEEE Trans. Commun. 2013, 61, 485–495. [Google Scholar] [CrossRef]
- Rocha, R.C.; Thatte, B.D. Distributed cycle detection in large-scale sparse graphs. In Proceedings of the Simpósio Brasileiro de Pesquisa Operacional, Pernambuco, Brazil, 25–28 August 2015; XLVII SBPO: Pernambuco, Brazil, 2015; pp. 1–11. [Google Scholar]
- Malewicz, G.; Austern, M.H.; Bik, A.J.C.; Dehnert, J.C.; Horn, I.; Leiser, N.; Czajkowski, G. Pregel: A system for large-scale graph processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Indianapolis, IN, USA, 6–11 June 2010; ACM: New York, NY, USA, 2010; pp. 135–146. [Google Scholar]
- Gonzalez, J.E.; Xin, R.S.; Dave, A.; Crankshaw, D.; Franklin, M.J.; Stoica, I. GraphX: Graph processing in a distributed dataflow framework. In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation, Broomfield, CO, USA, 6–8 October 2014; USENIX: Berkeley, CA, USA, 2014; pp. 599–613. [Google Scholar]
- Salihoglu, S.; Widom, J. GPS: A graph processing system. In Proceedings of the 25th International Conference on Scientific and Statistical Database Management, Baltimore, MD, USA, 29–31 July 2013; ACM: New York, NY, USA, 2013; pp. 1–31. [Google Scholar]
- Féray, V. Weighted dependency graphs. Available online: https://arxiv.org/abs/1605.03836 (accessed on 9 October 2017).
- McLendon, W.; Hendrickson, B.; Plimpton, S.J.; Rauchwerger, L. Finding strongly connected components in distributed graphs. J. Parallel Distrib. Comput. 2005, 65, 901–910. [Google Scholar] [CrossRef]
- Leskovec, J.; Sosic, R. SNAP: A general-purpose network analysis and graph-mining library. ACM Trans. Intell. Syst. Technol. 2016, 8. [Google Scholar] [CrossRef] [PubMed]
- Seidl, T.; Boden, B.; Fries, S. CC-MR—Finding connected components in huge graphs with MapReduce. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Bristol, UK, 24–28 September 2012; Springer: Berlin/Heidelberg, Germany, 2014; pp. 458–473. [Google Scholar]
- Slota, G.M.; Rajamanickam, S.; Madduri, K. BFS and coloring-based parallel algorithms for strongly connected components and related problems. In Proceedings of the IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, AZ, USA, 19–23 May 2014; IEEE: New York, NY, USA, 2014; pp. 550–559. [Google Scholar]
Graph Name | p2p-Gnutella04 | p2p-Gnutella25 | p2p-Gnutella30 | p2p-Gnutella31 | Email-EuAll | Web-NotreDame | Wiki-Talk |
---|---|---|---|---|---|---|---|
10,876 | 22,687 | 36,682 | 62,586 | 265,214 | 325,729 | 2,394,385 | |
39,994 | 54,705 | 88,328 | 147,892 | 420,045 | 1,497,134 | 5,021,410 | |
ratio 1 | 54.80% | 74.06% | 74.12% | 74.29% | 95.79% | 57.65% | 94.88% |
Graph Name | p2p-Gnutella04 | p2p-Gnutella25 | p2p-Gnutella30 | p2p-Gnutella31 | email-EuAll | Web-NotreDame | Wiki-Talk |
---|---|---|---|---|---|---|---|
355.5179 | 615.3466 | - | - | - | - | - | |
315.4235 | 592.1235 | 1804.2942 | 2181.8719 | 4788.6087 | 6075.5061 | 7560.0935 | |
147.0574 | 342.7287 | 891.0342 | 1238.7748 | 2798.9455 | 3680.5876 | 4907.7557 | |
0.4662 | 0.5788 | 0.4938 | 0.5678 | 0.5845 | 0.6058 | 0.6492 |
© 2017 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Cui, H.; Niu, J.; Zhou, C.; Shu, M. A Multi-Threading Algorithm to Detect and Remove Cycles in Vertex- and Arc-Weighted Digraph. Algorithms 2017, 10, 115. https://doi.org/10.3390/a10040115
Cui H, Niu J, Zhou C, Shu M. A Multi-Threading Algorithm to Detect and Remove Cycles in Vertex- and Arc-Weighted Digraph. Algorithms. 2017; 10(4):115. https://doi.org/10.3390/a10040115
Chicago/Turabian StyleCui, Huanqing, Jian Niu, Chuanai Zhou, and Minglei Shu. 2017. "A Multi-Threading Algorithm to Detect and Remove Cycles in Vertex- and Arc-Weighted Digraph" Algorithms 10, no. 4: 115. https://doi.org/10.3390/a10040115