2

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

到目前为止，我所做的是遍历这两个图，并创建了一个字典，它为 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”，依此类推.

这是问题所在： 我正在努力生成从 G 到 H 的所有有效排列的列表，以保留由着色给出的分区，并且正在努力思考如何去做。我很清楚 python 的排列函数，并且在以前版本的蛮力方法中我没有考虑颜色，这意味着排列列表要大得多（并且运行时间要慢得多），但也可以实现更轻松。现在我想通过只考虑根据给定颜色可能的排列来加快速度。

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

其他一些事实：

两个图中的节点都是连续标记的，并且我使用的“颜色”是数字，因为这些图可以变得任意大。

我会很感激任何帮助，ItsAnApe

4

1 回答 1

0

要回答您问题的算法部分：假设您的分区有 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)
于 2015-06-23T15:34:11.617 回答