动态创建满足Python和Networkx条件的图 [英] Dynamic creation of a graph meeting the conditions in Python and Networkx

问题描述

我有一个节点列表:

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

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

from which I want to create any graph, in which after choosing two any nodes and finding nx.shortest_path I will get all combinations of triples:

 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的对应物.

Where A andB are the counterparts of nodes a1, a2, a3, a4, b1, b2, b3, b4.

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

For example, if the algorithm creates paths between nodes for me:

(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'.

您将如何从算法角度考虑呢?

How would you take it from the algorithmic side?

推荐答案

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

Some ideas and partial solutions.

从您的示例中可以看出，图形是无向的(无向的).在这种情况下，如果我们在顶点X和Y之间的最短路径产生了三元组(A，A，B)，则在Y和X之间的最短路径产生了三元组. (B，A，A).

From your example it is seen that graph is undirected (not directed.) In that case, if we shortest path between vertices X and Y produces triplet (A, A, B), than shortest path between Y and X produces triplet (B, A, A).

构想将从包含所有三胞胎作为连续字符的字符串开始，无论方向如何.如果三元组是字符串AAABABBB.现在我们可以用不同的a和b代替A和B.产生图:

Idea is to start from a string that contains all triplets as consecutive characters, no matter of direction. In case of triplets that is string AAABABBB. Now we can substitute A's and B's with different a's and b's. That produces graph:

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

此图满足条件.

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

In case of triplets we had a luck that we had enough nodes to substitute initial string. If we do not have enough nodes, than it is possible to merge upper graph nodes to reduce number of needed nodes. Merging is done between two nodes of same type (A or B) so that it doesn't produce loop of length < 2 * size_of_substrings - 1. In case of triplets loop can have length 5 or more. In case of upper string (AAABABBB) there are no nodes of same type with distance >= 5. Constraint on a loop is to not produce new shortest paths between nodes.

检查子串的长度为4的大小写.然后我们有了初始字符串AAAABBAABABBAAAABBBB.我们可以在> = 7的距离上合并A或B.让我们将第一个A与中间的单个A合并.产生图:

Check case with substring of length 4. Than we have initial string AAAABBAABABBAABBBB. We can merge A or B on distance >= 7. E.g. lets merge first A with single A in middle. That produces graph:

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

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

Note initial string has to be symmetric by exchanging A<->B. With that same reduction of A can be done to reduce opposite B.

这篇关于动态创建满足Python和Networkx条件的图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！