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

目录
一、概要 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
   八、图同构算法的实际应用
   1.计算机视觉与模式识别
   图的匹配技术已经在模式识别领域取得了长足的进展，具体而言其渗透到以下几个方面：图像分析与处理、文本一致性的鉴定、图像的匹配与提取等。对于

计算机视觉领域，现阶段，许多机器人的目标检测部分都会包含图的匹配，从深海探测到太空遥感识别，图的匹配技术在计算机视觉领域有着十分成功的应用， 其还渗透到了医学中有害细胞的识别，例如癌细胞的识别，与场景分析领域等。
对于实际事物应用匹配算法时，通常会将事物利用图来进行表述。我们知道图主要在呈现一种具有组织性的关系，而这种关系体现在具体事物上，便是同类事物具有的方方面面的属性。这一理论不仅适合于图像的匹配，各种事物都可以用来匹配，因为联系是必然的、内在的、多样化的，只要能提取特征，就能进行匹配。
2.蛋白质结构的研究
在蛋白质研究领域，人们往往好奇具有某种特定结构的蛋白质分子或蛋白质分子簇会不会始终如一地具有某些性质，在进行大量研究后人们找到了一些能体现特定功能的特殊基团。而在研究新的蛋白质分子时，就可以利用自图同构算法进行部分匹配，以利用先验经验对未知蛋白质分子进行学习和探索。
3.化合物分子的识别
对于化合物的结构，必须有一种唯一且无歧义的标签对各种化合物进行标记。以前人们使用树结构来进行这方面的工作，随着数学尤其是群论的发展，一类专门研究化合物结构性质的学科诞生，并推动了分子结构表示从树形图发展到了平面图。对于分子结构的特殊性质，再得益于各种图同构匹配算法的蓬勃发展，化合物分子的匹配可以在有限的时间内高效地完成。
4.社交网络
如何检测人与人之间的相似性，利用他们的社交网络可以轻松完成这一任务。人所进行的关系建立是有目的性、有目标性的，所以对于拥有不同属性的人来说， 他们的社交网络图会呈现出不同的结构。理论上认为，在某些方面相似的两个人， 他们的社交网络图会呈现出某些相似的特征。
九、小结
图的同构算法是一类古老且经典的问题，虽然其被认为是一类 NP 的问题， 但这并不妨碍人们对高效匹配算法的追求。
本次课程设计使我初步了解了图的同构问题，本文转载自http://www.biyezuopin.vip/onews.asp?id=16711看到了图同构算法的发展历程与各种侧重点不同的算法。使我印象最深刻的一篇论文便是 McKay 对于 Nauty 算法的原论文，我被其严谨的数学论证过程所震撼，也深刻意识到自己要学的东西还有很多。
软件并不是单纯的算法与数据结构的堆叠，简单的堆叠是没有灵魂的，它更应该是适应实际问题的最佳匹配。同理，算法也不是对于前人智慧结晶的简单背诵，更应该是对其内在缘由的深度把握。知道、会用一个新算法没什么了不起， 真正厉害的，是通过研究算法与算法被研究出来的过程，将前人的思维方式纳入自己的技术栈。熟练掌握的算法与数据结构是一个程序员的硬实力，而对于体系与性能的精当把控就完全体现了一个人的技术软实力。从长远来看，软实力的积累是至关重要且应当长久不断的一环。

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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114