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

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

10 голосов
/ 02 ноября 2011

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

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

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

узлов = [1,2,3,4]

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

ребер = ((1,2),(2,3), (3,4))

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

Это будет означать, что:

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

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

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

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

Спасибо.

Ответы [ 2 ]

4 голосов
/ 02 ноября 2011

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

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

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

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

Чтобы поместить это в график, вы можете вставить копии узла 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 голосов
/ 13 ноября 2015

Вы можете установить данные своего узла {color = ['blue']} для узла 1, узел 2 имеет {color = ['red', 'blue']}, а узел 3 имеет {color = ['red']},Затем используйте сеть x.algorithms.При подходе astar_path () установка эвристики

  • устанавливается на функцию, которая возвращает might_as_well_be_infinity, когда она обнаружила узел без того же цвета, который вы ищете
  • weight = less_than_infinity.
...