Как ограничить определенные пути в графиках NetworkX?

Я пытаюсь рассчитать кратчайший путь между двумя точками, используя алгоритмы Дейкстра и А-Звезды (в направленном графике NetworkX).

В настоящий момент он работает нормально, и я вижу вычисленный путь, но мне хотелось бы найти способ ограничения определенных путей.

Например, если у нас есть следующие узлы:

nodes = [1,2,3,4]

С этими ребрами:

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

Есть ли способ блокировки/ограничения 1 → 2 → 3, но все еще разрешить 2 → 3 и 1 → 2.

Это означает, что:

  • может перемещаться от 1 до 2

  • может перемещаться от 2 до 3

  • не может перемещаться от 1 до 3.. прямо или косвенно (т.е. ограничивать 1- > 2- > 3 путь).

Может ли это быть достигнуто в NetworkX.. если нет, есть еще одна библиотека графов в Python, которая позволила бы это?

Спасибо.

Ответы

Ответ 1

Интересный вопрос, я никогда не слышал об этой проблеме, возможно, потому, что у меня мало опыта в этой теме, и не много опыта работы с NetworkX. Однако у меня есть идея для алгоритма. Это может быть самый наивный способ сделать это, и я был бы рад услышать более умный алгоритм.

Идея состоит в том, что вы можете использовать свои правила ограничения для преобразования графика в новый граф, где все ребра действительны, используя следующий алгоритм.

Ограничение пути (1,2,3) можно разделить на два правила:

  • Если вы пришли (1,2), то удалите (2,3)
  • Если вы оставите (2,3), то удалите (1,2)

Чтобы разместить это на графике, вы можете вставить копии node 2 для каждого случая. Я приведу новые узлы 1_2 и 2_3 после допустимого края в соответствующем случае. Для обоих узлов вы копируете все входящие и исходящие края за пределы ограниченного ребра.

Например:

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

Допустимый путь должен быть только 4- > 2- > 3 не 1- > 2- > 3. Итак, мы разворачиваем график:

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

Единственный допустимый путь на этом графе - это 4- > 2_3- > 3. Это просто отображает 4- > 2- > 3 в исходном графе.

Я надеюсь, что этот ответ может по крайней мере помочь вам, если вы не найдете никакого существующего решения. Более длинные правила ограничения взорвали бы граф экспоненциально растущим числом состояний, поэтому либо этот алгоритм слишком прост, либо проблема сложна; -)

Ответ 2

Вы можете установить данные node {color = ['blue']} для node 1, node 2 имеет {color = ['red', 'blue']}, а node3 - {color = [ 'красный']}. Затем используйте сетевые алгоритмы. astar_path(), устанавливающий

  • эвристика устанавливается в функцию, которая возвращает значение________________________________________________________________________IN_IN_INFINITY, когда встречается <
  • вес = less_than_infinity.