生成保留给定分区的排列列表(上下文:图同构)

generate a list of permutations that preserve a given partitioning (context: Graph Isomorphism)

我正在开发一个 python 程序,该程序使用强力方法测试两个给定的 networkx 图 G 和 H 的同构性。每个图中的每个节点都被分配了一个标签和颜色属性,程序应该测试图 G 和图 H 之间所有可能的双射,图 G 的标签是固定的,图 H 的标签是可变的。此外,我只需要检查双射,确保对于给定的节点,图 G 中的颜色 'i' 映射到 H 中也具有颜色 'i' 的节点上。为此,我创建了一个 class,它继承了 nx.Graph 的所有 methods/attributes,并编写了几个我自己的方法。

到目前为止,我所做的是遍历两个图,并创建了一个字典,它给出了 G 中每个节点到 H 的可能有效映射。

例如对于图 G == 1-2-3 着色将是:color_g = {1: 1, 2: 2, 3:1} 因为 '1' 和 '3' 的度数相同,而 2 的度数不同。

如果图表 H == 2-1-3 那么 color_h = {2:1, 1:2, 3:1}

当我运行一个group_by_color函数给出从G到H的可能映射时我会得到以下字典

地图 = {1: [2, 3], 2: [1], 3:[2, 3]}

这意味着由于 G 中的颜色分区节点“1”可以映射到 H 中的“2”或“3”,因此 G 中的“2”只能映射到 H 中的“1” H等。

问题是:我正在努力生成一个列表,其中包含从 G 到 H 的所有有效排列,这些排列保留了着色给出的分区,并且正在努力思考如何去做吧。我很清楚 python 的排列函数,并且在以前版本的蛮力方法中我没有考虑颜色,这意味着排列列表要大得多(并且 运行 -时间慢得多),但实现也更容易。现在我想通过只考虑根据给定的着色可能的排列来加快速度。

问题: 我如何使用我的地图字典,并使用它来生成 color-conserving/preserving(德语:'farbe-erhaltend')的双射函数?或者你会建议一个不同的方法吗?

其他一些事实:

两个图中的节点都被标记为连续且升序 'colors' 我使用的是数字,因为图表可以变得任意大。

如有任何帮助,我将不胜感激, ItsAnApe

回答问题的算法部分:假设您的分区有 k 个单元:C_1,...,C_k。保留分区的整个集合的排列与笛卡尔积 P_1 x P_2 x ... x P_k 之间存在 1 对 1 的对应关系,其中 P_i 是单元格的一组排列 C_i。 itertools 包含生成笛卡尔积的方法。您究竟想如何使用像 (p_1, p_2, ..., p_k) 这样的元组,其中每个 p_i 是单元格 C_i 的排列取决于在你的目的。如果需要,您可以编写一个函数将它们组合成一个排列——或者如果您打算逐个单元地使用排列,则只需迭代它们。

以下是概念证明。它将分区表示为元组列表,其中每个元组代表一个单元格,并且它列出了保留分区的整个集合的所有排列。在测试用例中,它列出了 {1,2,3,4,5,6,7} 的 2x6x2 = 24 个排列,这些排列保留了分区 [(1,4), (2,3,5),(6,7 )]。无需遍历和过滤所有 7 个! = 5040 个排列:

#list_perms.py
import itertools

def combinePermutations(perms):
    a = min(min(p) for p in perms)
    b = max(max(p) for p in perms)
    d = {i:i for i in range(a,b+1)}
    for p in perms:
        pairs = zip(sorted(p),p)
        for i,j in pairs:
            d[i] = j
    return tuple(d[i] for i in range(a,b+1))

def permute(cell):
    return [p for p in itertools.permutations(cell)]

def listGoodPerms(cells):
    products = itertools.product(*(permute(cell) for cell in cells))
    return [combinePermutations(perms) for perms in products]

#to test:
myCells = [(1,4), (2,3,5), (6,7)]
for p in listGoodPerms(myCells): print(p)

模块为运行时的输出:

(1, 2, 3, 4, 5, 6, 7)
(1, 2, 3, 4, 5, 7, 6)
(1, 2, 5, 4, 3, 6, 7)
(1, 2, 5, 4, 3, 7, 6)
(1, 3, 2, 4, 5, 6, 7)
(1, 3, 2, 4, 5, 7, 6)
(1, 3, 5, 4, 2, 6, 7)
(1, 3, 5, 4, 2, 7, 6)
(1, 5, 2, 4, 3, 6, 7)
(1, 5, 2, 4, 3, 7, 6)
(1, 5, 3, 4, 2, 6, 7)
(1, 5, 3, 4, 2, 7, 6)
(4, 2, 3, 1, 5, 6, 7)
(4, 2, 3, 1, 5, 7, 6)
(4, 2, 5, 1, 3, 6, 7)
(4, 2, 5, 1, 3, 7, 6)
(4, 3, 2, 1, 5, 6, 7)
(4, 3, 2, 1, 5, 7, 6)
(4, 3, 5, 1, 2, 6, 7)
(4, 3, 5, 1, 2, 7, 6)
(4, 5, 2, 1, 3, 6, 7)
(4, 5, 2, 1, 3, 7, 6)
(4, 5, 3, 1, 2, 6, 7)
(4, 5, 3, 1, 2, 7, 6)