Introduction to Computational Analysis




Pay Notebook Creator: Roy Hyunjin Han0
Set Container: Numerical CPU with TINY Memory for 10 Minutes 0
Total0

Enable plotting.

In [ ]:
%matplotlib inline
  1. Browse the NetworkX Example Gallery.
  2. Click on an example you like.
  3. Cut and past the code from the example in the cell below and press CTRL-ENTER.

Type whos in the code box below and press CTRL-ENTER.

In [ ]:
whos

Import the NetworkX package.

In [ ]:
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.

In [ ]:
nx.Graph()

Make an undirected graph.

In [ ]:
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.

In [ ]:
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.

In [ ]:
nx.draw(graph)

Find the fastest path from Brooklyn Bridge to 96th Street and Broadway using the Dijkstra algorithm.

In [ ]:
nx.dijkstra_path(graph, 'Brooklyn Bridge', '96th Street and Broadway', weight='duration')

Ask how many minutes it will take.

In [ ]:
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.

In [ ]:
nx.astar_path(graph, 'Brooklyn Bridge', '96th Street and Broadway', weight='duration')

Compare algorithm speed.

In [ ]:
%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.

In [ ]:
[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.