Creación dinámica de un gráfico que cumple las condiciones en Python y Networkx

Tengo una lista de nodos:

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

a partir del cual quiero crear cualquier gráfico, en el cual, después de elegir dos nodos y encontrar nx.shortest_path , obtendré todas las combinaciones de 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]] 

Donde A y B son las contrapartes de los nodos a1, a2, a3, a4, b1, b2, b3, b4 .

Por ejemplo, si el algoritmo crea rutas entre nodos para mí:

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

entonces:

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

¿Cómo lo tomarías desde el lado algorítmico?

Algunas ideas y soluciones parciales.

En su ejemplo, se ve que la gráfica no está dirigida (no está dirigida). En ese caso, si el camino más corto entre los vértices X e Y produce un triplete (A, A, B), el camino más corto entre Y y X produce un triplete (B, A, A).

La idea es comenzar desde una cadena que contiene todos los tripletes como caracteres consecutivos, sin importar la dirección. En el caso de los tripletes que es la cadena AAABABBB Ahora podemos sustituir A y B con diferentes a y b. Eso produce grafo:

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

Este gráfico satisface las condiciones.

En el caso de los trillizos tuvimos suerte de tener suficientes nodos para sustituir la cadena inicial. Si no tenemos suficientes nodos, es posible fusionar los nodos del gráfico superior para reducir el número de nodos necesarios. La fusión se realiza entre dos nodos del mismo tipo (A o B) para que no produzca un bucle de longitud <2 * size_of_substrings - 1. En el caso de los tripletes, el bucle puede tener una longitud de 5 o más. En el caso de la cadena superior (AAABABBB), no hay nodos del mismo tipo con distancia> = 5. La restricción en un bucle es no producir nuevas rutas más cortas entre los nodos.

Verifique el caso con una subcadena de longitud 4. De lo que tenemos la cadena inicial AAAABBAABABBAABBBB. Podemos fusionar A o B en la distancia> = 7. Por ejemplo, fusionemos primero A con solo A en medio. Eso produce grafo:

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

La cadena inicial de la nota debe ser simétrica intercambiando A <-> B. Con esa misma reducción de A se puede hacer para reducir la B opuesta.