我有一个节点列表：
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'.
您如何从算法方面获取它？
一些想法和部分解决方案。
从你的例子可以看出，图是无向的（没有指向。）在这种情况下，如果我们在顶点X和Y之间的最短路径产生三元组（A，A，B），那么Y和X之间的最短路径产生三元组（B， A，A）。
想法是从包含所有三元组的字符串开始，作为连续字符，无论方向如何。如果三元组是字符串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.