Enable plotting.
%matplotlib inline
Type whos in the code box below and press CTRL-ENTER.
whos
Import the NetworkX package.
import networkx as nx
Type nx. and press TAB to see what is inside the package.
Type nx.Graph and press SHIFT-TAB to see a tip.
nx.Graph()
Make an undirected graph.
graph = nx.Graph()
Type graph. and press TAB to see what you can do with it.
Type graph.add_edge? and press CTRL-ENTER to see the function's documentation. Press ESC to exit.
Type graph.add_edge?? and press CTRL-ENTER to see the function's source code. Press ESC to exit.
Add edges.
graph.add_edge('Brooklyn Bridge', 'Union Square', duration=10)
graph.add_edge('Union Square', 'Grand Central', duration=10)
graph.add_edge('Grand Central', 'Times Square', duration=5)
graph.add_edge('Penn Station', 'Times Square', duration=5)
graph.add_edge('Times Square', '72nd Street and Broadway', duration=10)
graph.add_edge('72nd Street and Broadway', '96th Street and Broadway', duration=10)
graph.add_edge('Grand Central', '86th Street and Lexington', duration=10)
Draw it.
nx.draw(graph)
Find the fastest path from Brooklyn Bridge to 96th Street and Broadway using the Dijkstra algorithm.
nx.dijkstra_path(graph, 'Brooklyn Bridge', '96th Street and Broadway', weight='duration')
Ask how many minutes it will take.
nx.dijkstra_path_length(graph, 'Brooklyn Bridge', '96th Street and Broadway', weight='duration')
Find the fastest path from Union Square to Penn Station using the A* algorithm.
nx.astar_path(graph, 'Brooklyn Bridge', '96th Street and Broadway', weight='duration')
Compare algorithm speed.
%timeit nx.dijkstra_path(graph, 'Brooklyn Bridge', '96th Street and Broadway', weight='duration')
%timeit nx.astar_path(graph, 'Brooklyn Bridge', '96th Street and Broadway', weight='duration')
Show stations with more than two connections.
[node for node, connection_count in nx.degree(graph).items() if connection_count > 2]
Look at the list of shortest path algorithms on the NetworkX algorithms page.