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

Question

我正在开发一个python程序，它使用蛮力方法测试两个给定的networkx图G和H是否同构。每个图中的每个节点都被分配了一个标签和颜色属性，程序应该测试图G（标签是固定的）和图H（标签可以改变）之间的所有可能的双射。另外，我只需要检查双投影，以确保对于给定的节点，图G中的颜色“i”映射到H中也有颜色“i”的节点。为此，我创建了一个类，它继承了nx.图形，写了一些自己的方法。在

到目前为止，我所做的是浏览这两个图，并创建了一个字典，其中给出了G中每个节点到H的可能有效映射

例如，对于图g==1-2-3 颜色应该是：color_g={1:1，2:2，3:1}，因为“1”和“3”的度数相同，而2的度数不同。在

如果图H==2-1-3，则 颜色{2:1，1:2，3:1}

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

{2，地图：[2]，3]

这意味着，由于颜色分区节点G的“1”可以从H映射到“2”或“3”，G的“2”只能从H映射到“1”，依此类推。在

问题是：我正在努力生成一个从G到H的所有有效置换的列表，这些置换保留了着色所给的分区，并且正在努力思考如何实现这一点。我很清楚python的置换函数，在brute-force方法的前一个版本中，我没有考虑颜色，这意味着置换列表要大得多（运行时要慢得多），但是实现起来也更容易。现在我想通过只考虑根据给定颜色可能的排列来加快速度。在

问题：如何使用我的地图字典，并使用它生成保色/保色的双射函数（德语：“farbe erhaltend”）？或者你会建议一种不同的方法吗？在

其他一些事实：

两个图中的节点都是连续递增的 我使用的“颜色”是数字，因为图形可以变得任意大。在

我很感激你的帮助， 它的名字

Answer 1

回答你问题的算法部分：假设你的分区有k个单元：C劬。。。其中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)

模块运行时的输出：

^{pr2}$