Exercises Notebook

Converted from exercises.ipynb for web reading.

Graph Representations - Exercises

This notebook contains 10 progressive exercises for 02-Graph-Representations. 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: Adjacency List Conversion

Convert an adjacency matrix to adjacency lists.

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 - Adjacency List Conversion
header("Exercise 1: adjacency list")
A=adj_from_edges(4,[(0,1),(0,2),(2,3)])
adj={i:list(map(int,np.flatnonzero(A[i]))) for i in range(4)}
print(adj)
check_true("neighbors of 0", set(adj[0])=={1,2})

Exercise 2: Edge List Conversion

Recover edges from an undirected adjacency matrix.

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 - Edge List Conversion
header("Exercise 2: edge list")
A=adj_from_edges(4,[(0,1),(1,3),(2,3)])
edges=[(i,j) for i in range(4) for j in range(i+1,4) if A[i,j]]
print(edges)
check_true("edge set", set(edges)=={(0,1),(1,3),(2,3)})

Exercise 3: Weighted Directed Matrix

Represent weighted directed edges.

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 - Weighted Directed Matrix
header("Exercise 3: weighted directed")
A=adj_from_edges(3,[(0,1,0.5),(1,2,2.0),(2,0,1.5)],directed=True,weighted=True)
print(A)
check_close("weight 1->2", A[1,2], 2.0)
check_true("not symmetric", not np.allclose(A,A.T))

Exercise 4: Incidence Matrix

Build an oriented incidence matrix $B$.

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 - Incidence Matrix
header("Exercise 4: incidence")
edges=[(0,1),(1,2),(2,0)]; n=3
B=np.zeros((n,len(edges)))
for k,(u,v) in enumerate(edges): B[u,k]=-1; B[v,k]=1
print(B)
check_close("columns sum zero", B.sum(axis=0), np.zeros(len(edges)))

Exercise 5: Memory Estimate

Compare dense and edge-list storage sizes.

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 - Memory Estimate
header("Exercise 5: memory")
n=1000; m=3000
dense=n*n; edge_list=2*m
print("dense entries",dense,"edge-list entries",edge_list)
check_true("sparse edge list smaller", edge_list < dense)

Exercise 6: CSR Arrays

Build simple CSR row pointers and column indices.

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 - CSR Arrays
header("Exercise 6: CSR")
adj=[[1,2],[2],[],[0,2]]
indices=[]; indptr=[0]
for row in adj:
    indices.extend(row); indptr.append(len(indices))
print("indptr",indptr,"indices",indices)
check_close("row 3 columns", indices[indptr[3]:indptr[4]], [0,2])

Exercise 7: Self Loops

Add identity self-loops to an adjacency matrix.

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 - Self Loops
header("Exercise 7: self loops")
A=adj_from_edges(3,[(0,1),(1,2)])
Ahat=A+np.eye(3)
check_close("diagonal ones", np.diag(Ahat), np.ones(3))

Exercise 8: Normalized Adjacency

Compute $D^{-1/2}(A+I)D^{-1/2}$.

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 - Normalized Adjacency
header("Exercise 8: normalized adjacency")
A=adj_from_edges(3,[(0,1),(1,2)])+np.eye(3)
d=A.sum(axis=1); S=np.diag(1/np.sqrt(d))@A@np.diag(1/np.sqrt(d))
check_close("symmetric", S, S.T)
check_true("finite", np.all(np.isfinite(S)))

Exercise 9: Block Diagonal Batch

Batch two graphs as a block diagonal adjacency matrix.

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 - Block Diagonal Batch
header("Exercise 9: graph batch")
A1=adj_from_edges(2,[(0,1)]); A2=adj_from_edges(3,[(0,1),(1,2)])
B=np.block([[A1,np.zeros((2,3))],[np.zeros((3,2)),A2]])
check_close("shape", np.array(B.shape), np.array([5,5]))
check_close("edge count", B.sum()/2, 3)

Exercise 10: Feature Matrix Alignment

Verify node feature rows align with adjacency rows.

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 - Feature Matrix Alignment
header("Exercise 10: feature alignment")
A=adj_from_edges(3,[(0,1),(1,2)]); X=np.array([[1.,0.],[0.,1.],[1.,1.]])
AX=A@X
print("aggregated features\n",AX)
check_close("node 1 aggregates nodes 0 and 2", AX[1], X[0]+X[2])