背景Weisfeiler-Lehman算法(lhdlf费勒-雷曼算法)是测试图同构的典型算法之一。 在此记录其实现原理。 参考报道是Weisfeiler-Lehman Graph Kernels

伪代码论文的伪代码如下

假设测试同构的两张图为g和g `，则在节点v的第I次迭代中，算法分别进行了标签复合集定义、复合集排序、标签压缩、再标签四个阶段的处理。

标签复合集的定义是v的标签，如果是第一次迭代，则v的标签复合集中只有一个元素。

如果不是第一次迭代，则v的标签复合集元素是v的所有邻居在上一次迭代中生成的标签。

复合集排序是：首先按升序对复合集中的元素进行排序，将排序后的元素组合成一个字符串； 然后，将v在上次反复中生成的标签作为前缀，追加到这个s中。

标签压缩两张图表g和g的所有节点的字符串s，按升序排列； 然后通过映射函数f，将每个s映射到压缩标签，只有在s1=s2时生成的压缩标签相同。

也就是说，压缩标签类似于s的标识符，但映射函数f完全可以通过计数函数实现。 其实，如果可以将s和压缩标签一一对应起来，就没有必要把前面的s按升序排列。

重标签将压缩标签作为节点v的两张图的第I个标签。

如果g和g `在此回合生成的标签集不同，则这两幅图不是同构的，算法直接结束。

以下图为例，图a至d显示了lhdlf费勒-莱曼算法在g和g上的第一次迭代过程

图a是初始形态，节点的标签对应于节点类型。

图b是复合集的生成和排序拼接的结果。 对于给定节点v，他的复合集是邻居在上一次迭代中生成的标签集。 但是，这里的上次迭代是初始化，邻居在上次迭代中生成的标签是邻居的初始标签(也就是节点类型)。 因此，以图g为例，两个1号节点的复合集合都是{4}，4号节点的复合集合是{1、1、3、5}{5}{6}，其余按升序排列。 完成后，将已排序的复合集合的元素依次连接到字符串s，并将节点标签本身作为前缀连接到s之前。 在g中，对于节点1，产生的s是‘1，4’； 对于节点4，所产生的s是’ 4、4、4, 1135 ‘。 最后，用s替换节点v的标签。

图c为标签压缩过程，将g和g `的所有复合集合按升序排列，按顺序标注。 此处的排序规则按元素中数字的升序排序，因此{ 2，3 }位于{ 1，4 }之前，{ 2，4，5 }位于{ 2，3，5 }之前。 经过上一次迭代(初始迭代)，图中已经出现了五种节点，这里的编号从6开始。

图d在最后步骤中重新排序，并且每个节点使用生成的编号而不是每个节点的复合集合，来获得节点在这种迭代中生成的新标签。

在以上两幅图中，因为第一次生成的新标签的集合不同，所以他们俩是异构化图。

由于时间复杂度主要是针对每次迭代来处理排序，所以假设复合集合中有m个元素，该复合集合能够针对某个曲线g针对每次迭代来生成，则迭代时间复杂度为o(m )。 由于每个节点的复合集至少包含其自己的标签，因此每一循环生成的复合集的元素数m为=节点数n。

设反复次数为h，则lhdlf费勒拉曼算法的计算复杂度为o(hm )