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

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

以上是伴随剪枝的搜索算法的大致流程,为了更清楚地描述这些步骤,我们给出了伪代码.算法 2 为搜索算
法的主体,其中的 subgraph 是根据第一阶段获得的五元组构建的子图,SearchLimit 值是人为给定的限制长度,ct
值为关闭时间值.Extend 函数和 UnBlock 函数用于封锁节点和解锁节点 [18] .
算法 2. ALLPATH(s,vcur,timestamps,stk).
输入:环路起始点 s,当前节点 vcur,当前时间戳向量 timestamps,先前路径束的堆栈 stk;
输出:所有要求内的路径.
1. tcur←timestamps 中的最小值;
2. ct[vcur]←tcur;
3. lastp←0;
4. ts←{(vcur,x,t)∈subgraph|tcur<t≤ct(x)}
5. for (ts 中的节点值 to)
6. if (to==s) //找到环路
7. T←{t|(vcur,to,t)∈ts};
8. maxT←max(T);
9. lastp←max(lastp,maxT);
10. 扩展 new_stk; //将新的路径加入到之前搜索的路径中
11. else
12. ret←0;
13. tss←{t∈ts|t<ct(x)};
14. if (tss 不为空)
15. 扩展 new_stk;
16. if (new_stk.size(⋅)<SearchLimit)
17. ret←ALLPATH(s,to,tss,new_stk);
18. Else //最大的时间戳
19. ret←new_stk.back(⋅).timestamps.back(⋅)+1;
20. num←min{t∈ts|t≥ret}
21. Extend(to,vcur,num);
22. if (ret)
23. num←max{t∈ts|t<num};
24. lastp←max(lastp,num);
25. if (lastp>0) //更新关闭时间
26. UnBlock(vcur,lastp);
27. return lastp;

4 实验与分析

4.1 实验设置
4.1.1 实验环境
我们使用 C++来实现此算法.所有的实验都运行在一台 Intel Corei5-8400 CPU@2.80GHz CPU 和 8GB 内存
的台式机上,操作系统为 Windows 系统.
4.1.2 实验数据集
为了验证算法的效率与实用性,本文使用以下 4 个真实的时序图数据集来进行对比实验,这 4 个数据集均
来自 SNAP 数据集 [20] (见表 1).