×

A multi-threading algorithm to detect and remove cycles in vertex- and arc-weighted digraph. (English) Zbl 1461.05207

Summary: A graph is a very important structure to describe many applications in the real world. In many applications, such as dependency graphs and debt graphs, it is an important problem to find and remove cycles to make these graphs be cycle-free. The common algorithm often leads to an out-of-memory exception in commodity personal computer, and it cannot leverage the advantage of multicore computers. This paper introduces a new problem, cycle detection and removal with vertex priority. It proposes a multithreading iterative algorithm to solve this problem for large-scale graphs on personal computers. The algorithm includes three main steps: simplification to decrease the scale of graph, calculation of strongly connected components, and cycle detection and removal according to a pre-defined priority in parallel. This algorithm avoids the out-of-memory exception by simplification and iteration, and it leverages the advantage of multicore computers by multithreading parallelism. Five different versions of the proposed algorithm are compared by experiments, and the results show that the parallel iterative algorithm outperforms the others, and simplification can effectively improve the algorithm’s performance.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles

Software:

GraphX; GPS; Pregel; SNAP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kühn, D.; Osthus, D.; A survey on hamilton cycles in directed graphs; Eur. J. Combin.: 2012; Volume 33 ,750-766. · Zbl 1239.05114
[2] 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; Volume 14 ,831-836.
[3] Lv, X.; Zhu, D.; An approximation algorithm for the shortest cycle in an undirected unweighted graph; Proceedings of the International Conference on Computer, Mechatronics, Control and Electronic Engineering: New York, NY, USA 2010; ,297-300.
[4] Yuster, R.; A shortest cycle for each vertex of a graph; Inform. Process. Lett.: 2011; Volume 111 ,1057-1061. · Zbl 1260.05083
[5] Paulusma, D.; Yoshimoto, K.; Cycles through specified vertices in triangle-free graphs; Discuss. Math. Gr. Theory: 2007; Volume 27 ,179-191. · Zbl 1134.05043
[6] Li, B.; Zhang, S.; Heavy subgraph conditions for longest cycles to be heavy in graphs; Discuss. Math. Gr. Theory: 2016; Volume 36 ,383-392. · Zbl 1338.05151
[7] Li, B.; Xiong, L.; Yin, J.; Large degree vertices in longest cycles of graphs, I; Discuss. Math. Gr. Theory: 2016; Volume 36 ,363-382. · Zbl 1338.05136
[8] Gerbner, D.; Keszegh, B.; Palmer, C.; Patkos, B.; On the Number of Cycles in a Graph with Restricted Cycle Lengths; ; . · Zbl 1379.05058
[9] Sankar, K.A.; Sarad, V.; A time and memory efficient way to enumerate cycles in a graph; Proceedings of the International Conference on Intelligent and Advanced Systems: New York, NY, USA 2007; ,498-500.
[10] Haeupler, B.; Kavitha, T.; Mathew, R.; Sen, S.; Tarjan, R.E.; Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance; ; . · Zbl 1295.05234
[11] 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; Volume 12 . · Zbl 1398.68386
[12] Reif, J.H.; Depth-first search is inherently sequential; Inform. Process. Lett.: 1985; Volume 20 ,229-234. · Zbl 0572.68051
[13] Karimi, M.; Banihashemi, A.H.; Message-passing algorithms for counting short cycles in a graph; IEEE Trans. Commun.: 2013; Volume 61 ,485-495.
[14] Rocha, R.C.; Thatte, B.D.; Distributed cycle detection in large-scale sparse graphs; Proceedings of the Simpósio Brasileiro de Pesquisa Operacional: Pernambuco, Brazil 2015; ,1-11.
[15] 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; Proceedings of the ACM SIGMOD International Conference on Management of Data: New York, NY, USA 2010; ,135-146.
[16] Gonzalez, J.E.; Xin, R.S.; Dave, A.; Crankshaw, D.; Franklin, M.J.; Stoica, I.; GraphX: Graph processing in a distributed dataflow framework; Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation: Berkeley, CA, USA 2014; ,599-613.
[17] Salihoglu, S.; Widom, J.; GPS: A graph processing system; Proceedings of the 25th International Conference on Scientific and Statistical Database Management: New York, NY, USA 2013; ,1-31.
[18] Féray, V.; Weighted dependency graphs; ; . · Zbl 1414.60014
[19] McLendon, W.; Hendrickson, B.; Plimpton, S.J.; Rauchwerger, L.; Finding strongly connected components in distributed graphs; J. Parallel Distrib. Comput.: 2005; Volume 65 ,901-910. · Zbl 1082.68086
[20] Leskovec, J.; Sosic, R.; SNAP: A general-purpose network analysis and graph-mining library; ACM Trans. Intell. Syst. Technol.: 2016; Volume 8 .
[21] Seidl, T.; Boden, B.; Fries, S.; CC-MR—Finding connected components in huge graphs with MapReduce; Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases: Berlin/Heidelberg, Germany 2014; ,458-473.
[22] Slota, G.M.; Rajamanickam, S.; Madduri, K.; BFS and coloring-based parallel algorithms for strongly connected components and related problems; Proceedings of the IEEE 28th International Parallel and Distributed Processing Symposium: New York, NY, USA 2014; ,550-559.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.