python – Customization Networkx Short Path Weight Function

Not sure if I understood what you’re after quite right, but here is a potential way of going about it. I think there was a problem with the way you added nodes, as that made every node have the full length list of all passersby as an attribute (which I assume is not what you wanted). I worked around that in the below, and also replaced your function definition with a bit of a weird nx-y workaround instead.

import networkx as nx
import copy

# Time step 0 = graph with no connections but with passerby values
G = nx.DiGraph()
G.add_nodes_from(['a', 'b', 'c', 'd', 'e', 'f'])

passerlist=[1, 2, 3, 3, 2, 1]

passerdict = dict(zip(G.nodes(), passerlist))
nx.set_node_attributes(G, passerdict, 'passerby')

# Add in-degree attribute to nodes (counts incoming connections w/ weight)
in_degrees = dict(G.in_degree(weight="weight"))
nx.set_node_attributes(G, in_degrees, 'in-degree')

# Time step 1 = graph with first connections
G1 = copy.deepcopy(G)

G1.add_edge('a', 'b')
G1.add_edge('a', 'c')
G1.add_edge('b', 'c')
G1.add_edge('b', 'd')
G1.add_edge('c', 'e')
G1.add_edge('b', 'e')

#### Initialize weights for timestep 1 ####

# Keep track of the edges
edgeids = []

# Keep track of the weights
weights = []

# Iterate over the edges
for edge in G1.edges(data=True):
    # Append edge tuple to id edges
    edgeids.append((edge[0], edge[1]))
    # Append the 'passersby' attribute of the source node as the weight
# Create a dictionary of the edge ids and weights
weight_dict = dict(zip(edgeids, weights))

# Set the edge attribute based on the weight_dict
nx.set_edge_attributes(G1, weight_dict, 'weight')

# Add in-degree attribute to nodes (counts incoming connections w/ weight)
in_degrees = dict(G1.in_degree(weight="weight"))
nx.set_node_attributes(G1, in_degrees, 'in-degree')

Outputs at time step 1:

>>> NodeDataView({'a': {'passerby': 1}, 'b': {'passerby': 2}, 'c': {'passerby': 3}, 'd': {'passerby': 3}, 'e': {'passerby': 2}, 'f': {'passerby': 1}})

>>> OutEdgeDataView([('a', 'b', {'weight': 1}), ('a', 'c', {'weight': 1}), ('b', 'c', {'weight': 2}), ('b', 'd', {'weight': 2}), ('b', 'e', {'weight': 2}), ('c', 'e', {'weight': 3})])

route = nx.shortest_path(G, 'a', 'e', weight="weight")
>>> ['a', 'b', 'e']

>>> DiGraph with 6 nodes and 0 edges
>>> DiGraph with 6 nodes and 6 edges

>>> [('a', {'passerby': 1, 'in-degree': 0}), ('b', {'passerby': 2, 'in-degree': 0}), ('c', {'passerby': 3, 'in-degree': 0}), ('d', {'passerby': 3, 'in-degree': 0}), ('e', {'passerby': 2, 'in-degree': 0}), ('f', {'passerby': 1, 'in-degree': 0})]
>>> [('a', {'passerby': 1, 'in-degree': 0}), ('b', {'passerby': 2, 'in-degree': 1}), ('c', {'passerby': 3, 'in-degree': 3}), ('d', {'passerby': 3, 'in-degree': 2}), ('e', {'passerby': 2, 'in-degree': 5}), ('f', {'passerby': 1, 'in-degree': 0})]

(There was no path from ‘a’ to ‘f’ in your example so I replaced ‘f’ with ‘e’ for the shortest_path bit.)

Each weight here represents the number of passersby at the source node, which is how I understood how you want it.

(Conceptually this appears a bit problematic as the traffic at a node does not determine the length of the path between intersections, so for accuracy you might want to consider the distance of each path together with the traffic weights. But this goes beyond the question : ))

To update the weights you might try something like this:

#### Update weights for each time step between two graphs ####

def update_weights(G, G1):
    """Update the weights for each time step $t$

    G : nx.DiGraph
        DiGraph from t-1
    G1 : nx.DiGraph
        Raw DiGraph from t before updating weights

    G2 : nx.DiGraph
        DiGraph w/ updated weights for t
    lst = list(G1.nodes())
    for node in lst:
        # Check if there are new connections to source node (if in-degree is higher in current timestep than previous)
        if G1.nodes(data=True)[node]['in-degree'] > G.nodes(data=True)[node]['in-degree']:
            # Get the difference between timesteps
            diff = G1.nodes(data=True)[node]['in-degree'] - G.nodes(data=True)[node]['in-degree']
            # Add the difference to the passerby score from the previous time step to the new time step
            G1.nodes(data=True)[node]['passerby'] = G.nodes(data=True)[node]['passerby'] + diff
    updated = []
    # Loop over the updated passerby values and update weights again
    for edge in G1.edges(data=True):
        # Append updated weight
    # Updated weight attributes
    nx.set_edge_attributes(G1, dict(zip(edgeids, updated)), 'weight')
    return G1

# Show nodes before updating weights    
print('nodes before update', G1.nodes(data=True))

# Show weights before updating
print('edges before update', G1.edges(data=True))

# Perform update
G2 = update_weights(G, G1)

# Show nodes after updating weights
print('nodes after update ', G2.nodes(data=True))

# Show weights after updating
print('edges after update ', G2.edges(data=True))

which looks quite verbose, probably want to set some variables to clean this. This output:

>>> nodes before update [('a', {'passerby': 1, 'in-degree': 0}), ('b', {'passerby': 2, 'in-degree': 1}), ('c', {'passerby': 3, 'in-degree': 3}), ('d', {'passerby': 3, 'in-degree': 2}), ('e', {'passerby': 2, 'in-degree': 5}), ('f', {'passerby': 1, 'in-degree': 0})]
>>> edges before update [('a', 'b', {'weight': 1}), ('a', 'c', {'weight': 1}), ('b', 'c', {'weight': 2}), ('b', 'd', {'weight': 2}), ('b', 'e', {'weight': 2}), ('c', 'e', {'weight': 3})]
>>> nodes after update  [('a', {'passerby': 1, 'in-degree': 0}), ('b', {'passerby': 3, 'in-degree': 1}), ('c', {'passerby': 6, 'in-degree': 3}), ('d', {'passerby': 5, 'in-degree': 2}), ('e', {'passerby': 7, 'in-degree': 5}), ('f', {'passerby': 1, 'in-degree': 0})]
>>> edges after update  [('a', 'b', {'weight': 1}), ('a', 'c', {'weight': 1}), ('b', 'c', {'weight': 3}), ('b', 'd', {'weight': 3}), ('b', 'e', {'weight': 3}), ('c', 'e', {'weight': 6})]

Not very optimized but seems to do the job as I understand it. The idea is to just count the difference between the incoming connections and initialize it with the original passerby values ​​and then keep updating based on the differences. I suppose you have another function for the walk-a-bout which might work together with adding the edgeweights here.

Hope this helps.

Leave a Comment