Graph Playground

কেন এই প্রজেক্ট

Graph Theory লেসনে আমরা BFS/DFS-এর ধারণা আর প্রমাণ দেখেছি — BFS কেন shortest path দেয়, DFS কেন cycle detect করতে পারে। কিন্তু “বুঝেছি” আর “লিখতে পারি” এক জিনিস না।

এই প্রজেক্টের আসল লক্ষ্য শুধু algorithm চালানো না — instrument করা। প্রতিটা algorithm-এ আপনি গুনবেন কয়টা node visit হলো, কয়টা edge পরীক্ষা হলো। এই সংখ্যাগুলোই পরে Asymptotic Notation লেসনের O(V+E) দাবিটাকে বাস্তবে যাচাই করবে।

গঠন

$ ./graph demo.txt bfs A

BFS from A:
  visit order : A B C D E F
  distances   : A=0 B=1 C=1 D=2 E=2 F=3
  nodes touched: 6   edges examined: 9

ধাপে ধাপে

১. দুইটা representation

class AdjList:
    def __init__(self, directed=False):
        self.adj = {}
        self.directed = directed

    def add_edge(self, u, v):
        self.adj.setdefault(u, []).append(v)
        self.adj.setdefault(v, [])
        if not self.directed:
            self.adj[v].append(u)

    def neighbors(self, u):
        return self.adj.get(u, [])

class AdjMatrix:
    def __init__(self, nodes, directed=False):
        self.index = {n: i for i, n in enumerate(nodes)}
        n = len(nodes)
        self.m = [[0] * n for _ in range(n)]
        self.directed = directed

    def add_edge(self, u, v):
        i, j = self.index[u], self.index[v]
        self.m[i][j] = 1
        if not self.directed:
            self.m[j][i] = 1

V node আর E edge-এ memory মাপুন: adjacency list O(V + E), matrix O(V²) — অভিজ্ঞতা দিয়ে দেখুন V = 10,000 আর E = 20,000-এ matrix কতটা বড় হয়ে যায় (১০০ মিলিয়ন cell), যেখানে list মাত্র ৩০,০০০ entry।

২. BFS — instrumented

from collections import deque

def bfs(graph, start):
    visited = {start: 0}
    order = []
    q = deque([start])
    nodes_touched, edges_examined = 1, 0

    while q:
        u = q.popleft()
        order.append(u)
        for v in graph.neighbors(u):
            edges_examined += 1
            if v not in visited:
                visited[v] = visited[u] + 1
                nodes_touched += 1
                q.append(v)

    return order, visited, nodes_touched, edges_examined

visited[v] = visited[u] + 1 লাইনটাই আসল দাবি: BFS প্রতিটা node-কে সবচেয়ে কম হপে পৌঁছায়, কারণ queue-এর FIFO ধর্মের জন্য কাছের node-গুলো সবসময় আগে process হয়।

৩. DFS — recursive বনাম iterative

def dfs_recursive(graph, u, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(u)
    order.append(u)
    for v in graph.neighbors(u):
        if v not in visited:
            dfs_recursive(graph, v, visited, order)
    return order

def dfs_iterative(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        u = stack.pop()
        if u in visited:
            continue
        visited.add(u)
        order.append(u)
        for v in reversed(graph.neighbors(u)):
            if v not in visited:
                stack.append(v)
    return order

দুইটা প্রায় সবসময় একই order দেয় না — কেন? কারণ explicit stack-এ push করা সব neighbor visited হওয়ার আগেই আরেকটা push হতে পারে (duplicate), যেখানে call stack প্রতিটা recursive call-এ সাথে সাথে visited আপডেট করে। এই পার্থক্যটা নিজে trace করে বের করুন — এটাই recursion আর explicit stack simulation-এর মধ্যেকার আসল ফারাক, যা Level 4-এ (call stack, stack frame) আরও গভীরভাবে আসবে।

৪. Edge classification (directed graph)

DFS চলাকালীন প্রতিটা edge (u, v) চারভাবে classify হতে পারে:

ধরন	চেনার উপায়
Tree edge	v আগে unvisited ছিল, DFS ওটাকে discover করলো
Back edge	v বর্তমান DFS path-এ ancestor (এখনো “in progress”)
Forward edge	v আগেই সম্পূর্ণ visited, u-র descendant
Cross edge	v সম্পূর্ণ visited, কিন্তু ancestor/descendant নয়

WHITE, GRAY, BLACK = 0, 1, 2

def dfs_classify(graph, start):
    color = {u: WHITE for u in graph.adj}
    classification = {}

    def visit(u):
        color[u] = GRAY
        for v in graph.neighbors(u):
            if color[v] == WHITE:
                classification[(u, v)] = 'tree'
                visit(v)
            elif color[v] == GRAY:
                classification[(u, v)] = 'back'      # ← cycle!
            elif color[v] == BLACK:
                classification[(u, v)] = 'forward/cross'
        color[u] = BLACK

    visit(start)
    return classification

একটা back edge মানেই cycle — v এখনো GRAY (call stack-এ আছে) মানে u থেকে v-তে ফিরে আসা path পাওয়া গেছে।

৫. Topological sort — দুইভাবে

Kahn’s algorithm (BFS-ভিত্তিক):

def topo_sort_kahn(graph):
    in_degree = {u: 0 for u in graph.adj}
    for u in graph.adj:
        for v in graph.neighbors(u):
            in_degree[v] += 1

    q = deque([u for u in in_degree if in_degree[u] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph.neighbors(u):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)

    if len(order) != len(graph.adj):
        raise ValueError("Cycle detected — topological sort অসম্ভব")
    return order

DFS-ভিত্তিক (finish-time reverse):

def topo_sort_dfs(graph):
    visited, finished = set(), []

    def visit(u):
        visited.add(u)
        for v in graph.neighbors(u):
            if v not in visited:
                visit(v)
        finished.append(u)     # নিজের সব dependency শেষ হওয়ার পরই append

    for u in graph.adj:
        if u not in visited:
            visit(u)
    return list(reversed(finished))

দুইটা algorithm সম্পূর্ণ ভিন্ন কৌশল ব্যবহার করে, কিন্তু (cycle না থাকলে) একটা বৈধ topological order-এই পৌঁছায় — যদিও আউটপুট আলাদা হতে পারে (topological order সাধারণত unique নয়)। দুইটা চালিয়ে compare করুন: দুইটাই কি সব dependency edge respect করছে?

নিজেকে চ্যালেঞ্জ করুন

1. Weighted BFS-এর ভুল ইচ্ছাকৃতভাবে দেখান — BFS একটা weighted graph-এ shortest path দেয় না কেন, একটা counterexample বানান (Level 6-এ Dijkstra এই সমস্যার সমাধান)
2. Connected components — undirected graph-এ কয়টা component আছে, BFS/DFS দিয়ে বের করুন
3. Strongly connected components — directed graph-এ Kosaraju’s algorithm (দুইবার DFS, একবার transpose graph-এ)
4. Bipartite check — 2-coloring দিয়ে, BFS-এর সময় পাশাপাশি node বিপরীত রঙ দিন, সংঘর্ষ হলে bipartite নয়
5. ASCII visualization — traversal order আর tree/back/forward edge আলাদা রঙে বা চিহ্নে টার্মিনালে দেখান

এটা যেখানে গিয়ে মিশবে

এখানে যা শিখলেন	পরে কোথায় লাগবে
Adjacency list vs matrix	Level 6 — Graph representation trade-off গভীরভাবে
BFS shortest path	Level 6 — Dijkstra, 0-1 BFS
Back edge = cycle	Level 4 — Deadlock detection (resource allocation graph)
Topological sort	Level 5 — Compiler dependency resolution, build systems
Kahn’s in-degree queue	Level 9 — Task scheduling, DAG-ভিত্তিক workflow engine