Блог

Я хочу реализовать алгоритм кратчайшего пути с библиотекой NetworkX. В моем случае моя функция weight выводит значение из других атрибутов ребра. Поскольку вес является вычисляемым значением, я не хочу сохранять его как дополнительный атрибут, чтобы избежать осложнений, например, обновлять значение при изменении других атрибутов. Однако algorithm API NetworkX, похоже, требует, чтобы вес был ключом данных ребра.

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

Параметр действительно должен быть ключом в словаре атрибутов ребра. Итак, вам нужно установить атрибут ребра в словаре для использования в качестве веса. Вы могли бы назначить их в простом цикле перед вычислением кратчайшего пути (и удалить их позже, если хотите).

В качестве альтернативы вы могли бы изменить код алгоритма Дейкстры, чтобы вычислить свой вес на основе других атрибутов ребра. Предполагая, что у вас есть график (не мультиграф), это изменение в одну строку. Поместите свою формулу веса в строку 231 https://networkx.lanl.gov/trac/browser/networkx/networkx/algorithms/shortest_paths/weighted.py#L231

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

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

 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 , вызывающих ненужные потенциально дорогостоящие вычисления. Получатель проверил бы справочную таблицу перед выполнением вычисления. Это просто запоминание.