专利名称--【子图匹配装置及子图匹配的方法】

基本信息
申请号 CN201210586892.9 申请日 2012-12-28 公开(公开)号 CN103077216A 公开(公开)日 2013.05.01
申请(专利权)人 中国科学院深圳先进技术研究院 申请人地址 518055 广东省深圳市南山区西丽大学城学苑大道1068号
发明人 曾理;成杰峰;冯圣中 专利类型 发明专利
摘要 一种子图匹配装置,用于在大规模图中查找出与带环图匹配的子图,包括:生成树模块、匹配模块、判断模块以及集合模块。生成树模块根据最小生成树算法找到带环图的生成树;匹配模块自底向上对数据图进行生成树匹配,寻找与生成树匹配的树Li(i>=1);判断模块判断所述树Li的评分函数值与缺失边数之和是否大于等于预设值,若是,则判断模块判断树Li能否扩展为带环图;集合模块还在所述树Li的评分函数值与缺失边数之和大于等于预设值时将所述集合V中前固定值个匹配图输出。
主权项 一种子图匹配装置,用于在大规模图中查找出与带环图匹配的子图,包括:生成树模块,用于根据最小生成树算法找到所述带环图的生成树;匹配模块,用于自底向上对数据图进行生成树匹配,寻找与生成树匹配的树Li(i>=1);判断模块,用于判断所述树Li的评分函数值与缺失边数之和是否大于等于预设值,其中,所述判断模块还用于在所述树Li的评分函数值与缺失边数之和小于预设值时判断所述树Li能否扩展为带环图;集合模块,用于在树Li能扩展为带环图时将所述树Li扩展为匹配图,并存入集合V中,其中,所述集合模块还用于将所述集合V中的匹配图按照权重从小到大来排序,所述判断模块还用于判断集合V中匹配图的个数是否大于等于固定值,且在集合V中匹配图的个数大于等于固定值时将所述预设值设为第固定值个匹配图的权重;其中,所述集合模块还用于在所述树Li的评分函数值与缺失边数之和大于等于预设值时将所述集合V中前固定值个匹配图输出。
IPC信息
IPC主分类号 G06F17/30(2006.01)I
IPC分类号 G06F17/30(2006.01)I
法律状态信息
法律状态公告日 2016.01.20 法律状态 授权 法律状态信息 授权
法律状态公告日 2013.06.05 法律状态 实质审查的生效 法律状态信息 实质审查的生效 IPC(主分类):G06F 17/30 申请日:20121228
法律状态公告日 2013.05.01 法律状态 公开 法律状态信息 公开
代理信息
申请(专利权)人 中国科学院深圳先进技术研究院 申请人地址 518055 广东省深圳市南山区西丽大学城学苑大道1068号
获取专利