Page 162 - 《软件学报》2020年第12期

3828 Journal of Software 软件学报 Vol.31, No.12, December 2020

代表拥有同一个起点、起始时间、结束时间的一系列环路.算法 1 中给出了寻找候选五元组函数的伪代码,其
中,S 集合代表节点拥有的三元组信息,SearchLimit 值为人为给定的限制长度值.
同理,在使用布隆过滤器 [19] 进行处理时,我们仍然可以利用 hop 值来降低搜索的复杂度.这是因为在使用布
隆过滤器时,为了满足获取候选信息的需要,要对原图进行一次反向遍历和一次正向遍历 [18] .而在进行正向遍历
的过程中,就可以运用三元组进行操作,操作的方式与上述方式是基本一致的.

Fig.2 Reduce the size of candidates using hop
图 2 通过 hop 缩小候选节点集合
算法 1. set_interaction_exact(G).
输入:读取时序图的输入流.其中,要求图输入的格式为(起始节点,终止节点,时间戳)的三元组,输入时间不
递减;
输出:〈起点,起始时间,结束时间,候选点集,最小跳数〉的五元组.
1. while (读取时序边〈from,to,timestamp〉)
2. if (self_loop) continue;
3. S[to]←pair((from,timestamp),1);
4. if (S[from]不为空) //进行继承
5. for (S[from]中的三元组〈node,time,hop〉)
6. if (该三元组的时间已经在时间窗口外) //清理
7. 从 S[from]中删除这个三元组;
8. else
9. new_hop←hop+1;
10. if (to==node) //找到了环路
11. if (new_hop≤SearchLimit)
12. 记录五元组信息;
13. else //还要继续进行搜索
14. if (new_hop<SearchLimit)
15. if (S[to]中不含有这个三元组)
16. S[to]←((node,time),new_hop);
17. else
18. if (原 hop 值>新的 hop 值)
19. 更新这个三元组的 hop 值;
20. if (到了程序约定的清理时间)
21. 清除已经过期的三元组;
3.2 搜索算法
在这一模块中,我们将沿用 2SCENT 算法中的剪枝方式 [18] ,利用关闭时间和封锁节点的策略来帮助我们进
行搜索.虽然通过第 1 步操作我们已经减少了很多不会被搜索到的点,但是当图变得越来越大,搜索的长度越来
越长,一些搜索已经超过了要求的长度却仍在进行.这样的搜索增加了寻找环路所需的时间.若想在 2SCENT 算