networkx: edge weight as a calculated value

Question

I want to implement a shortest path algorithm with NetworkX library. In my case, my weight function derives the value from other edge attributes. Because weight is a calculated value, I don't want to store it as an extra attribute to avoid the complication e.g. update the value when other attributes change. NetworkX's algorithm API, however, seems requiring weight to be an edge data key.

So I was wondering if it's possible not to store the value? My ideal case would be to specify a custom weight function to the algorithm.

Answer 1

The parameter does need to be a key in the edge attribute dictionary. So you need to set an edge attribute in the dictionary to use as a weight. You could assign those in a simple loop before computing the shortest path (and delete them later if you want).

Alternatively you could modify the Dijkstra algorithm code to compute your weight from the other edge attributes. Assuming you have a graph (not a multigraph) it is a one-line change. Put your weight formula in line 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

You can calculate the weight value lazily, but present it as if it were an attribute, using properties. For example:

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

Here e.z appears to be an actual stored value, an attribute of the Edge object. But it's not - it's calculated on demand. You still have to write your update code, in the get_z method, but the benefit here is that you don't have to worry about updating a concrete value whenever the dependent properties change. Instead, you only calculate it when it is asked for.

It would be easy to extend this example to cache values, if you were concerned about many accesses of z causing needless potentially expensive calculations. The getter would check a look-up table before doing the calculation. This is just memoization.