Come limitare determinati percorsi nei grafici di NetworkX?

Question

Sto cercando di calcolare il percorso più breve tra 2 punti utilizzando gli algoritmi Dijkstra e A Star (in un grafico NetworkX diretto).

Al momento funziona benissimo e posso vedere il percorso calcolato, ma vorrei trovare il modo di limitare alcuni percorsi.

Per esempio se abbiamo nodi seguenti:

nodi = [1,2,3,4]

Con questi bordi:

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

c'è un modo di bloccare/limitare 1 -> 2 -> 3 ma ancora permettono 2 -> 3 & 1 -> 2.

Ciò significa che:

• può viaggio ai 1 a 2

• può viaggio ai 2 a 3

• non può viaggi da 1 a 3 .. direttamente o indirettamente (cioè limitare il percorso 1-> 2-> 3).

Questo può essere ottenuto in NetworkX .. se non è presente un'altra libreria di grafici in Python che consentirebbe questo?

Grazie.

Answer 1

Interessante domanda, non ho mai sentito parlare di questo problema, probabilmente perché non ho molto background in questo argomento, né molta esperienza con NetworkX. Tuttavia, ho un'idea per un algoritmo. Questo potrebbe essere il modo più ingenuo per farlo e sarei lieto di apprendere un algoritmo più intelligente.

L'idea è che è possibile utilizzare le regole di restrizione per trasformare il grafico in un nuovo grafico in cui tutti i bordi sono validi, utilizzando il seguente algoritmo.

La limitazione di percorso (1,2,3) può essere diviso in due regole:

• caso in cui siate sopra (1,2) e rimuovere (2,3)
• Se si lascia oltre (2,3) quindi rimuovere (1,2)

Per inserire questo nel grafico è possibile inserire copie del nodo 2 per ciascun caso. Chiamerò i nuovi nodi 1_2 e 2_3 dopo il margine valido nel rispettivo caso. Per entrambi i nodi, si copiano tutti i bordi in entrata e in uscita meno il margine limitato.

Ad esempio:

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

Il percorso valido deve essere solo 4-> 2-> 3 non 1-> 2-> 3. Quindi espandiamo il grafico:

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

L'unico percorso valido in questo grafico è 4-> 2_3-> 3. Questo semplicemente mappa su 4-> 2-> 3 nel grafico originale.

Spero che questa risposta possa almeno aiutarti se non trovi alcuna soluzione esistente. Regole di restrizione più lunghe farebbero esplodere il grafico con un numero in crescita esponenziale di nodi di stato, quindi o questo algoritmo è troppo semplice, o il problema è difficile ;-)

Answer 2

Puoi impostare i tuoi dati di nodo {color = ['blue' ]} per il nodo 1, il nodo 2 ha {color = ['red', 'blue']} e node3 ha {color = ['red']}. Quindi utilizzare un networkx.algorithms. approccio astar_path() impostando l'euristica

• è impostato su una funzione che restituisce un might_as_well_be_infinity quando ha incontrato un nodo senza lo stesso colore che si sta cercando
• peso = less_than_infinity.