CODEWITHSUNDEEP
pythondictionarynetwork-programmingnetworkx
AwkwardAttempts
AwkwardAttempts

Reputation: 45

Find the shortest path length of a weighted graph in NetworkX

I am trying to use networkx to determine the shortest weighted path between a source and target node. For this I am using nx.shortest_path. However, I am unable to get it to function correctly.

The following resembles my setup:

import pandas as pd
import networkx as nx

df = pd.DataFrame({'F': ['a','b','c','d','d','e'], # f node identifier
                   'T': ['b','c','d','e','f','f'], # t node identifier
                   'weight': [1.2,5.2,2.7,2.8,1.3,7.4], # weight for shortest path algorithm
                   'dummy': ['q','w','e','r','t','y']}) # dummy variable

Network building occurs within a function as it will be applied to a few different datasets if I ever get it working! This is also why attributes are added as a dictionary rather than individually.

def build_network(df=None, column_names=None):
    g = nx.DiGraph()
    
    for i,row in df.iterrows():
          g.add_edge(row[column_names['F']],row[column_names['T']],attributes=row[column_names['attributes']].to_dict())
           
    return g

g = build_network(df, column_names={'F':'F',
                                    'T':'T',
                                    'attributes':['weight','dummy']})

Finally, the shortest_path_length algorithm is applied, which indicates the length is 2 (the number of edges), rather than 4.0 (the weighted distance). I suspect this is because I am referencing the weight attribute incorrectly. However, I am unsure how I should.

nx.shortest_path_length(G=g, source='c', target='f', weight="['attributes']['weight']")

Any help would be greatly appreciated!

Upvotes: 0

Views: 2585

Answers (1)

yatu
yatu

Reputation: 88226

You're overcomplicating the creating of the graph. You can use nx.from_pandas_edgelist to create the graph from the dataframe in a much simpler way (including the edge attributes) and find the shortest path length as:

G = nx.from_pandas_edgelist(df, source='F', target='T', edge_attr=['weight','dummy'], 
                            create_using=nx.DiGraph)

G.edges(data=True)
# EdgeDataView([('a', 'b', {'weight': 1.2, 'dummy': 'q'}), 
#               ('b', 'c', {'weight': 5.2, 'dummy': 'w'})...

nx.shortest_path_length(G, source='c', target='f', weight='weight')
# 4.0

Looking closer into your approach, the problem is how you are specifying the weight in nx.shortest_path_length. You're using "['attributes']['weight']", when the weight argument should be set to a string specifying the weight attribute name. So in you case, "weight".

Hence you're getting the same as:

nx.shortest_path_length(G=g, source='c', target='f', weight=None)
# 2

Whereas you should be doing as above:

nx.shortest_path_length(G, source='c', target='f', weight='weight')
# 4.0

Upvotes: 2

Related Questions