1.一种银行交易资金回流多线程并行检测方法,其特征在于,包括:根据银行交易记录构建有向图及其邻接表存储结构,并增加一个虚拟顶点来指向有向图中每一个顶点;
所述根据银行交易记录构建有向图及其邻接表存储结构,并增加一个虚拟顶点来指向有向图中每一个顶点,具体包括:获取银行交易记录;所述银行交易记录中包括多条交易流水;
将每一条交易流水对应一条有向边,资金转出账户作为起始顶点,资金转入账户作为终止顶点,构建出银行交易记录的有向图;
为所述有向图中的每个顶点 构建对应的邻接表来存放该顶点 指向的所有邻接点;
在所述有向图中增加一个虚拟顶点 ,所述虚拟顶点 的邻接表中的邻接点为所述有向图中的所有顶点;
基于所述有向图创建线程间共享内存数据结构,定义并初始化线程内局部数据结构;
所述基于所述有向图创建线程间共享内存数据结构,定义并初始化线程内局部数据结构,具体包括:针对所述有向图中的每个顶点 创建三个线程间共享内存数据结构,分别为状态集合status(v)、线程集合thread(v)以及环路集合circle(v);其中状态集合status(v)用于记录该顶点 的状态,线程集合thread(v)用于记录该顶点 当前所在的线程集合,环路集合circle(v)用于记录该顶点 当前所处的环路集合;
每个顶点在环路求解过程中共区分三个状态,使用状态集合status(v)进行记录:顶点未访问过,标记为unvisited;顶点 已完全识别出在某个环路中,标记为dead;顶点 已被访问过并且其所有的邻接点是dead状态或者与该顶点在同一个环路集合中,标记为done;
当某一线程访问顶点 时,将该线程身份信息加入线程集合thread(v)中;
环路集合circle(v)采用并查集数据结构实现,具体包括:设顶点 对应的并查集结构为 , 和 分别代表顶点 在并查集里的父节点以及顶点所在并查集的深度;初始化时每个顶点对应一个独立的环路集合,即 ,相应地,并查集结构初始化为 和 ;
针对每一个线程p定义两个线程内局部数据结构,分别为控制栈 和顶点栈 ;其中控制栈 用于模拟该线程p进行深度优先搜索的递归操作,顶点栈 用于存储深度优先搜索遍历过程中访问到的顶点序列;
初始化所述控制栈 和顶点栈 均为空;
基于所述线程间共享内存数据结构和所述线程内局部数据结构,调用多个线程同时从所述虚拟顶点出发进行深度优先搜索遍历执行有向环路求解算法;
所有线程运行结束之后,利用所述线程间共享内存数据结构中的环路集合输出检测到的资金回流环路;
所述所有线程运行结束之后,利用所述线程间共享内存数据结构中的环路集合输出检测到的资金回流环路,具体包括:所有线程运行结束之后,扫描所述线程间共享内存数据结构中的环路集合的并查集,找出每个环路顶点集合的根节点,并根据根节点的个数统计总的资金回流环路个数;
对每个并查集根节点创建一个环路链表存放该根节点所在环路的顶点信息,初始化为空;
遍历有向图中的每个顶点,利用并查集上的查找算法找到该顶点的根结点,将该顶点添加至对应根节点的环路链表中;
根据每个并查集根节点对应的环路链表输出预设交易长度范围内的资金回流环路。
2.一种银行交易资金回流多线程并行检测系统,其特征在于,包括:有向图及邻接表构建模块,用于根据银行交易记录构建有向图及其邻接表存储结构,并增加一个虚拟顶点来指向有向图中每一个顶点;
所述有向图及邻接表构建模块具体包括:
交易记录获取单元,用于获取银行交易记录;所述银行交易记录中包括多条交易流水;
有向图构建单元,用于将每一条交易流水对应一条有向边,资金转出账户作为起始顶点,资金转入账户作为终止顶点,构建出银行交易记录的有向图;
邻接表构建单元,用于为所述有向图中的每个顶点 构建对应的邻接表来存放该顶点指向的所有邻接点;
虚拟顶点增加单元,用于在所述有向图中增加一个虚拟顶点 ,所述虚拟顶点 的邻接表中的邻接点为所述有向图中的所有顶点;
数据结构构建模块,用于基于所述有向图创建线程间共享内存数据结构,定义并初始化线程内局部数据结构;
所述数据结构构建模块具体包括:
线程间共享内存数据结构构建单元,用于针对所述有向图中的每个顶点 创建三个线程间共享内存数据结构,分别为状态集合status(v)、线程集合thread(v)以及环路集合circle(v);其中状态集合status(v)用于记录该顶点 的状态,线程集合thread(v)用于记录该顶点 当前所在的线程集合,环路集合circle(v)用于记录该顶点 当前所处的环路集合;
每个顶点在环路求解过程中共区分三个状态,使用状态集合status(v)进行记录:顶点未访问过,标记为unvisited;顶点 已完全识别出在某个环路中,标记为dead;顶点 已被访问过并且其所有的邻接点是dead状态或者与该顶点在同一个环路集合中,标记为done;
当某一线程访问顶点 时,将该线程身份信息加入线程集合thread(v)中;
环路集合circle(v)采用并查集数据结构实现,具体包括:设顶点 对应的并查集结构为 , 和 分别代表顶点 在并查集里的父节点以及顶点所在并查集的深度;初始化时每个顶点对应一个独立的环路集合,即 ,相应地,并查集结构初始化为 和 ;
线程内局部数据结构构建单元,用于针对每一个线程p定义两个线程内局部数据结构,分别为控制栈 和顶点栈 ;其中控制栈 用于模拟该线程p进行深度优先搜索的递归操作,顶点栈 用于存储深度优先搜索遍历过程中访问到的顶点序列;
线程内局部数据结构初始化单元,用于初始化所述控制栈 和顶点栈 均为空;
多线程并行检测模块,用于基于所述线程间共享内存数据结构和所述线程内局部数据结构,调用多个线程同时从所述虚拟顶点出发进行深度优先搜索遍历执行有向环路求解算法;
资金回流交易信息输出模块,用于在所有线程运行结束之后,利用所述线程间共享内存数据结构中的环路集合输出检测到的资金回流环路;
所述资金回流交易信息输出模块具体包括:
资金回流环路个数统计单元,用于在所有线程运行结束之后,扫描所述线程间共享内存数据结构中的环路集合的并查集,找出每个环路顶点集合的根节点,并根据根节点的个数统计总的资金回流环路个数;
根节点环路链表创建单元,用于对每个并查集根节点创建一个环路链表存放该根节点所在环路的顶点信息,初始化为空;
遍历查找单元,用于遍历有向图中的每个顶点,利用并查集上的查找算法找到该顶点的根结点,将该顶点添加至对应根节点的环路链表中;
资金回流环路输出单元,用于根据每个并查集根节点对应的环路链表输出预设交易长度范围内的资金回流环路。