NetworkX 그래프의 특정 경로를 제한하는 방법은 무엇입니까?

Question

Dijkstra와 A Star 알고리즘 (directed NetworkX 그래프에서)을 사용하여 2 점 사이의 최단 경로를 계산하려고합니다. 순간

그것을 잘 작동 내가 계산 된 경로를 볼 수 있지만 내가 특정 경로을 제한 의 방법을 찾고 싶습니다. 예를 들어

우리는 다음과 같은 경우 노드 이러한 가장자리

노드 = [1,2,3,4]

:

에지 = ((1,2), (2 > - 2 -> 3 & - 1 -> 2> 3 여전히 허용 2, 3), (3,4))

은 1 제한/차단하는 방법이있다.

이 그런 의미 :

• 수 여행 1

• 수 여행 2

• 수 없습니다 여행 1 ~ 3에게 3에 2 .. 직접 또는 간접적으로 (즉 1-> 2-> 3 경로를 제한).

NetworkX에서 달성 할 수 있습니까? 그렇지 않다면 파이썬에서 다른 그래프 라이브러리가 허용됩니까?

감사합니다.

Answer 1

재미있는 질문입니다.이 주제에 대해 많은 배경 지식이 없거나 NetworkX에 대한 많은 경험이 없기 때문에이 문제에 관해 들어 본 적이 없습니다. 그러나 알고리즘에 대한 아이디어가 있습니다. 이 작업을 수행하는 가장 순진한 방법 일 수 있으며 더 명확한 알고리즘을 듣게되어 기쁩니다.

다음 알고리즘을 사용하여 제한 규칙을 사용하여 모든 에지가 유효한 새 그래프로 그래프를 변형 할 수 있습니다. 당신이 온 경우두면 (1, 2) 다음 제거 (2,3)

• :

  경로 (1,2,3)의 제한은 두 가지 규칙으로 분할 할 수 있습니다 over (2,3) then remove (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으로 매핑됩니다.

기존 솔루션이 없다면이 답변으로 도움이되기를 바랍니다. 더 긴 제한 규칙은 지수 노드가 기하 급수적으로 증가하는 그래프를 날려 버리므로이 알고리즘이 너무 간단하거나 문제가 어렵습니다 .-)

Answer 2

노드 데이터 {color = [ 'blue' ]} 노드 1은 노드 2가 {color = [ 'red', 'blue']}이고 노드 3은 {color = [ 'red']}입니다. 그런 다음 networkx.algorithms를 사용하십시오.

• 휴리스틱을 설정 astar_path() 방식은 (는) 같은 색이
• 무게를 검색 = less_than_infinity없이 노드를 발견 할 때 might_as_well_be_infinity을 반환하는 함수로 설정되어 있습니다.