¿Cómo restringir ciertas rutas en los gráficos de NetworkX?

Question

Estoy tratando de calcular el camino más corto entre 2 puntos utilizando los algoritmos Dijkstra y A Star (en un gráfico dirigido de NetworkX).

En estos momentos se trabaja muy bien y puedo ver la ruta calculada, pero me gustaría encontrar una manera de restringir ciertos caminos .

Por ejemplo si hemos siguientes nodos:

nodos = [1,2,3,4]

Con estos bordes:

bordes = ((1,2), (2 , 3), (3,4))

¿hay alguna manera de bloquear/restringir 1 -> 2 -> 3 pero todavía permiten 2 -> 3 & 1 -> 2.

Esto significaría que:

• puede de viaje desde 1 a 2

• puede viajar de 2 a 3

• no puede viajes de 1 a 3 .. directa o indirectamente (es decir, restringir 1-> 2-> 3 ruta).

¿Se puede lograr esto en NetworkX ... si no hay otra biblioteca de gráficos en Python que permita esto?

Gracias.

Answer 1

Interesante pregunta, nunca escuché de este problema, probablemente porque no tengo mucha experiencia en este tema, ni mucha experiencia con NetworkX. Sin embargo, tengo una idea para un algoritmo. Esta puede ser la forma más ingenua de hacer esto y me gustaría saber de un algoritmo más inteligente.

La idea es que puede usar sus reglas de restricción para transformar su gráfico en un nuevo gráfico donde todos los bordes son válidos, utilizando el siguiente algoritmo.

La restricción de la trayectoria (1,2,3) se puede dividir en dos reglas:

• Si viniste (1,2) luego quite (2,3)
• Si deja más (2,3) luego eliminar (1,2)

Para poner esto en el gráfico, puede insertar copias del nodo 2 para cada caso. Llamaré a los nuevos nodos 1_2 y 2_3 después del borde válido en el caso respectivo. Para ambos nodos, copie todos los bordes entrantes y salientes menos el borde restringido.

Por ejemplo:

Nodes = [1,2,3,4] 
Edges = [(1,2),(2,3),(4,2)] 

La ruta válida sólo será 4-> 2-> 3 no 1-> 2-> 3. Así que expandimos el gráfico:

Nodes = [1,1_2,2_3,3,4] # insert the two states of 2 
Edges = [ # first case: no (1_2,3) because of the restriction 
      (1,1_2), (4, 1_2) 
      # 2nd case, no (1,2_3) 
      (2_3,3), (4,2_3)] 

La única ruta válida en este gráfico es 4-> 2_3-> 3. Esto simplemente se asigna a 4-> 2-> 3 en el gráfico original.

Espero que esta respuesta al menos pueda ayudarlo si no encuentra una solución. Las reglas de restricción más largas explotarían el gráfico con un número exponencialmente creciente de nodos estatales, por lo que este algoritmo es demasiado simple o el problema es difícil ;-)

Answer 2

Puede establecer los datos de su nodo {color = ['blue'] ]} para el nodo 1, el nodo 2 tiene {color = ['red', 'blue']} y node3 tiene {color = ['red']}. Luego use un networkx.algorithms. astar_path enfoque() el establecimiento de la heurística

• se define como una función que devuelve un might_as_well_be_infinity cuando se encontró un nodo sin el mismo color que usted está en busca de
• peso = less_than_infinity.