AI Generated Answers. Original assignment/project questions on this blog are attributed to Sayed Ahmed. The new AI-generated worked solutions and examples are offered for reuse without copyright restrictions asserted by the blog; external datasets and linked resources retain their own rights. These are instructional examples; test code before classroom use.
Graph Mining – 1 course index · Original prompt source: Graph Mining: Misc. Topics to Learn · This part covers prompts 13.01–13.03.
Q13.01. Implement graph algorithms from scratch and apply them to a suitably chosen network. The post lists BFS, DFS, single-source and all-pairs shortest paths, Dijkstra’s algorithm, minimum cuts including Karger’s method, and clique algorithms.
Answer. Worked solution. Choose a small, reproducible undirected graph. Implement traversal by BFS/DFS, shortest paths by Dijkstra (nonnegative weights), and all-pairs distances by Floyd–Warshall; implement global min-cut by Karger and clique enumeration by Bron–Kerbosch. Analyze complexity: BFS/DFS O(V+E), heap Dijkstra O((V+E)log V), Floyd–Warshall O(V³), and clique enumeration is exponential in the worst case. The code examples below are original didactic implementations; do not treat them as optimized large-graph libraries.
Q13.02. Run comparable graph-library implementations on the same datasets. Do they give the same results? Use a library such as NetworkX in Python. Keep the graph and assumptions the same when comparing with your own implementation.
Answer. Worked solution. Use identical vertices, edges, directions and weights in handwritten and library versions, and compare results with assertions. BFS traversal order may differ because multiple equal choices are valid; instead compare reachable vertex sets and shortest-path distances. Min-cut size and MST cost are good invariant outputs. A disagreement requires checking node order, self-loops, tie-breaking, and edge-weight meaning.
Q13.03. Implement spanning trees and highly connected subgraphs.
Answer. Worked solution. Calculate an MST with Prim on a connected weighted graph and partition it by removing k−1 highest distance edges. For highly connected subgraphs, repeatedly compute global min-cuts and recurse until λ(H)>|H|/2. The MST lesson and HCS lesson contain the complete implementations and verified fixture.
From-scratch algorithms: BFS, DFS, Dijkstra and Floyd–Warshall
from collections import deque
import heapq
INF=float("inf")
# Weighted undirected adjacency list
W = {0:{1:2,2:5}, 1:{0:2,2:1,3:4},
2:{0:5,1:1,3:2}, 3:{1:4,2:2}}
def bfs(adj, source):
seen={source}; q=deque([source]); order=[]
while q:
u=q.popleft(); order.append(u)
for v in adj[u]:
if v not in seen: seen.add(v); q.append(v)
return order
def dfs(adj, source):
seen=set(); order=[]
def visit(u):
seen.add(u); order.append(u)
for v in adj[u]:
if v not in seen: visit(v)
visit(source)
return order
def dijkstra(adj, source):
dist={u:INF for u in adj}; dist[source]=0
q=[(0,source)]
while q:
d,u=heapq.heappop(q)
if d!=dist[u]: continue
for v,w in adj[u].items():
if w<0: raise ValueError("Negative weight")
nd=d+w
if nd
From scratch: Bron–Kerbosch maximal cliques
def maximal_cliques(adj):
out=[]
def bk(R,P,X):
if not P and not X:
out.append(set(R)); return
for v in list(P):
bk(R|{v}, P & set(adj[v]), X & set(adj[v]))
P.remove(v); X.add(v)
bk(set(),set(adj),set())
return out
simple={u:set(neighbors) for u,neighbors in W.items()}
print("Maximal cliques:",maximal_cliques(simple))
# Maximal sets are {0,1,2} and {1,2,3} only if edge 0-2 exists;
# here both triangles do exist in W.
For randomized minimum cuts use the full Karger implementation in lesson 09, Part 3. Its repeated trials are important because one contraction run is not guaranteed to find an optimal cut.
