一种基于拓扑序列匹配的有向图

1、一种基于拓扑序列匹配的有向图子图同构过滤算法的设计与实现指导老师：吕建华学生： 罗丹学号： 71107304大纲 背景意义 问题描述 基本思路 关键算法 实验结果 总结 致谢2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法2背景意义 与其它数据结构相比，图能够表达更加丰富的语义，它能够很好的建模存在多种关联的数据，以及表示内部具有拓扑结构的数据。 丰富的语义和复杂的内部结构增加了各种查询算法的难度，使得传统的数据查询和处理算法无法继续适用或高效处理。2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法3背景意义 目前，大多数的图查询算法的思路： 优缺点 本文提出了一种基于拓扑序

2、列匹配的有向图子图同构的过滤算法，使得每个图都对应于一个独立的序列。2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法4图形数据库图形数据库G G候选结果集候选结果集CLCL结果集结果集RSRS过滤规则过滤规则子图同构检测子图同构检测过过 滤滤验验 证证问题描述 给定有向图数据库D=g1,g2,gn和查询图q，找出D中所有以q为子图的gi。2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法5基本思路2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法6关键算法 分层拓扑算法 序列匹配算法顶点标签唯一DAG顶点标签可重复DAG 环路处理算法2022-3-22基于拓扑序列匹配

3、的有向图子图同构过滤算法7分层拓扑算法分层拓扑算法关键算法2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法8分层拓扑算法 定义定义 DAGDAG上的严格偏序关系上的严格偏序关系对于顶点集V，对E中的每一条边，定义偏序关系ab，则“”是顶点集V上的严格偏序，满足反自反，非对称和传递性。2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法9分层拓扑算法2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法10拓扑序列：1,2 / 3,5,8 / 4,9 / 6,7138497265138497265序列匹配算法序列匹配算法顶点标签唯一顶点标签唯一DAGDAG关键算法2022-3

4、-22基于拓扑序列匹配的有向图子图同构过滤算法11序列匹配算法 - 顶点标签唯一DAG2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法12gi.str: 1,3/2,5/4/6,7/q.str: 2,3/4/6,7/ q.str的第一层：的第一层： 2,3/ Gi.str: 1,3/ 2,5/ 4/ 6,7/ q.str第二层：第二层： 4 / Gi.str: 1,3/ 2,5/ 4/ 6,7/ q.str第三层：第三层： 6,7 Gi.str: 1,3/ 2,5/ 4/ 6,7/ s=1s=1s=1序列匹配算法 - 顶点标签唯一DAG 命题命题 若Gi和q为标签不重复的有向无环图且

5、Gi包含q，则Gi.str必匹配q.str。证明略。 命题也证明了以上算法不丢解。2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法13序列匹配算法序列匹配算法顶点标签可重复顶点标签可重复DAGDAG关键算法2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法14序列匹配算法 - 顶点标签可重复DAG2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法15gi.str: a,d/b,c2/c1/eq.str: c1,d/c2/e序列匹配算法 - 顶点标签可重复DAG 命题命题 若Gi和q为DAG且Gi包含q，则Gi.str必匹配q.str。证明略。 以上命题的证明也就是，算

6、法2推广到顶点标签可重复DAG不丢解的证明。2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法16环路处理算法环路处理算法关键算法2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法17环路处理算法 定义定义 环路中顶点等序关系环路中顶点等序关系有向图环路中的边首尾相连，定义环路中顶点是等序关系。2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法18环路处理算法2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法191235412,35412,3,4,5算法的正确性算法的正确性实验测试2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法20算法的正确性2022

7、-3-22基于拓扑序列匹配的有向图子图同构过滤算法21性能分析性能分析实验测试2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法22性能分析 - 候选结果集平均大小2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法23性能分析 - 索引构造时间算法索引构造时间(sec.)gIndex 255.42FG-Index11.05TopologicalOrder5.99Tree+5.742022-3-22基于拓扑序列匹配的有向图子图同构过滤算法24性能分析 查询时间2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法25性能分析 查询时间2022-3-22基于拓扑序列匹配的有向图

8、子图同构过滤算法26性能分析 在线查询时间2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法27性能分析 在线查询时间2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法28性能分析 TopologicalOrder使得每个图都对应于一个独立的序列，无需构造复杂的索引。 数据库动态更新时，只需要进行个别序列处理，便于数据库的动态维护。并且，相对于图的匹配，序列的匹配是简单的，算法在线查询表现出色。2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法29总结 首先，根据定义有向图环路中顶点之间的等序关系，可以将有向图转化为DAG；然后根据定义在DAG上的严格偏序关系，将DAG拓扑成序列；再利用序列匹配算法过滤出候选结果集；最后通过同构检测验证，获得真正的结果集。 本文提出的算法无需构建复杂索引结构，便于数据库的动态维护，可用于在线查询。2022-3-22基于拓扑序列匹配的有向图子图同构过滤算法30致谢 感谢在座的老师耐