CODEWITHSUNDEEP
pythonnetworkx
Michael Millman
Michael Millman

Reputation: 81

Edge attributes of shortest path using networkx

I’m trying to use networkx to calculate the shortest path between two nodes. For example:

paths = nx.shortest_path(G, ‘A’, ‘C’, weight=‘cost’)

paths would return something like: [‘A’, ‘B’, ‘C’]

nx.shortest_path_length() returns the cost of that path, which is also helpful. However, I would like to return a list of the edges traversed for this path as well. Within those edges are other attributes I’ve stored that I’d like to return.

Is this possible?

Upvotes: 8

Views: 5786

Answers (3)

Aaron Bramson
Aaron Bramson

Reputation: 1288

It maybe be faster with a list comprehension, which seems similar to Vitaly's solution:

First, using the same setup as swatchai:

# Create a random graph with 8 nodes, with degree=3
G = nx.random_regular_graph(3, 8, seed=None)
# Add 'cost' attributes to the edges
for (start, end) in G.edges:
    G.edges[start, end]['att'] = np.random.randint(1,10)

# Find the shortest path from 0 to 7, use 'cost' as weight
pth = nx.shortest_path(G, source=0, target=7, weight='att')

Then you can get a list of whatever edge attributes you need by iterating over sequential pairs of nodes in the path list.

edgeAttrList = [G[pth[i]][pth[i+1]]['att'] for i in range(len(pth[:-1]))]

A slightly more elegant way to do the same thing is:

edgeAttrList = [G[u][v]['att'] for u,v in zip(pth,pth[1:])]

If there is a chance that some nodes on the path don't have the attribute you are looking for, then you can use this to return defVal instead of breaking.

edgeAttrList = [G[u][v].get('att', defVal) for u,v in zip(pth,pth[1:])]

Or you can filter out such cases:

edgeAttrList = [G[u][v].get('att') for u,v in zip(pth,pth[1:]) if G[u][v].get('att','foo') != 'foo']

Upvotes: 0

Vitaly Tregubov
Vitaly Tregubov

Reputation: 41

The script allows you to get a list of attributes of visited edges

import networkx as nx
import matplotlib.pyplot as plt

Nodes = [('A', 'B'),('A', 'C'), ('C', 'D'), ('D', 'B'), ('C', 'B')]

G = nx.Graph()
num = 1 #name edge
for node in Nodes:
    G.add_edge(*node, num = num, weight = 1)
    num += 1

pos = nx.spring_layout(G)
edge_labels = nx.get_edge_attributes(G, 'num')
nx.draw(G,  with_labels=True, node_color='skyblue', pos=pos)
nx.draw_networkx_edge_labels(G, pos, edge_labels = edge_labels, font_color='red')
plt.show()

path = nx.shortest_path(G)
st = 'A' #start node
end = 'D' #end node
path_edges = [edge_labels.get(x, edge_labels.get((x[1],x[0]))) for x in zip(path[st][end], path[st][end][1:])]
print('Path by nodes: ', path[st][end])
print('Path by edges: ', path_edges)

Upvotes: 0

swatchai
swatchai

Reputation: 18762

Here is a code that does all you need (hopefully :p):

import numpy as np
# import matplotlib.pyplot as plt
import networkx as nx

# Create a random graph with 8 nodes, with degree=3
G = nx.random_regular_graph(3, 8, seed=None)

# Add 'cost' attributes to the edges
for (start, end) in G.edges:
    G.edges[start, end]['cost'] = np.random.randint(1,10)

# Find the shortest path from 0 to 7, use 'cost' as weight
sp = nx.shortest_path(G, source=0, target=7, weight='cost')
print("Shortest path: ", sp)

# Create a graph from 'sp'
pathGraph = nx.path_graph(sp)  # does not pass edges attributes

# Read attributes from each edge
for ea in pathGraph.edges():
    #print from_node, to_node, edge's attributes
    print(ea, G.edges[ea[0], ea[1]])

The output will look similar to this:

Shortest path:  [0, 5, 7]
(0, 5) {'cost': 2}
(5, 7) {'cost': 3}

Upvotes: 8

Related Questions