公开(公告)号：CN110288507B

公开(公告)日：2021-03-09

申请号：CN201910371230.1

申请日：2019-05-06

Applicant: 中国科学院信息工程研究所

Inventor： 侯骏腾 ,  王树鹏 ,  吴广君 ,  王振宇 ,  张建宇

IPC: G06T1/20 ,  G06F16/901

Abstract: 本发明提出一种基于GPU的多分区强连通图检测方法，包括以下步骤：加载图数据并统一存储格式；在图数据上基于GPU进行第一剪枝操作，检测出1‑SCC；在除1‑SCC外的部分上选取中心点，从中心点开始并行地前向和后向遍历，更新状态得到SCC和多个分区；在未被检测的图数据上基于GPU进行第二剪枝操作，检测出2‑SCC；在未被检测的图数据上检测弱连通区域，并在弱连通区域上每个选取中心点，从中心点开始前向遍历；在弱连通区域的中未被前向遍历到的区域随机选取保存的最后一个顶点做为副中心点，从中心点与副中心点开始后向遍历，再进行第一剪枝操作，再次更新状态得到SCC和分区；通过上述步骤获得全部的SCC。

公开(公告)号：CN110288507A

公开(公告)日：2019-09-27

申请号：CN201910371230.1

申请日：2019-05-06

Applicant: 中国科学院信息工程研究所

Inventor： 侯骏腾 ,  王树鹏 ,  吴广君 ,  王振宇 ,  张建宇

IPC: G06T1/20 ,  G06F16/901

Abstract: 本发明提出一种基于GPU的多分区强连通图检测方法，包括以下步骤：加载图数据并统一存储格式；在图数据上基于GPU进行第一剪枝操作，检测出1-SCC；在除1-SCC外的部分上选取中心点，从中心点开始并行地前向和后向遍历，更新状态得到SCC和多个分区；在未被检测的图数据上基于GPU进行第二剪枝操作，检测出2-SCC；在未被检测的图数据上检测弱连通区域，并在弱连通区域上每个选取中心点，从中心点开始前向遍历；在弱连通区域的中未被前向遍历到的区域随机选取保存的最后一个顶点做为副中心点，从中心点与副中心点开始后向遍历，再进行第一剪枝操作，再次更新状态得到SCC和分区；通过上述步骤获得全部的SCC。