Jak ograniczyć niektóre ścieżki na wykresach NetworkX?

Question

Próbuję obliczyć najkrótszą ścieżkę między 2 punktami przy użyciu algorytmów Dijkstra i A Star (w ukierunkowanym grafie NetworkX).

Obecnie działa dobrze i widzę obliczoną ścieżkę ale chciałbym znaleźć sposób ograniczającą pewne ścieżki.

Na przykład, jeśli mamy następujących węzłów:

węzły = [1,2,3,4]

z tych krawędzi:

krawędzie = ((1,2), (2 , 3), (3,4))

istnieje sposób blokowania/ograniczając 1 -> 2 -> 3 ale pozwalają 2 -> 3 & 1 -> 2.

Oznaczałoby to, że:

• może podróże od 1 do 2

• może podróży od 2 do 3

• nie może podróże od 1 do 3 .. bezpośrednio lub pośrednio (tj. ograniczyć ścieżkę 1-> 2-> 3).

Czy można to osiągnąć w NetworkX. Jeśli nie, to jest inna biblioteka grafów w Pythonie, która by na to pozwoliła?

Dzięki.

Answer 1

Interesujące pytanie, nigdy nie słyszałem o tym problemie, prawdopodobnie dlatego, że nie mam zbyt wiele informacji na ten temat, ani dużego doświadczenia z NetworkX. Mam jednak pomysł na algorytm. To może być najbardziej naiwny sposób, aby to zrobić i chętnie usłyszę o mądrzejszym algorytmie.

Chodzi o to, że można użyć reguł ograniczeń, aby przekształcić wykres na nowy wykres, w którym wszystkie krawędzie są prawidłowe, przy użyciu następującego algorytmu.

Ograniczenie ścieżki (1,2,3) można podzielić na dwie reguły:

• Jeśli podeszła (1,2), a następnie usunąć (2,3)
• Jeśli zostawisz ponad (2,3), a następnie usuń (1,2)

Aby umieścić to na wykresie, można wstawić kopie węzła 2 dla każdego przypadku. Naznaczę nowe węzły 1_2 i 2_3 po prawidłowym zbiorze w odpowiednim przypadku. W przypadku obu węzłów kopiowane są wszystkie krawędzie przychodzące i wychodzące minus ograniczona krawędź.

Na przykład

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

Ważny jest tylko droga 4-> 2> 3 1-> 2> 3. Tak więc rozwijamy wykres:

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

Jedyną poprawną ścieżką na tym wykresie jest 4-> 2_3-> 3. To po prostu odwzorowuje 4-> 2-> 3 na oryginalnym wykresie.

Mam nadzieję, że ta odpowiedź może przynajmniej Ci pomóc, jeśli nie znajdziesz żadnego rozwiązania. Dłuższe reguły ograniczeń powodowałyby powiększenie wykresu z rosnącą wykładniczo liczbą węzłów stanu, więc albo ten algorytm jest zbyt prosty, albo problem jest trudny ;-)

Answer 2

Można ustawić dane węzła {kolor = ["niebieski" ]} dla węzła 1 węzeł 2 ma {kolor = ["czerwony", "niebieski"]}, a węzeł3 ma kolor {kolor = ["czerwony"]}. Następnie użyj networkx.algorithms. astar_path() podejście ustawiania

• heurystyki jest ustawiony na funkcję, która zwraca might_as_well_be_infinity gdy napotkał węzeł bez tego samego koloru, którego szukasz
• waga = less_than_infinity.