Dynamic creation of a graph meeting the conditions

Question

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 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]]

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)

then:

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?

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