"""Graphs — runnable reference implementation. ভেতরে কী আছে (উপর থেকে নিচে পড়ো): 1. build_adjacency -- edge list -> adjacency list (default storage) 2. bfs_distances -- queue-চালিত traversal; shortest unweighted paths 3. dfs_recursive / dfs_iterative -- stack-চালিত traversal, দুই style-এই 4. count_components -- প্রতিটা unclaimed island-এ একটা করে traversal launch 5. dijkstra -- BFS + greedy + min-heap; weighted shortest paths 6. topo_sort_kahn -- zero-indegree nodes ছাড়িয়ে নাও; cycles detect করে চালাও: python implementation.py প্রতিটা demo নিজের result assert করে, তাই চুপচাপ শেষ হওয়া মানেই সব কাজ করছে। শুধু standard library। """ import heapq from collections import defaultdict, deque # --------------------------------------------------------------------------- # 1. Edge list থেকে adjacency list বানাও # --------------------------------------------------------------------------- def build_adjacency(edges, directed=False): """edges: (u, v) pair-দের iterable। Returns {node: [neighbors]}। Beginner graph code-এ সবচেয়ে বেশি ভুলে যাওয়া লাইন: UNDIRECTED graph-এ প্রতিটা edge-কে BOTH প্রান্ত থেকেই register করতে হবে। """ adj = defaultdict(list) for u, v in edges: adj[u].append(v) if not directed: adj[v].append(u) # mirror entry-টা else: adj[v] # v ছুঁয়ে দাও, যাতে isolated sink-রাও থাকে return adj # --------------------------------------------------------------------------- # 2. BFS — queue-র traversal। প্রথমবার পৌঁছানো = shortest unweighted path। # --------------------------------------------------------------------------- def bfs_distances(adj, start): """সব reachable node-এর জন্য {node: start থেকে hop distance} return করো। যে discipline matter করে: - deque, কখনোই list.pop(0) না (pop প্রতি O(1) vs O(n)) - visited mark করো PUSH-এর সময়, pop-এ না (এখানে: `dist`-এ insert করা) """ dist = {start: 0} # visited set হিসেবেও কাজ করে q = deque([start]) while q: node = q.popleft() for nxt in adj[node]: if nxt not in dist: dist[nxt] = dist[node] + 1 q.append(nxt) return dist # --------------------------------------------------------------------------- # 3. DFS — stack-এর traversal, দুই পোশাকেই # --------------------------------------------------------------------------- def dfs_recursive(adj, start, visited=None): """Classic তিন-লাইনের DFS। Call stack-টাই হলো stack।""" if visited is None: visited = set() visited.add(start) for nxt in adj[start]: if nxt not in visited: dfs_recursive(adj, nxt, visited) return visited def dfs_iterative(adj, start): """একই reach, explicit stack — Python-এর recursion limit-এ অটল।""" visited = {start} stack = [start] while stack: node = stack.pop() # .pop() (LIFO)-ই BFS থেকে একমাত্র পার্থক্য for nxt in adj[node]: if nxt not in visited: visited.add(nxt) stack.append(nxt) return visited # --------------------------------------------------------------------------- # 4. Connected components — প্রতিটা unclaimed island-এ এক paint-bucket flood # --------------------------------------------------------------------------- def count_components(nodes, adj): visited = set() count = 0 for node in nodes: if node not in visited: # এমন এক দ্বীপ, যাকে কেউ এখনো রঙ করেনি dfs_recursive(adj, node, visited) # পুরোটা রঙ করে ফেলো count += 1 return count # --------------------------------------------------------------------------- # 5. Dijkstra — BFS + greedy + min-heap (weights অবশ্যই non-negative!) # --------------------------------------------------------------------------- def dijkstra(wadj, start): """wadj: {u: [(v, weight), ...]}। Returns {node: start থেকে cheapest cost}। Greedy হৃৎপিণ্ডটা: heap-এর cheapest entry-টাই একটা FINAL answer, কারণ যেকোনো বিকল্প route আগে থেকেই দামি কোনো path extend করত, আর non-negative weights শুধু cost-ই যোগ করতে পারে। """ dist = {start: 0} done = set() heap = [(0, start)] # (cost, node) — heap-এর জন্য cost FIRST while heap: cost, node = heapq.heappop(heap) if node in done: continue # stale entry — lazy deletion কাজে নেমেছে done.add(node) for nxt, w in wadj[node]: new_cost = cost + w if nxt not in dist or new_cost < dist[nxt]: dist[nxt] = new_cost # edge-টা "relax" করো heapq.heappush(heap, (new_cost, nxt)) return dist # --------------------------------------------------------------------------- # 6. Topological sort (Kahn) — zero unmet prerequisite-ওয়ালা nodes ছাড়িয়ে নাও # --------------------------------------------------------------------------- def topo_sort_kahn(nodes, dadj): """dadj: DIRECTED adjacency {u: [v, ...]} — মানে u আসবে v-র আগে। একটা valid order return করে, অথবা None যদি cycle order-কে impossible করে। """ indeg = {n: 0 for n in nodes} for u in nodes: for v in dadj[u]: indeg[v] += 1 q = deque(n for n in nodes if indeg[n] == 0) # এখনই করা যায় order = [] while q: node = q.popleft() order.append(node) for nxt in dadj[node]: indeg[nxt] -= 1 # একটা prerequisite সাফ if indeg[nxt] == 0: q.append(nxt) return order if len(order) == len(nodes) else None # ছোট = cycle def is_valid_topo(order, edges): """Check করো প্রতিটা edge u->v-তে u আছে v-র আগে (orders unique না)।""" pos = {node: i for i, node in enumerate(order)} return all(pos[u] < pos[v] for u, v in edges) # --------------------------------------------------------------------------- # Demos — concept.md-এর worked graph, শুরু থেকে শেষ পর্যন্ত verify করা # --------------------------------------------------------------------------- if __name__ == "__main__": # concept.md-এর road map টা, সাথে একটা isolated island {X, Y}: # # A ---- B # | | # C ---- D ---- E X ---- Y # edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")] island = [("X", "Y")] adj = build_adjacency(edges + island) assert sorted(adj["D"]) == ["B", "C", "E"] assert sorted(adj["A"]) == ["B", "C"] print("adjacency list ..... ok (D's neighbors:", sorted(adj['D']), ")") # BFS: A থেকে hop distances। E আছে 3 hop দূরে (A-B-D-E বা A-C-D-E)। dist = bfs_distances(adj, "A") assert dist == {"A": 0, "B": 1, "C": 1, "D": 2, "E": 3} assert "X" not in dist # island-টা unreachable print("BFS distances ...... ok (from A:", dict(sorted(dist.items())), ")") # DFS: দুই style-কেই হুবহু একই set of nodes-এ পৌঁছাতে হবে। reach_rec = dfs_recursive(adj, "A") reach_it = dfs_iterative(adj, "A") assert reach_rec == reach_it == {"A", "B", "C", "D", "E"} print("DFS (rec & iter) ... ok (reached", len(reach_rec), "nodes from A)") # Components: mainland {A..E} + island {X, Y} = 2। nodes = ["A", "B", "C", "D", "E", "X", "Y"] assert count_components(nodes, adj) == 2 print("components ......... ok (count = 2)") # shortest-path.md-এর weighted square-এ Dijkstra: # # (4) # A -------- B # | /| # (1)| (1) |(5) # | / | # C -------- D # (8) # # Best A->B যায় C-র মধ্য দিয়ে: 1 + 1 = 2, direct edge 4-কে হারিয়ে। wedges = [("A", "B", 4), ("A", "C", 1), ("C", "B", 1), ("B", "D", 5), ("C", "D", 8)] wadj = defaultdict(list) for u, v, w in wedges: wadj[u].append((v, w)) wadj[v].append((u, w)) # undirected weighted graph sp = dijkstra(wadj, "A") assert sp == {"A": 0, "C": 1, "B": 2, "D": 7} print("Dijkstra ........... ok (from A:", dict(sorted(sp.items())), ")") # topological-sort.md-এর course graph-এ topological sort: # # intro ──> ds ──> algo # │ ^ # └────> math ────┘ # course_edges = [("intro", "ds"), ("intro", "math"), ("ds", "algo"), ("math", "algo")] courses = ["intro", "ds", "math", "algo"] dadj = build_adjacency(course_edges, directed=True) order = topo_sort_kahn(courses, dadj) assert order is not None and len(order) == 4 assert is_valid_topo(order, course_edges) # প্রতিটা arrow মেনে চলে assert order[0] == "intro" and order[-1] == "algo" print("topo sort .......... ok (one valid order:", order, ")") # Cycle detection: a -> b -> c -> a-র কোনো valid order নেই। cyc_edges = [("a", "b"), ("b", "c"), ("c", "a")] cyc_adj = build_adjacency(cyc_edges, directed=True) assert topo_sort_kahn(["a", "b", "c"], cyc_adj) is None print("cycle detection .... ok (cyclic graph correctly returns None)") print("\nAll graph demos passed.")