Customization Networkx Short Path Weight Function

Question

I'm doing a simulation experiment on pedestrian wayfinding. First, I used networkx to create a Graph with some nodes and edges. Each node represents an intersection and the node has the attribute "passerby" which represents the number of people at the current intersection. Now, given a starting node and a target node, I need to find out the shortest path from the starting node to the target node, where the value of the cost on the road is the passerby value of the starting node, and every passerby will walk along the shortest route, which means the passerby value of the next node will increase. How should I define the weight function? Below is code:

import networkx as nx

G = nx.Graph()
G.add_nodes_from(['a', 'b', 'c', 'd', 'e', 'f'], passerby=[1, 2, 3, 3, 2, 1])
G.add_edge('a', 'b')
G.add_edge('a', 'c')
G.add_edge('b', 'c')
G.add_edge('b', 'd')
G.add_edge('c', 'e')
G.add_edge('b', 'e')


def weight():
    pass


route = nx.shortest_path(G, 'a', 'f', weight=weight)

Answer 1

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
    weights.append(G1.nodes[edge[0]]['passerby'])
    
# 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:

G.nodes(data=True)
>>> NodeDataView({'a': {'passerby': 1}, 'b': {'passerby': 2}, 'c': {'passerby': 3}, 'd': {'passerby': 3}, 'e': {'passerby': 2}, 'f': {'passerby': 1}})

G.edges(data=True)
>>> 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')
print(route)
>>> ['a', 'b', 'e']

print(nx.info(G))
print(nx.info(G1))
>>> DiGraph with 6 nodes and 0 edges
>>> DiGraph with 6 nodes and 6 edges

print(G.nodes(data=True))
print(G1.nodes(data=True))
>>> [('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$

    Parameters
    ----------
    G_ : nx.DiGraph
        DiGraph from t-1
    G1_ : nx.DiGraph
        Raw DiGraph from t before updating weights

    Returns
    -------
    G1_ : 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
        else:
            pass
    
    updated = []
    
    # Loop over the updated passerby values and update weights again
    for edge in G1_.edges(data=True):
        # Append updated weight
        updated.append(G1_.nodes[edge[0]]['passerby'])
    
    # 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 outputs:

>>> 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.