Exercises Notebook

Converted from exercises.ipynb for web reading.

Graph Basics - Exercises

This notebook contains 10 progressive exercises for 01-Graph-Basics. Each exercise has a learner workspace followed by a complete reference solution. The examples emphasize graph math used in retrieval, GNNs, spectral methods, and network analysis.

Code cell 2

import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl

try:
    import seaborn as sns
    sns.set_theme(style="whitegrid", palette="colorblind")
    HAS_SNS = True
except ImportError:
    plt.style.use("seaborn-v0_8-whitegrid")
    HAS_SNS = False

mpl.rcParams.update({
    "figure.figsize":    (10, 6),
    "figure.dpi":         120,
    "font.size":           13,
    "axes.titlesize":      15,
    "axes.labelsize":      13,
    "xtick.labelsize":     11,
    "ytick.labelsize":     11,
    "legend.fontsize":     11,
    "legend.framealpha":   0.85,
    "lines.linewidth":      2.0,
    "axes.spines.top":     False,
    "axes.spines.right":   False,
    "savefig.bbox":       "tight",
    "savefig.dpi":         150,
})
np.random.seed(42)
print("Plot setup complete.")

Code cell 3

import numpy as np
import numpy.linalg as la
from collections import deque, defaultdict
import heapq

np.set_printoptions(precision=8, suppress=True)
np.random.seed(42)

def header(title):
    print("\n" + "=" * len(title))
    print(title)
    print("=" * len(title))

def check_true(name, cond):
    ok=bool(cond)
    print(f"{'PASS' if ok else 'FAIL'} - {name}")
    return ok

def check_close(name, got, expected, tol=1e-8):
    ok=np.allclose(got, expected, atol=tol, rtol=tol)
    print(f"{'PASS' if ok else 'FAIL'} - {name}")
    if not ok:
        print('  got     =', got)
        print('  expected=', expected)
    return ok

def adj_from_edges(n, edges, directed=False, weighted=False):
    A=np.zeros((n,n), dtype=float)
    for e in edges:
        if weighted:
            u,v,w=e
        else:
            u,v=e; w=1.0
        A[u,v]=w
        if not directed: A[v,u]=w
    return A

def components(A):
    n=A.shape[0]; seen=set(); comps=[]
    for s in range(n):
        if s in seen: continue
        q=deque([s]); seen.add(s); comp=[]
        while q:
            u=q.popleft(); comp.append(u)
            for v in np.flatnonzero(A[u]):
                if int(v) not in seen:
                    seen.add(int(v)); q.append(int(v))
        comps.append(comp)
    return comps

def laplacian(A):
    return np.diag(A.sum(axis=1))-A

def softmax(x):
    x=np.asarray(x,float); e=np.exp(x-x.max()); return e/e.sum()

print("Chapter 11 helper setup complete.")

Exercise 1: Build an Adjacency Matrix

Create an undirected graph from an edge list.

Code cell 5

# Your Solution
# Exercise 1 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 1.")

Code cell 6

# Solution
# Exercise 1 - Build an Adjacency Matrix
header("Exercise 1: adjacency matrix")
edges=[(0,1),(1,2),(2,3),(3,0),(1,3)]
A=adj_from_edges(4,edges)
print(A)
check_close("symmetric", A, A.T)
check_close("edge count", A.sum()/2, len(edges))

Exercise 2: Degrees and Handshaking

Verify $\sum_v d_v=2|E|$.

Code cell 8

# Your Solution
# Exercise 2 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 2.")

Code cell 9

# Solution
# Exercise 2 - Degrees and Handshaking
header("Exercise 2: degrees")
A=adj_from_edges(5,[(0,1),(0,2),(2,3),(3,4)])
deg=A.sum(axis=1)
print("degrees", deg)
check_close("handshaking", deg.sum(), 2*4)

Exercise 3: Paths and Walks

Count length-2 walks using $A^2$.

Code cell 11

# Your Solution
# Exercise 3 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 3.")

Code cell 12

# Solution
# Exercise 3 - Paths and Walks
header("Exercise 3: walks")
A=adj_from_edges(4,[(0,1),(1,2),(2,3),(0,3)])
A2=A@A
print("A^2\n",A2)
check_close("two walks from 0 to 2", A2[0,2], 2)

Exercise 4: Connected Components

Find components by BFS.

Code cell 14

# Your Solution
# Exercise 4 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 4.")

Code cell 15

# Solution
# Exercise 4 - Connected Components
header("Exercise 4: components")
A=adj_from_edges(6,[(0,1),(1,2),(3,4)])
comps=components(A)
print(comps)
check_true("three components", sorted(len(c) for c in comps)==[1,2,3])

Exercise 5: BFS Distances

Compute unweighted shortest-path distances from a source.

Code cell 17

# Your Solution
# Exercise 5 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 5.")

Code cell 18

# Solution
# Exercise 5 - BFS Distances
header("Exercise 5: BFS distances")
A=adj_from_edges(5,[(0,1),(1,2),(0,3),(3,4),(4,2)])
dist=np.full(5,np.inf); dist[0]=0; q=deque([0])
while q:
    u=q.popleft()
    for v in np.flatnonzero(A[u]):
        if np.isinf(dist[v]): dist[v]=dist[u]+1; q.append(int(v))
print(dist)
check_close("distance to 2", dist[2], 2)

Exercise 6: Graph Density

Compute density $2|E|/(n(n-1))$.

Code cell 20

# Your Solution
# Exercise 6 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 6.")

Code cell 21

# Solution
# Exercise 6 - Graph Density
header("Exercise 6: density")
n=5; edges=[(0,1),(1,2),(2,3),(3,4)]
density=2*len(edges)/(n*(n-1))
check_close("density", density, 0.4)

Exercise 7: Bipartite Check

Color a graph with two colors or detect failure.

Code cell 23

# Your Solution
# Exercise 7 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 7.")

Code cell 24

# Solution
# Exercise 7 - Bipartite Check
header("Exercise 7: bipartite")
A=adj_from_edges(4,[(0,1),(1,2),(2,3)])
color={0:0}; q=deque([0]); ok=True
while q:
    u=q.popleft()
    for v in np.flatnonzero(A[u]):
        v=int(v)
        if v not in color: color[v]=1-color[u]; q.append(v)
        elif color[v]==color[u]: ok=False
print(color)
check_true("path graph bipartite", ok)

Exercise 8: Triangle Count

Count triangles with $\operatorname{tr}(A^3)/6$.

Code cell 26

# Your Solution
# Exercise 8 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 8.")

Code cell 27

# Solution
# Exercise 8 - Triangle Count
header("Exercise 8: triangles")
A=adj_from_edges(4,[(0,1),(1,2),(2,0),(2,3)])
tri=np.trace(la.matrix_power(A,3))/6
print("triangles", tri)
check_close("one triangle", tri, 1)

Exercise 9: Local Clustering

Compute clustering coefficient for a node.

Code cell 29

# Your Solution
# Exercise 9 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 9.")

Code cell 30

# Solution
# Exercise 9 - Local Clustering
header("Exercise 9: clustering")
A=adj_from_edges(4,[(0,1),(0,2),(0,3),(1,2)])
neigh=np.flatnonzero(A[0]); sub=A[np.ix_(neigh,neigh)]
actual=sub.sum()/2; possible=len(neigh)*(len(neigh)-1)/2
c=actual/possible
print("clustering", c)
check_close("one of three neighbor edges", c, 1/3)

Exercise 10: Directed In and Out Degree

Compute in/out degrees for a directed graph.

Code cell 32

# Your Solution
# Exercise 10 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 10.")

Code cell 33

# Solution
# Exercise 10 - Directed In and Out Degree
header("Exercise 10: directed degrees")
A=adj_from_edges(4,[(0,1),(0,2),(2,1),(3,2)],directed=True)
out=A.sum(axis=1); inn=A.sum(axis=0)
print("out",out,"in",inn)
check_close("edge count", out.sum(), inn.sum())