Page 369 - 《软件学报》2026年第5期

2248 软件学报 2026 年第 37 卷第 5 期

1. sg j (i) ← ∅,Q ← ∅;
2. label ← the key of the middle node in sq j ;
3. Q ← get node from L KN (P i , label);
4. FOR each u in Q DO
5. match nodes of the first level of sq j ;
6. match nodes of the third level of sq j ;
7. IF match all nodes of the sq j THEN
8. sg j (i).push(all matches nodes);
9. IF u ∈ B THEN
10. FOR each v in all matches nodes and v ∈ ( j , i) DO
11. P i ← P i ∪P j ;
12. END FOR
13. END IF
14. END IF
15. END FOR
16. RETURN sg j (i).

例如, 在图 4 所示的划分区域 P 3 中匹配图 8(b) 中的模式子图 sq 1 时, 由于该模式子图的中间顶点标签为 a, 则
根据 L KN (P 3 , a) 列表将候选顶点集合初始化为{17, 0}. 然后逐一去访问该集合中的顶点, 其中顶点 17 的入度为 0,
无法匹配第 1 层顶点. 当访问到顶点 0 时, 其双向广度优先遍历一步后, 分别找到了可匹配模式子图 sq 1 第 1 层和
第 3 层的顶点, 即{17}和{1, 2}. 但由于顶点 0 属于边界顶点, 并且其中匹配的顶点 2 属于其他划分区域, 因此需将
划分区域 P 3 更新为 P 3 ∪P 1 , 接下来则在更新后的划分区域 P 3 中匹配其他模式子图.
4.4.3 模式图匹配
为加快模式图匹配算法的执行效率, 本文还给出了相应的剪枝策略, 即当划分区域 P i 不可匹配其某一个模式
子图 sq j 时, 则说明在该划分区域中不存在可以匹配模式图的子图, 可直接返回 sg j (i) 为空. 除此之外, 按照最优匹
配顺序逐一匹配模式子图的过程, 也可以看作是不断缩小最终结果的过程, 也可视为一种剪枝. 划分模式图后得到
的最优匹配顺序, 可最大程度上约束后匹配的模式子图中的顶点, 使得在匹配后序模式子图时, 仅需在已匹配的顶
点中选取含有中心顶点标签的顶点, 构成当前模式子图的中间顶点的候选顶点. 例如, 当在某划分区域匹配
图 8(b) 中的模式子图 sq 2 时, 其中的顶点 3 已被约束在了匹配模式子图 sq 1 的结果子图中. 因此, 虽然在模式匹配
的过程中会不断扩大划分区域, 但匹配的模式子图的约束顶点也越来越多, 符合的匹配结果会因约束越来越少, 而
不会因为匹配区域的扩大而获得更多的匹配结果. 基于模式子图的匹配算法, 模式图匹配算法 PMUI (graph pattern
matching on unified index) 的流程如算法 6 所示. 第 1 行初始化最终结果. 第 2–14 行为在各划分区域 P i 中匹配模
式图 q m : 第 5 行调用 4 模式子图的匹配算法在各划分区域 P i 中匹配模式子图 sq j , 并得到匹配结果 sg j (i). 第 6–9
行用于判断是否满足剪枝条件. 第 11–13 行是对未剪枝情况的操作, 将同一划分区域中对模式子图的匹配结果做
连接, 得到该划分区域下对模式图 q m 的匹配结果. 第 16 行为对所有划分区域下对模式图 q m 的匹配结果做并集操
作. 第 17 行返回最终的匹配子图集合.
算法 6. 模式图匹配算法 PMUI.

输入: 划分覆盖 P, 模式图划分覆盖 sp, 临界顶点集合 B;
输出: 匹配的子图集合 g.
1. g ← ∅;