生成保留给定分区的排列列表（上下文：图同构）

Question

我正在开发一个 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

Answer 1

回答问题的算法部分：假设您的分区有 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)

生成保留给定分区的排列列表（上下文：图同构）

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

python

graph

permutation

networkx

isomorphism