基于Python的图的同构算法实现

今天药忘吃喽~ 2024-03-24 20:10 29阅读 0赞

目录  
数据机构课程设计报告书 1  
一、概要 1  
二、文章结构 1  
三、问题描述：图的同构 1  
四、判断图同构的算法 2

1.  基于生成全排列序列的算法 2
2.  两种基于深度优先搜索与根据局部匹配进行剪枝的算法 3
3.  基于 canonical labelling（CL）算法的图同构匹配问题 7  
    五、算法实现 7  
    六、算法测试 7  
    七、时间复杂度与 NP 9  
    八、图同构算法的实际应用 9
4.  计算机视觉与模式识别 9
5.  蛋白质结构的研究 10
6.  化合物分子的识别 10
7.  社交网络 10  
    九、小结 10  
    十、参考文献 11  
    五、算法实现  
    我实现了本文中所提到的前三种算法：全排列、Ullman，VF2。在实现 VF2 算法时，我从 networkx 库汲取了大量编程经验与技巧，在此感谢一切向开源事业做出无私奉献的开发者。  
    实现代码我将不会贴在文中，因为这只关乎实现而非算法本身。本次实验我使用了 Python 语言，主要是因为其简洁与灵活。值得一提的是，Python 的内置集合数据结构（set）为 VF2 算法的实现提供了极大地便利，由于并集、差集等集合常用运算都被重载为了具有语义性的数学运算符，代码的可读性与简洁性都有了质的飞跃。  
    由于全排列算法实际意义不大，其执行效率也是低得惊人，在节点数大于 10 时就已然放弃了挣扎。所以本部分我将对 Ullman 算法与 VF2 算法进行运行时间上的比较。但考虑到本人的编码水平问题，并不能保证两个算法的差异真正是由算法本身引起的，所以本部分主要观察算法趋势。

from copy import deepcopy
    
    import numpy as np
    
    import graph.algorithm as alg
    import graph_database as g_db
    from graph.graph import Graph
    from graph.utils import *
    
    import pickle
    
    
    def alg_tester(alg_name, graph_g, graph_h, name="None", output=False):
        matcher = alg_name(graph_g, graph_h)
        outer = RunTimer()
        inner = RunTimer()
    
        cnt = 0
        time_list = []
    
        ntl = None
    
        if matcher.is_isomorphic():
            outer.tic()
            inner.tic()
            print(name, "- 两图同构")
            print("字典序映射(G -> H):")
            for res in matcher.isomorphisms_iter():
                cnt += 1
                res = sort_dict_by_key(res)
                inner.toc()
                time_list.append(inner.how())
                if output:
                    print("#{:03d}  -  {:.15f}\t{}".format(cnt, time_list[-1], res))
                inner.tic()
            print("可能映射数: ", cnt)
            ntl = np.array(time_list)
            print("\tmean :\t{}\n\tstd  :\t{}".format(ntl.mean(), ntl.std()))
        else:
            print(name, "- 两图不同构")
        outer.toc()
        outer.show()
        return {
        "total": outer.how(), "mean": ntl.mean(), "std": ntl.std()}
    
    
    if __name__ == "__main__":
        # edge_dict = {
        
        #     1: [6, 7, 8, 9],
        #     2: [5, 7, 8],
        #     3: [5, 6, 8],
        #     4: [5, 6, 7],
        #     5: [2, 3, 4],
        #     6: [1, 3, 4],
        #     7: [1, 2, 4],
        #     8: [3, 2, 1],
        #     9: [1]
        # }
    
        # edge_dict = {
        
        #     1: [2, 6, 7],
        #     2: [1, 3],
        #     3: [2, 4],
        #     4: [3, 5, 7],
        #     5: [4, 6, 7],
        #     6: [1, 5],
        #     7: [1, 4, 5]
        # }
    
        # edge_dict = {
        
        #     1: [8, 9, 10, 11, 13],
        #     2: [8, 9, 10, 14, 15],
        #     3: [8, 9, 12, 13, 14],
        #     4: [8, 9, 12, 13, 15],
        #     5: [10, 11, 12, 14, 15],
        #     6: [10, 11, 13, 14, 15],
        #     7: [11, 12, 13, 14, 15],
        #     8: [16, 1, 2, 3, 4],
        #     9: [16, 1, 2, 3, 4],
        #     10: [16, 1, 2, 5, 6],
        #     11: [16, 1, 5, 6, 7],
        #     12: [16, 3, 4, 5, 7],
        #     13: [1, 3, 4, 6, 7],
        #     14: [2, 3, 5, 6, 7],
        #     15: [2, 4, 5, 6, 7],
        #     16: [8, 9, 10, 11, 12],
        # }
    
        times = {
        }
        for name, edge_dict in g_db.graphs:
            print("testing -", name)
            ee = g_db.parse_data(edge_dict)
            times[len(ee)] = {
        }
            G = Graph(ee)
            # H = Graph(edge_dict_2)
            H = deepcopy(G)
            per = np.random.permutation(list(H.edge_dict.keys()))
            H.do_permutation(idx_mapping(per))
            times[len(ee)]["VF2"] = alg_tester(alg.VF2Matcher, G, H, "VF2", output=False)
            if len(ee) < 30:
                print("-" * 40)
                times[len(ee)]["Ullmann"] = alg_tester(alg.UllmannMatcher, G, H, "Ullmann", output=False)
            print("-" * 80)
            print("\n\n")
    
        format_print_dict(times)
    
        pickle.dump(times, open("times_record.svz", "wb"))
    
        # alg_tester(alg.VF2Matcher, G, H, "VF2", output=True)
        # print("-" * 40)
        # alg_tester(alg.UllmannMatcher, G, H, "Ullmann", output=True)
        # print("-" * 40)
        # alg_tester(alg.PermutationMatcher, G, H, "全排列", output=True)

![在这里插入图片描述][b6c08f4607fc4e0ab7304c43d480f4f6.png_pic_center]  
![在这里插入图片描述][4f3d6728d4e54fbcb588b393b3fd6ad0.png_pic_center]  
![在这里插入图片描述][e603dde594c943b08a5304c9cb246d89.png_pic_center]  
![在这里插入图片描述][c01660f124e1491ea9148af93911f52f.png_pic_center]  
![在这里插入图片描述][afcf2e61e2514926a7836fae119eb5da.png_pic_center]  
![在这里插入图片描述][e06f867abaf44b63ad909d96090cb58e.png_pic_center]  
![在这里插入图片描述][fc084d9f1b144ab3b22d05708aae2830.png_pic_center]  
![在这里插入图片描述][f1c7170cca1a43fb8ecceb19682bbb92.png_pic_center]  
![在这里插入图片描述][3e89a78436eb428d95ff72538c4745e8.png_pic_center]  
![在这里插入图片描述][b7a68e38e9d34900b679126f113386af.png_pic_center]  
![在这里插入图片描述][11f2593d30314fa8b7c482374887aa3e.png_pic_center]  
![在这里插入图片描述][aa5f76a53c354086b714f6847e792f08.png_pic_center]

[b6c08f4607fc4e0ab7304c43d480f4f6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/1c5940db76544cbf801d399fe2aa831f.png
[4f3d6728d4e54fbcb588b393b3fd6ad0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/82ee40d0fc0645b6bb4f91d082e69ffa.png
[e603dde594c943b08a5304c9cb246d89.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/9b2007d00cd54a25828e1bb1f288ceb5.png
[c01660f124e1491ea9148af93911f52f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/6afdccb464054f5cbca8f4017da8fd57.png
[afcf2e61e2514926a7836fae119eb5da.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/9b4dd09803fd4988ba19c000085b2220.png
[e06f867abaf44b63ad909d96090cb58e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/a6265a8fbcf6484b8e543f53de2a8294.png
[fc084d9f1b144ab3b22d05708aae2830.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/d75d96df8f74480ca5683147cc79bbd5.png
[f1c7170cca1a43fb8ecceb19682bbb92.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/7c8a27ac176c40a481f8884b1dc477bd.png
[3e89a78436eb428d95ff72538c4745e8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/937d0359bad643ff8b2ea40caa999cd1.png
[b7a68e38e9d34900b679126f113386af.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c6c4642db8784dd682852ad9cf828255.png
[11f2593d30314fa8b7c482374887aa3e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/20f2b81a43284effa8f544d276921b9e.png
[aa5f76a53c354086b714f6847e792f08.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/665ecc6d200040b9807f8be5686b6bbf.png