Dynamic Creation Of A Graph Meeting The Conditions In Python And Networkx

I have a list of nodes: n = [a1, a2, a3, a4, b1, b2, b3, b4] from which I want to create any graph, in which after choosing two any nodes and finding nx.shortest_path I will get a

Solution 1:

Some ideas and partial solutions.

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).

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

This graph satisfies conditions.

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.

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

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