networkx : 계산 된 값으로 에지 무게

Question

NetworkX 라이브러리를 사용하여 최단 경로 알고리즘을 구현하고 싶습니다. 내 경우, 내 가중치 함수는 다른 가장자리 속성에서 값을 가져옵니다. 가중치는 계산 된 값이므로 합병증을 피하기 위해 추가 속성으로 저장하고 싶지는 않습니다. 다른 속성이 변경되면 값을 갱신하십시오. 그러나 NetworkX의 algorithm API은 에지 데이터 키가되도록 가중치를 요구합니다.

값을 저장하지 않을 수 있는지 궁금합니다. 내 이상적인 경우는 알고리즘에 맞춤식 가중치 함수를 지정하는 것입니다.

Answer 1

매개 변수는 가장자리 속성 사전의 키 여야합니다. 따라서 사전에 가장자리 속성을 설정하여 가중치로 사용해야합니다. 최단 경로를 계산하기 전에 간단한 루프에서 이들을 할당 할 수 있습니다 (나중에 원하는 경우 삭제할 수 있습니다).

또는 당신은 다른 에지 속성에서 체중을 계산하는 다 익스트라 알고리즘 코드를 수정할 수 있습니다. 그래프가 있다고 가정하면 (multigraph가 아닌) 한 행으로 변경됩니다. 231 https://networkx.lanl.gov/trac/browser/networkx/networkx/algorithms/shortest_paths/weighted.py#L231 당신이 NetworkX 내장 된 방법을 사용하려고하는 경우

vw_dist = dist[v] + edgedata.get(weight,1) 

Answer 2

당신은 느리게 가중치를 계산하지만,이 특성을 이용하여, 속성 인 것처럼 제시 할 수있다. 예를 들어

class Edge(object): 

    def __init__(self, x, y): 
     self.x = x 
     self.y = y 

    def get_z(self): 
     return self.x + self.y 

    z = property(get_z) 


e = Edge(3,4) 
print e.z 

여기 e.z 실제 저장된 값은 Edge 객체의 속성이 될 것으로 보인다. 하지만 그렇지 않습니다. 수요에 따라 계산됩니다. 당신은 여전히 ​​get_z 방법, 당신의 업데이트 코드를 작성해야하지만, 여기 장점은 종속 속성을 변경할 때마다 구체적인 값을 업데이트에 대해 걱정할 필요가 없다는 것입니다. 대신 요청할 때만 계산합니다.

z의 많은 액세스가 걱정되는 경우 잠재적으로 값 비싼 계산이 필요하므로이 예제를 캐시 값으로 쉽게 확장 할 수 있습니다. getter는 계산을하기 전에 룩업 테이블을 검사합니다. 이것은 단지 memoization입니다.