Más

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

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


Estoy tratando de calcular la ruta más corta entre 2 puntos usando los algoritmos Dijkstra y A Star (en un gráfico NetworkX dirigido).

Por el momento funciona bien y puedo ver la ruta calculada, pero me gustaría encontrar una forma de restringir cierto rutas.

Por ejemplo, si tenemos los siguientes nodos:

nodos = [1,2,3,4]

Con estos bordes:

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

¿Hay alguna forma de bloquear / restringir? 1 -> 2 -> 3 pero aún permitir 2 -> 3 y 1 -> 2.

Esto significaría que:

  • puede viajar de 1 a 2

  • puede viajar de 2 a 3

  • no poder viajar 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 lo permita?


El método add_edge de un Graph en NetworkX toma un peso como atributo. Este es un proxy para la restricción transversal. Si el peso especificado es alto, los algoritmos de recorrido evitarán esa ruta. Por ejemplo:

importar networkx como nx G = nx.Graph () G.add_edge ('a', 'b', peso = 0.6) G.add_edge ('b', 'c', peso = 0.2) G.add_edge ('c' , 'd', peso = 999) # este está restringido G.add_edge ('a', 'd', peso = 0.7)

A primera vista, su ejemplo de no permitir el enrutamiento de 1 -> 2 -> 3 parecía extraño. Sin embargo, esto tiene sentido si queremos restringir los "atajos". Supongamos que tenemos un gráfico G que representa el plano de un edificio con habitaciones y pasillos. Los vértices V representan puntos de decisión de giro y los bordes E representan caminos entre puntos de decisión. Una oficina con dos puertas y un pasillo a cada lado puede proporcionar una ruta rápida de un pasillo al otro, pero a menos que sea su oficina, no es bueno simplemente cortar. En este caso, la semántica de nuestro gráfico G (V, E) es demasiado limitada, incluso cuando se agregan pesos de borde.

Entonces, la respuesta a su pregunta es no, las representaciones gráficas nativas en NetworkX no pueden manejar este escenario. Pero podría implementar un cálculo como el modelo bigraph de Milner. Esto podría hacerse ampliando las relaciones de adyacencia de NetworkX para incluir hipervínculos y semántica de acceso.