networkx: вес ребра как вычисленное значение

Question

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

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

Answer 1

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

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

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