python - 在 Python 和 Networkx 中动态创建满足条件的图

Question

我有一个节点列表:

n = [a1, a2, a3, a4, b1, b2, b3, b4]

我想从中创建任何图形，在其中选择两个任意节点并找到 nx.shortest_path 我将获得所有三元组组合:

 comb = [[A, A, A], [A, A, B], [A, B, A], [A, B, B], [B, A, A], [B, A, B], [B, B, A], [B, B, B]]

其中 A 和 B 是节点 a1, a2, a3, a4, b1, b2, b3, b4 的对应项。

例如，如果算法为我创建节点之间的路径:

(a1, b1), (a2, a3), (a3, a4), (a3, b1), (b1, b2), (b2, b3)

然后:

nx.shortest_path(g, a2, a4) == (a2, a3, a4), as a case representation (A, A, A)
nx.shortest_path(g, a2, b1) == (a2, a3, b1), as a case representation (A, A, B)
nx.shortest_path(g, a3, a1) == (a3, b1, a1), as a case representation (A, B, A)

and so on all combinations with 'comb'.

您如何从算法方面看待它？

Answer 1

一些想法和部分解决方案。

从你的例子可以看出图是无向的(不是有向的)。在这种情况下，如果我们顶点 X 和 Y 之间的最短路径产生三元组(A，A，B)，那么 Y 和 X 之间的最短路径产生三元组(乙，甲，甲)。

想法是从一个字符串开始，该字符串包含所有三元组作为连续字符，无论方向如何。如果是字符串 AAABABBB 的三元组。现在我们可以用不同的 a 和 b 替换 A 和 B。生成图表:

a1 - a2 - a3 - b1 - a4 - b2 - b3 - b4

这个图满足条件。

在三元组的情况下，我们很幸运，我们有足够的节点来替换初始字符串。如果我们没有足够的节点，则可以合并上层图节点以减少所需节点的数量。合并是在相同类型(A 或 B)的两个节点之间完成的，因此它不会产生长度 < 2 * size_of_substrings - 1 的循环。在三元组循环的情况下，循环的长度可以为 5 或更长。在上字符串 (AAABABBB) 的情况下，没有距离 >= 5 的相同类型的节点。循环的约束是不在节点之间产生新的最短路径。

检查长度为 4 的子字符串的大小写。比我们有初始字符串 AAAABBAABABBAABBBB。我们可以在 >= 7 的距离上合并 A 或 B。例如让我们将第一个 A 与中间的单个 A 合并。生成图表:

/-------\
AAAABBAAB
|
BBAABBBB

注意初始字符串必须通过交换 A<->B 来对称。同样减少 A 可以减少相反的 B。