从图的集合中拒绝同构

Question

我有一个15M(百万)DAG(有向无环图 - 实际上是指向超立方体)的集合,我想从中删除同构.这个的常见算法是什么？每个图都相当小,一个维数为N的混合立方体,其中N为3到6(现在),得到64个节点的图,每个节点为N = 6的情况.

使用networkx和python,我实现了它,这适用于300k(千)的小集合就好(几天后运行).

def isIsomorphicDuplicate(hcL, hc):
    """checks if hc is an isomorphism of any of the hc's in hcL
    Returns True if hcL contains an isomorphism of hc
    Returns False if it is not found"""
    #for each cube in hcL, check if hc could be isomorphic
    #if it could be isomorphic, then check if it is
    #if it is isomorphic, then return True
    #if all comparisons have been made already, then it is not an isomorphism and return False

    for saved_hc in hcL:
        if nx.faster_could_be_isomorphic(saved_hc, hc):
            if nx.fast_could_be_isomorphic(saved_hc, hc):
                if nx.is_isomorphic(saved_hc, hc):
                    return True
    return False

一种更好的方法是将每个图形转换为其规范排序,对集合进行排序,然后删除重复项.这绕过了检查二进制is_isomophic()测试中的每个15M图,我相信上面的实现类似于O(N!N)(不考虑同构时间)而干净转换为规范排序和排序应该采取O(N)用于转换+ O(log(N)N)用于搜索+ O(N)用于删除重复项.O(N!N)>> O(log(N)N)

我在Canonical图形标注上发现了这篇论文,但它用数学方程式非常简洁地描述,没有伪代码:"McKay的Canonical Graph Labeling Algorithm" - http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf

tldr:我有一个不可思议的大量图表来检查二进制同构检查.我相信这样做的常用方法是通过规范排序.是否存在任何打包算法或直接发布以实现算法(即具有伪代码)？

Answer 1

以下是McKay的Canonical Graph标签算法的细分,如Hartke和Radcliffe的论文[链接到论文]所示.

我应该首先指出这里有一个开源实现:nauty和Traces源代码.

好的,我们这样做!不幸的是,这个算法在图论中很重要,所以我们需要一些术语.首先,我将从定义同构和自守开始.

同构:

如果两个图是相同的,则它们是同构的,除了顶点标记不同.以下两个图是同构的.

自守:

如果它们完全相同,则两个图是自动的,包括顶点标记.以下两个图是自守的.这似乎微不足道,但由于技术原因,这一点很重要.

图哈希:

整个事情的核心思想是有一种方法将图形散列为字符串,然后对于给定的图形,您计算与其同构的所有图形的哈希字符串.按字母顺序(技术上按字典顺序)最大的同构散列字符串称为"Canonical Hash",产生它的图形称为"Canonical Isomorph"或"Canonical Labeling".

有了这个,要检查是否有两个图是同构的,你只需要检查它们的规范的isomporphs(或规范的labellings)是否相等(即彼此的自动形态).哇行话!不幸的是,没有行话,这更令人困惑:-(

我们将要使用的哈希函数对于图G称为i(G):通过查看G中的每对顶点(按顶点标签的顺序)构建二进制字符串,如果有边缘则设置为"1"在这两个顶点之间,如果不是,则为"0".这样,i(G)中的第j位表示图中没有该边的存在.

麦凯的标准图标记算法

问题是对于n个顶点上的图形,有基于标记顶点的方式的O(n!)个可能的同构哈希字符串,如果我们必须多次计算相同的字符串(即自动变形),还有许多更多.一般来说,我们必须计算每个isomorph哈希字符串,以便找到最大的一个,没有神奇的排序.McKay的算法是一种搜索算法,可以通过从搜索树中修剪所有自动变形来更快地找到这个规范的isomoprh,迫使规范isomoprh中的顶点按递增程度顺序进行标记,以及一些减少同形体数量的其他技巧哈希.

(1)第4节:McKay的第一步是根据程度对顶点进行排序,修剪大部分isomoprhs进行搜索,但不保证是唯一的排序,因为可能存在给定度数的多个顶点.例如,下图有6个顶点; verts {1,2,3}有1度,verts {4,5}有2度,vert {6}有3度.根据顶点度的部分排序是{1,2,3 | 4,5 | 6 }.

(2)第5节:在顶点上没有区分的顶点上施加人工对称; 基本上我们采用一个具有相同度数的顶点组,然后依次选择一个在总排序中的第一个(图2中的纸张),所以在上面的例子中,节点{1,2 ,3 | 4,5 | 6}会生孩子{{ 1 | 2,3 | 4,5 | 6},{ 2 | 1,3 | 4,5 | 6}},{ 3 | 1,2 | 4 ,5 | 6}}}通过扩展组{1,2,3}以及子{{1,2,3 | 4 | 5 | 6},{1,2,3 | 5 | 4 | 6}}通过扩展组{4,5}.这种拆分可以一直到叶节点完成,这些叶节点是像{1 | 2 | 3 | 4 | 5 | 6}这样的总排序,它描述了G的完全同构.这允许我们通过顶点进行部分排序程度从(1),{1,2,3 | 4,5 | 6},并建立一个树列出规范同构的所有候选人 - 这已经是一个少于n的方法!因为,例如,顶点6将永远不会出现.请注意,McKay以深度优先的方式评估孩子,从最小的群体开始,这导致更深但更窄的树,这对于下一步中的在线修剪更好.另请注意,每个总排序叶节点可能出现在多个子树中,修剪进来的地方!

(3)教派 6:在搜索树时,查找自同构并使用它来修剪树.这里的数学有点高于我,但我认为这个想法是,如果你发现树中的两个节点是彼此的自同构,那么你可以安全地修剪它们的一个子树,因为你知道它们都会产生相同的叶子节点.

我只给出了McKay的高级描述,这篇论文在数学中有了更深入的内容,构建实现需要理解这个数学.希望我已经给你足够的上下文,要么回去重新阅读论文,要么阅读实现的源代码.