📚 The CoCalc Library - books, templates and other resources

cocalc-examples / think-complexity-2ed / soln / chap03soln.ipynb

¹³²⁹²³ views
License: OTHER

Kernel: Python 3

Small World Graphs

Code examples from Think Complexity, 2nd edition.

In [1]:

%matplotlib inline

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
import seaborn as sns

from utils import decorate, savefig

# I set the random seed so the notebook 
# produces the same results every time.
np.random.seed(17)

# TODO: remove this when NetworkX is fixed
from warnings import simplefilter
import matplotlib.cbook
simplefilter("ignore", matplotlib.cbook.mplDeprecation)

In [2]:

# node colors for drawing networks
colors = sns.color_palette('pastel', 5)
#sns.palplot(colors)
sns.set_palette(colors)

Regular ring lattice

To make a ring lattice, I'll start with a generator function that yields edges between each node and the next halfk neighbors.

In [3]:

def adjacent_edges(nodes, halfk):
    """Yields edges between each node and `halfk` neighbors.
    
    halfk: number of edges from each node
    """
    n = len(nodes)
    for i, u in enumerate(nodes):
        for j in range(i+1, i+halfk+1):
            v = nodes[j % n]
            yield u, v

We can test it with 3 nodes and halfk=1

In [4]:

nodes = range(3)
for edge in adjacent_edges(nodes, 1):
    print(edge)

Out[4]:

(0, 1)
(1, 2)
(2, 0)

Now we use adjacent_edges to write make_ring_lattice

In [5]:

def make_ring_lattice(n, k):
    """Makes a ring lattice with `n` nodes and degree `k`.
    
    Note: this only works correctly if k is even.
    
    n: number of nodes
    k: degree of each node
    """
    G = nx.Graph()
    nodes = range(n)
    G.add_nodes_from(nodes)
    G.add_edges_from(adjacent_edges(nodes, k//2))
    return G

And we can test it out with n=10 and k=4

In [6]:

lattice = make_ring_lattice(10, 4)

In [7]:

nx.draw_circular(lattice, 
                 node_color='C0', 
                 node_size=1000, 
                 with_labels=True)

savefig('figs/chap03-1')

Out[7]:

Saving figure to file figs/chap03-1

Exercise: To see how this function fails when k is odd, run it again with k=3 or k=5.

WS graph

To make a WS graph, you start with a ring lattice and then rewire.

In [8]:

def make_ws_graph(n, k, p):
    """Makes a Watts-Strogatz graph.
    
    n: number of nodes
    k: degree of each node
    p: probability of rewiring an edge
    """
    ws = make_ring_lattice(n, k)
    rewire(ws, p)
    return ws

Here's the function that does the rewiring

In [9]:

def rewire(G, p):
    """Rewires each edge with probability `p`.
    
    G: Graph
    p: float
    """
    nodes = set(G)
    for u, v in G.edges():
        if flip(p):
            choices = nodes - {u} - set(G[u])
            new_v = np.random.choice(list(choices))
            G.remove_edge(u, v)
            G.add_edge(u, new_v)
            
def flip(p):
    """Returns True with probability `p`."""
    return np.random.random() < p

Here's an example with p=0.2

In [10]:

ws = make_ws_graph(10, 4, 0.2)
nx.draw_circular(ws, 
                 node_color='C1', 
                 node_size=1000, 
                 with_labels=True)

Out[10]:

Just checking that we have the same number of edges we started with:

In [11]:

len(lattice.edges()), len(ws.edges())

Out[11]:

(20, 20)

Now I'll generate a plot that shows WS graphs for a few values of p

In [12]:

n = 10
k = 4
ns = 100

plt.subplot(1,3,1)
ws = make_ws_graph(n, k, 0)
nx.draw_circular(ws, node_size=ns)
plt.axis('equal')

plt.subplot(1,3,2)
ws = make_ws_graph(n, k, 0.2)
nx.draw_circular(ws, node_size=ns)
plt.axis('equal')

plt.subplot(1,3,3)
ws = make_ws_graph(n, k, 1.0)
nx.draw_circular(ws, node_size=ns)
plt.axis('equal')

#TODO: Set figure size
savefig('figs/chap03-2')

Out[12]:

Saving figure to file figs/chap03-2

Exercise: What is the order of growth of rewire?

In [13]:

# Solution

"""The loop executes once for each edge.  Inside the loop, everything is constant
time except computing `choices`, which is linear in `n`.  So the total run time is 
`O(nm)`.""";

Clustering

The following function computes the local clustering coefficient for a given node, u:

In [14]:

def node_clustering(G, u):
    """Computes local clustering coefficient for `u`.
    
    G: Graph
    u: node
    
    returns: float
    """
    neighbors = G[u]
    k = len(neighbors)
    if k < 2:
        return np.nan
        
    possible = k * (k-1) / 2
    exist = 0    
    for v, w in all_pairs(neighbors):
        if G.has_edge(v, w):
            exist +=1
    return exist / possible

def all_pairs(nodes):
    """Generates all pairs of nodes."""
    for i, u in enumerate(nodes):
        for j, v in enumerate(nodes):
            if i < j:
                yield u, v

The network average clustering coefficient is just the mean of the local CCs.

In [15]:

def clustering_coefficient(G):
    """Average of the local clustering coefficients.
    
    G: Graph
    
    returns: float
    """
    cu = [node_clustering(G, node) for node in G]
    return np.nanmean(cu)

In a ring lattice with k=4, the clustering coefficient for each node should be 0.5

In [16]:

lattice = make_ring_lattice(10, 4)
node_clustering(lattice, 1)

Out[16]:

0.5

And the network average should be 0.5

In [17]:

clustering_coefficient(lattice)

Out[17]:

0.5

Correct.

In [18]:

%timeit clustering_coefficient(lattice)

Out[18]:

107 µs ± 887 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Exercise: Write a version of node_clustering that replaces the for loop with a list comprehension. Is it faster?

In [19]:

# Solution

def node_clustering(G, u):
    neighbors = G[u]
    k = len(neighbors)
    if k < 2:
        return np.nan
        
    edges = [G.has_edge(v, w) for v, w in all_pairs(neighbors)]
    return np.mean(edges)

clustering_coefficient(lattice)

Out[19]:

0.5

In [20]:

%timeit clustering_coefficient(lattice)

Out[20]:

299 µs ± 7.61 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Exercise: What is the order of growth of clustering_coefficient in terms of n, m, and k?

In [21]:

# Solution

"""`clustering_coefficient` calls `node_clustering` once for each node.  
`node_clustering` is quadratic in `k`, the number of neighbors.

In a complete graph, `k = n-1`, so `node_clustering` is `O(n^2)` and 
`clustering_coefficient` is `O(n^3)`.

But in a ring lattice, or any other graph where `k` is not proportional to `n`, 
`clustering_coefficient` is `O(k^2 n)`.
""";

Path length

The following function computes path lengths between all pairs of nodes

In [22]:

def path_lengths(G):
    length_iter = nx.shortest_path_length(G)
    for source, dist_map in length_iter:
        for dest, dist in dist_map.items():
            yield dist

The characteristic path length is the mean path length for all pairs.

In [23]:

def characteristic_path_length(G):
    return np.mean(list(path_lengths(G)))

On a complete graph, the average path length should be 1

In [24]:

complete = nx.complete_graph(10)
characteristic_path_length(complete)

Out[24]:

0.9

On a ring lattice with n=1000 and k=10, the mean is about 50

In [25]:

lattice = make_ring_lattice(1000, 10)
characteristic_path_length(lattice)

Out[25]:

50.4

Exercise: What is the mean path length in a ring lattice with n=10 and k=4?

In [26]:

# Solution

lattice = make_ring_lattice(10, 4)
characteristic_path_length(lattice)

Out[26]:

1.5

The experiment

This function generates a WS graph with the given parameters and returns a pair of (mean path length, clustering coefficient):

In [27]:

def run_one_graph(n, k, p):
    """Makes a WS graph and computes its stats.
    
    n: number of nodes
    k: degree of each node
    p: probability of rewiring
    
    returns: tuple of (mean path length, clustering coefficient)
    """
    ws = make_ws_graph(n, k, p)    
    mpl = characteristic_path_length(ws)
    cc = clustering_coefficient(ws)
    print(mpl, cc)
    return mpl, cc

With n=1000 and k=10, it takes a few seconds on my computer:

In [28]:

%time run_one_graph(1000, 10, 0.01)

Out[28]:

8.162078 0.6428959595959596
CPU times: user 4.06 s, sys: 0 ns, total: 4.06 s
Wall time: 4.05 s

(8.162078, 0.6428959595959596)

Now we'll run it with a range of values for p.

In [29]:

ps = np.logspace(-4, 0, 9)
print(ps)

Out[29]:

[1.00000000e-04 3.16227766e-04 1.00000000e-03 3.16227766e-03
 1.00000000e-02 3.16227766e-02 1.00000000e-01 3.16227766e-01
 1.00000000e+00]

This function runs each value of p 20 times and returns a dictionary that maps from each p to a list of (mpl, cc) pairs.

In [30]:

def run_experiment(ps, n=1000, k=10, iters=20):
    """Computes stats for WS graphs with a range of `p`.
    
    ps: sequence of `p` to try
    n: number of nodes
    k: degree of each node
    iters: number of times to run for each `p`
    
    returns:
    """
    res = []
    for p in ps:
        print(p)
        t = [run_one_graph(n, k, p) for _ in range(iters)]
        means = np.array(t).mean(axis=0)
        print(means)
        res.append(means)
    return np.array(res)

Here are the raw results. Warning: this takes a few minutes to run.

In [31]:

%time res = run_experiment(ps)

Out[31]:

0001
57323 0.6662065656565656
4 0.6666666666666665
4 0.6666666666666665
339582 0.6662065656565656
4 0.6666666666666665
164194 0.6664232323232322
4 0.6666666666666665
967736 0.6661343434343433
016814 0.6662787878787878
4 0.6666666666666665
4 0.6666666666666665
4 0.6666666666666665
4 0.6666666666666665
767096 0.6656742424242422
91298 0.6659631313131312
208114 0.6661343434343433
4 0.6666666666666665
697288 0.6663510101010099
4 0.6666666666666665
4 0.6666666666666665
[47.1023517   0.66643528]
00031622776601683794
463862 0.6663510101010099
58725 0.6654252525252525
205762 0.665890909090909
609504 0.6653585858585858
489624 0.6660353535353534
631614 0.6656020202020202
650582 0.6662787878787878
419386 0.666179797979798
514678 0.6661075757575756
557846 0.6662787878787878
04731 0.6651484848484848
337198 0.6656020202020202
758942 0.6662787878787877
688598 0.6662787878787878
300572 0.6657464646464646
273246 0.6652863636363635
594396 0.6663510101010099
798952 0.6660353535353535
726948 0.6663510101010099
307492 0.66635101010101
[38.3981881   0.66594687]
001
552388 0.6645828282828281
769764 0.6648717171717171
18603 0.6633419191919191
80615 0.6644383838383837
802208 0.6634954545454546
963988 0.6629590909090909
51659 0.664970707070707
109694 0.6637348484848485
13038 0.6642939393939393
076 0.6658186868686867
848188 0.664240404040404
734808 0.6642671717171716
538652 0.6655030303030303
542386 0.6647272727272726
155594 0.6641227272727271
983918 0.6647994949494949
87073 0.6661343434343433
66691 0.6662065656565656
350184 0.6655752525252524
738948 0.6654080808080808
[27.6171755  0.6646746]
0031622776601683794
272672 0.6598944444444443
34433 0.66035101010101
578058 0.6614888888888888
711704 0.6581424242424241
136524 0.6592005050505051
30348 0.660730808080808
941544 0.6597222222222222
383178 0.6618666666666666
360688 0.6620429292929292
623272 0.6634080808080808
444884 0.6596454545454544
417036 0.6603722222222221
977442 0.6600151515151516
907122 0.6608525252525252
39333 0.6606050505050505
93532 0.6597459595959596
238748 0.6612388888888888
432526 0.6621186868686868
090436 0.6615974747474748
59943 0.6641949494949494
[16.0545862   0.66086172]
01
13664 0.6418499278499278
475946 0.6381155122655123
344462 0.6466026695526695
00073 0.6497444444444443
166168 0.6527138528138527
648424 0.6475435786435786
207154 0.6502984848484848
243344 0.6487505050505051
911388 0.648009163059163
066084 0.6420868686868687
41456 0.646054329004329
335748 0.6518338383838383
88653 0.651291847041847
479478 0.6496893939393938
010566 0.6428583694083694
608524 0.6474093795093795
2007 0.6478267676767677
34362 0.6493121212121211
159336 0.649133621933622
40576 0.6533761904761904
[8.9522581  0.64772504]
03162277660168379
048262 0.6134790043290043
10155 0.6154768231768232
357336 0.6179012265512265
167 0.613159163059163
896132 0.6024292929292929
32553 0.615318598068598
84725 0.6027877178377178
83052 0.6008812964812964
03765 0.6087532467532467
119854 0.612483116883117
106244 0.6089813131313131
985542 0.6066399045399046
951444 0.6105337662337662
135332 0.6111709956709956
167574 0.6127669552669552
743762 0.6029446442446442
926564 0.604659312909313
090104 0.6103888222888222
872004 0.6065657287157287
06414 0.6091246031746032
[6.0386897  0.60932228]
1
524346 0.505069302919303
468068 0.49751704961704957
583124 0.5121176268176268
491548 0.5012122544122545
50167 0.4967166056166055
503978 0.4999713675213675
52731 0.5046446109446109
468652 0.4995939449439449
479824 0.4962459595959596
446226 0.48976229326229326
542556 0.5045483627483627
41463 0.49021065601065605
62191 0.512448878898879
505932 0.49635845265845263
472522 0.49883646353646355
50645 0.501297952047952
442082 0.4858485958485959
546656 0.5078436174936174
459742 0.4952886224886225
46487 0.49769552669552664
[4.4986048  0.49966141]
31622776601683794
655612 0.2600498778998779
669992 0.2675819014319014
64657 0.2562733849483849
666938 0.26097005494505493
68846 0.2722830225330225
67202 0.26716233766233766
666396 0.2613013542013542
637664 0.2412051053521642
666666 0.2605679070929071
657766 0.26473909978909976
671978 0.2637997502497502
665552 0.25928273393273393
656404 0.25932069597069596
65933 0.2594986013986014
664362 0.26175901206636504
64668 0.2585398934398934
67281 0.2613041347541347
67608 0.2639866938616938
661836 0.2576614607614608
666236 0.26394777999778
[3.6634676  0.26106174]
0
264956 0.012826835367934438
26303 0.013843647211062073
263122 0.013904749319266002
266104 0.014088157234012067
26777 0.014267722559518227
26246640788295 0.013364616288592897
264642 0.013981335833387105
264526 0.014243496518960914
263098 0.012831131659803083
261476 0.01107101661668225
262692 0.012861808126514008
262998 0.013477745641488332
262246 0.013962687329822131
26699 0.013954945922670381
259644 0.012913516815142202
264004 0.013832632121994756
269998 0.013472386230900163
265248 0.014079368816597916
266862 0.013204454028327437
266988 0.013973989443648884
[3.26444302 0.01350781]
CPU times: user 12min 52s, sys: 468 ms, total: 12min 52s
Wall time: 12min 52s

In [32]:

res

Out[32]:

array([[4.71023517e+01, 6.66435278e-01],
       [3.83981881e+01, 6.65946869e-01],
       [2.76171755e+01, 6.64674596e-01],
       [1.60545862e+01, 6.60861717e-01],
       [8.95225810e+00, 6.47725043e-01],
       [6.03868970e+00, 6.09322277e-01],
       [4.49860480e+00, 4.99661407e-01],
       [3.66346760e+00, 2.61061740e-01],
       [3.26444302e+00, 1.35078122e-02]])

Let's get the results into a form that's easy to plot.

In [33]:

L, C = np.transpose(res)

In [34]:

Out[34]:

array([47.1023517 , 38.3981881 , 27.6171755 , 16.0545862 ,  8.9522581 ,
        6.0386897 ,  4.4986048 ,  3.6634676 ,  3.26444302])

In [35]:

Out[35]:

array([0.66643528, 0.66594687, 0.6646746 , 0.66086172, 0.64772504,
       0.60932228, 0.49966141, 0.26106174, 0.01350781])

And normalize them so they both start at 1.0

In [36]:

L /= L[0]
C /= C[0]

Here's the plot that replicates Watts and Strogatz's Figure 2.

In [37]:

plt.plot(ps, C, 's-', linewidth=1, label='C(p) / C(0)')
plt.plot(ps, L, 'o-', linewidth=1, label='L(p) / L(0)')
decorate(xlabel='Rewiring probability (p)', xscale='log',
         title='Normalized clustering coefficient and path length',
         xlim=[0.00009, 1.1], ylim=[-0.01, 1.01])

savefig('figs/chap03-3')

Out[37]:

Saving figure to file figs/chap03-3

Breadth-first search

Now let's see how the shortest path algorithm works. We'll start with BFS, which is the basis for Dijkstra's algorithm.

Here's our old friend, the ring lattice:

In [38]:

lattice = make_ring_lattice(10, 4)

In [39]:

nx.draw_circular(lattice, 
                 node_color='C2', 
                 node_size=1000, 
                 with_labels=True)

Out[39]:

And here's my implementation of BFS using a deque.

In [40]:

from collections import deque

def reachable_nodes_bfs(G, start):
    """Finds reachable nodes by BFS.
    
    G: graph
    start: node to start at
    
    returns: set of reachable nodes
    """
    seen = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in seen:
            seen.add(node)
            queue.extend(G.neighbors(node))
    return seen

It works:

In [41]:

reachable_nodes_bfs(lattice, 0)

Out[41]:

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Here's a version that's a little faster, but maybe less readable.

In [42]:

def reachable_nodes_bfs(G, start):
    """Finds reachable nodes by BFS.
    
    G: graph
    start: node to start at
    
    returns: set of reachable nodes
    """
    seen = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in seen:
            seen.add(node)
            neighbors = set(G[node]) - seen
            queue.extend(neighbors)
    return seen

It works, too.

In [43]:

reachable_nodes_bfs(lattice, 0)

Out[43]:

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Dijkstra's algorithm

Now we're ready for Dijkstra's algorithm, at least for graphs where all the edges have the same weight/length.

In [44]:

def shortest_path_dijkstra(G, source):
    """Finds shortest paths from `source` to all other nodes.
    
    G: graph
    source: node to start at
    
    returns: make from node to path length
    """
    dist = {source: 0}
    queue = deque([source])
    while queue:
        node = queue.popleft()
        new_dist = dist[node] + 1

        neighbors = set(G[node]).difference(dist)
        for n in neighbors:
            dist[n] = new_dist
        
        queue.extend(neighbors)
    return dist

Again, we'll test it on a ring lattice.

In [45]:

lattice = make_ring_lattice(10, 4)

In [46]:

nx.draw_circular(lattice, 
                 node_color='C3', 
                 node_size=1000, 
                 with_labels=True)

Out[46]:

Here's my implementation:

In [47]:

d1 = shortest_path_dijkstra(lattice, 0)
d1

Out[47]:

{0: 0, 8: 1, 1: 1, 2: 1, 9: 1, 6: 2, 7: 2, 3: 2, 4: 2, 5: 3}

And here's the result from NetworkX:

In [48]:

d2 = nx.shortest_path_length(lattice, 0)
d2

Out[48]:

{0: 0, 1: 1, 2: 1, 8: 1, 9: 1, 3: 2, 4: 2, 6: 2, 7: 2, 5: 3}

They are the same:

In [49]:

d1 == d2

Out[49]:

True

Exercise: In a ring lattice with n=1000 and k=10, which node is farthest from 0 and how far is it? Use shortest_path_dijkstra to check your answer.

Note: the maximum distance between two nodes is the diameter of the graph.

In [50]:

# Solution

lattice = make_ring_lattice(1000, 10)
d = shortest_path_dijkstra(lattice, 0)

from operator import itemgetter
node, dist = sorted(d.items(), key=itemgetter(1))[-1]
node, dist

Out[50]:

(501, 100)

Exercises

Exercise: In a ring lattice, every node has the same number of neighbors. The number of neighbors is called the degree of the node, and a graph where all nodes have the same degree is called a regular graph.

All ring lattices are regular, but not all regular graphs are ring lattices. In particular, if k is odd, we can't construct a ring lattice, but we might be able to construct a regular graph.

Write a function called make_regular_graph that takes n and k and returns a regular graph that contains n nodes, where every node has k neighbors. If it's not possible to make a regular graph with the given values of n and k, the function should raise a ValueError.

In [51]:

# Solution

# Here's `adjacent_edges` again for comparison:

def adjacent_edges(nodes, halfk):
    n = len(nodes)
    for i, u in enumerate(nodes):
        for j in range(i+1, i+halfk+1):
            v = nodes[j % n]
            yield u, v

In [52]:

# Solution

# And here's a function that computes edges that connect each
# node to the one half-way around the circle

def opposite_edges(nodes):
    """Enumerates edges that connect opposite nodes."""
    n = len(nodes)
    for i, u in enumerate(nodes):
        j = i + n//2
        v = nodes[j % n]
        yield u, v

In [53]:

# Solution

# Now we can make regular graphs.

def make_regular_graph(n, k):
    """Makes graph with `n` nodes where all nodes have `k` neighbors.
    
    Not possible if both `n` and `k` are odd.
    """
    # a is the number of adjacent edges
    # b is the number of opposite edges (0 or 1)
    a, b = divmod(k, 2)
    
    G = nx.Graph()
    nodes = range(n)
    G.add_nodes_from(nodes)
    G.add_edges_from(adjacent_edges(nodes, a))
    
    # if k is odd, add opposite edges
    if b:
        if n%2:
            msg = "Can't make a regular graph if n and k are odd."
            raise ValueError(msg)
        G.add_edges_from(opposite_edges(nodes))
    return G

In [54]:

# Solution

# Here's an example.

regular = make_regular_graph(10, 3)

nx.draw_circular(regular, 
                 node_color='C4', 
                 node_size=1000, 
                 with_labels=True)

Out[54]:

Exercise: My implementation of reachable_nodes_bfs is efficient in the sense that it is in $O(n + m)$ , but it incurs a lot of overhead adding nodes to the queue and removing them. NetworkX provides a simple, fast implementation of BFS, available from the NetworkX repository on GitHub.

Here is a version I modified to return a set of nodes:

In [55]:

def plain_bfs(G, start):
    """A fast BFS node generator"""
    seen = set()
    nextlevel = {start}
    while nextlevel:
        thislevel = nextlevel
        nextlevel = set()
        for v in thislevel:
            if v not in seen:
                seen.add(v)
                nextlevel.update(G[v])
    return seen

Compare this function to reachable_nodes_bfs and see which is faster. Then see if you can modify this function to implement a faster version of shortest_path_dijkstra

In [56]:

# Solution

lattice = make_ring_lattice(1000, 10)

In [57]:

# Solution

%timeit len(reachable_nodes_bfs(lattice, 0))

Out[57]:

2.33 ms ± 59.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [58]:

# Solution

%timeit len(plain_bfs(lattice, 0))

Out[58]:

1.5 ms ± 3.66 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [59]:

# Solution

#The version from NetworkX is faster.

#Here's a version of Dijkstra's algorithm that works the same way:

def plain_shortest_path(G, source):
    """A fast version of Dijkstra's algorithm for equal edges."""
    new_dist = 0
    dist = {}
    nextlevel = {source}
    while nextlevel:
        thislevel = nextlevel
        nextlevel = set()
        for v in thislevel:
            if v not in dist:
                dist[v] = new_dist
                nextlevel.update(G[v])
        new_dist += 1
    return dist

In [60]:

# Solution

#It gets the right answers

lattice = make_ring_lattice(1000, 10)
d1 = shortest_path_dijkstra(lattice, 0)
d2 = plain_shortest_path(lattice, 0)
d1 == d2

Out[60]:

True

In [61]:

# Solution

# And it is substantually faster than the version that uses a deque.

%timeit shortest_path_dijkstra(lattice, 0)

Out[61]:

2.1 ms ± 89.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [62]:

# Solution

%timeit plain_shortest_path(lattice, 0)

Out[62]:

1.51 ms ± 9.93 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [63]:

# Solution

%timeit nx.shortest_path_length(lattice, 0)

Out[63]:

3.7 ms ± 49.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Exercise: The following implementation of a BFS contains two performance errors. What are they? What is the actual order of growth for this algorithm?

In [64]:

def bfs(G, start):
    """Breadth-first search on a graph, starting at top_node."""
    visited = set()
    queue = [start]
    while len(queue):
        curr_node = queue.pop(0)    # Dequeue
        visited.add(curr_node)

        # Enqueue non-visited and non-enqueued children
        queue.extend(c for c in G[curr_node]
                     if c not in visited and c not in queue)
    return visited

In [65]:

# Solution

"""The first performance error is using `pop(0)` on a list, which is linear in
the length of the list.  The second error is checking whether the children are 
in queue, which is also linear in the length of the list.  In the worst case, 
a completely connected graph, the queue loop runs `n` times, and each time we 
have to check `n` nodes to see if they are in a list with `n` elements, so the 
total run time is `O(n^3)`, which is really terrible.

By the way, I did not make this example up.  It used to be on 
[the Wikipedia page for BFS](https://en.wikipedia.org/wiki/Breadth-first_search).
In fact, if you search the Internet for Python implementations of BFS, many of 
them contain at least one performance error.
"""
None

Exercise: In the book, I claimed that Dijkstra's algorithm does not work unless it uses BFS. Write a version of shortest_path_dijkstra that uses DFS and test it on a few examples to see what goes wrong.

In [66]:

# Solution

# Here's the broken version:

def shortest_path_dfs(G, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.pop()
        new_dist = dist[node] + 1

        neighbors = set(G[node]).difference(dist)
        for n in neighbors:
            dist[n] = new_dist
        
        queue.extend(neighbors)
    return dist

#Sure enough, it gets the answers wrong

lattice = make_ring_lattice(10, 4)
d1 = shortest_path_dfs(lattice, 0)
print(d1)
d2 = nx.shortest_path_length(lattice, 0)
print(d2)
d1 == d2

Out[66]:

{0: 0, 8: 1, 1: 1, 2: 1, 9: 1, 7: 2, 5: 3, 6: 3, 4: 4, 3: 5}
{0: 0, 1: 1, 2: 1, 8: 1, 9: 1, 3: 2, 4: 2, 6: 2, 7: 2, 5: 3}

False