(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210250063.7 (22)申请日 2022.03.14 (71)申请人 中山大学 地址 510275 广东省广州市海珠区新港西 路135号 (72)发明人 姚正安　黄凤　张婧纯　陶文哲　 (74)专利代理 机构 广州粤高专利商标代理有限 公司 44102 专利代理师 禹小明 (51)Int.Cl. G06F 16/23(2019.01) G06F 16/22(2019.01) (54)发明名称 一种以动态有向图形式保存的数据维护方 法和系统 (57)摘要 本发明公开一种以动态有向图形式保存的 数据维护方法和系统， 方法包括以下步骤： S1： 实 时获取以动态有向图形式保存的数据， 在动态有 向图中， 顶点表示对象， 边表示对象间的关系； S2： 对所述动态有向图进行初始化， 得到每个强 连通分支， 并标记出每个强连通分支的标签， 获 取每个强连通分支所含的顶点集合和边集合； S3： 当数据发生变化时， 对应的动态有向图表现 为新增加边或删除边， 判断新增加的边集和被删 除的边集对应的强连通分支的标签， 分别处理更 新， 得到更新后的动态有向图。 本发明针对增边 情形和删边情形， 而非每次都对全量数据重新检 测强连通分支， 冗余检测大 大减少了 计算开支。 权利要求书2页 说明书7页 附图2页 CN 114840535 A 2022.08.02 CN 114840535 A 1.一种以动态有向图形式保存的数据维护方法， 其特 征在于， 包括以下步骤： S1： 实时获取以动态有向图形式保存的数据， 在动态有向图中， 顶点表示对象， 边表示 对象间的关系； S2： 对所述动态有向图进行初始化， 得到每个强连通分支， 并标记出每个强连通分支的 标签， 获取每 个强连通分支所含的顶点 集合和边集合； S3： 当数据发生变化时， 对应的动态有向图表现为新增加边或删除边， 判断新增加的边 集和被删除的边 集对应的强连通分支的标签， 分别处 理更新， 得到更新后的动态有向图。 2.根据权利要求1所述的以动态有向图形式保存的数据维护方法， 其特征在于， 步骤S3 中处理新增加的边集， 具体为： S301： 对于新增加的边集中的每一条新增边， 利用冗余检测方法， 检测出不影响原有的 强连通分支的新增边， 直接将原有的强连通分支的边数量加1； S302： 对于影响原有的强连通分支的新增边， 重新计算强连通分支， 利用异步迭代的方 法将原有的动态有向图缩构为有向无环图； S303： 对缩构后得到的有向无环图进行处 理， 剪掉有向无环图中的单团； S304： 在剪掉单团后的有向无环图中重新计算所有强连通分支， 得到更新后的动态有 向图。 3.根据权利要求2所述的以动态有向图形式保存的数据维护方法， 其特征在于， 步骤 S301中对于新增 加的边集中的每一条新增边， 需判断是否影响原有的强连通分支， 具体为： 当新增加的边(u,v)的顶点u和顶点v在同一个强连通分支中， 称为 内部连接， 此时不影 响原有的强连通分支； 当新增加的边(u,v)的顶点u和顶点v不在同一个强连通分支中， 成为外部连接， 此 时影 响原有的强连通分支。 4.根据权利要求3所述的以动态有向图形式保存的数据维护方法， 其特征在于， 步骤 S301中通过检测顶 点u和顶点v对应的强连通分支的标签是否相同， 若相同， 则顶 点u和顶点 v在同一个强连通分支， 若不相同， 则顶点u和顶点v不在同一个强连通分支。 5.根据权利要求4所述的以动态有向图形式保存的数据维护方法， 其特征在于， 步骤 S303中使用Trim算法剪掉单团。 6.根据权利要求5所述的以动态有向图形式保存的数据维护方法， 其特征在于， 步骤 S304中在有向无环图上实行Co loring算法计算 新图的所有强连通分支。 7.根据权利要求1所述的以动态有向图形式保存的数据维护方法， 其特征在于， 步骤S3 中处理被删除的边 集， 具体为： S311： 对于被删除的边集中的每一条被删除的边， 利用冗余检测方法， 检测出不影响原 有的强连通分支的被删除的边， 直接在原有的强连通分支删除即可； S312： 根据动态图中强连通分支间的相互独立性， 将可能被破坏的所有强连通分支挑 选出来， 对这些强连通分支分别选择算法进行重新计算强连通分支； S313： 选择枢轴点， 标记图中最大强连通分支的根； S314： 根据现实世界图的小世界属性和幂律度分布， 如果最大的强连通分支被破坏， 选 择静态图强连通分支并行检测算法Multistep算法进行重新计算， 如果最大的强连通分支 未被破坏， 执 行步骤S315；权　利　要　求　书 1/2 页 2 CN 114840535 A 2S315： 选择阈值， 分别选择不同的算法对顶点总数大于阈值和小于阈值的强连通分支 进行更新。 8.根据权利要求7所述的以动态有向图形式保存的数据维护方法， 其特征在于， 步骤 S315中所述阈值Ver texCut＝10 00。 9.根据权利要求8所述的以动态有向图形式保存的数据维护方法， 其特征在于， 步骤 S315中， 对顶点总数大于阈值的强连通分支采用Coloring算法进行更新， 对顶点总数小于 阈值的强连通分支采用Tarjan串行算法进行 更新。 10.一种以动态有向图形式保存的数据维护系统， 其特 征在于， 包括： 数据获取模块， 所述数据获取模块用于实时获取以动态有向图形式保存的数据， 在动 态有向图中， 顶点表示数据个 体， 便表示数据个 体间的联系； 初始化模块， 所述初始化模块用于对所述动态有向图进行初始化， 得到每个强连通分 支， 并标记出每 个强连通分支的标签， 获取每 个强连通分支所含的顶点 集合和边集合； 处理更新模块， 所述处理更新模块用于选择冗余检测和 异步迭代的方法分别处理新增 加的边集和被删除的边 集， 得到更新后的动态有向图。权　利　要　求　书 2/2 页 3 CN 114840535 A 3