求解大规模稀疏有向图回路的多线程并行算法

Multithreading Parallel Algorithm for Solving Circuits of Large-scale Sparse Directed Graphs

传统的基于深度优先遍历的回路求解算法限于计算机内存无法对大规模图进行求解,而已有的分布式图计算系统需要借助计算机集群,成本较高。针对此问题,给出一种可在普通计算机上求解大规模有向图所有回路的多线程并行算法。该算法根据顶点的出度,首先删除出度为0的顶点,然后采用多线程并行求解包含出度较大的顶点的回路,最后使用串行算法求出图剩余部分的回路。实验表明,此算法能够在普通计算机上求得大规模有向稀疏图的所有回路。

To solve the incapability of traditional circuit algorithms based on depth-first traversal in solving the largescale graph due to the limited memory and the high cost of the existing distributed graph computing platforms with the help of computer cluster,this paper presented a multithreading parallel algorithm for solving circuits of largescale sparse directed graphs which could be conducted on ordinary personal computers.According to the out-degree of vertices,the algorithm first deleted the vertices with the out-degree of 0,then solved the circuits containing the vertices with larger out-degree by using multithreading paralell algorithm,and finally computed the residual graph＇s circuits by using serial algorithm.Experiment results show that the proposed algorithm can solve all circuits of a large-scale sparse graph on an ordinary computer.