Topological Sort ও SCC — dependency-র গণিত

from collections import deque


# ---------- অংশ ১: intentionally circular spec ----------
bad_deps = {
    'auth':    ['session'],
    'session': ['db'],
    'db':      ['cache'],
    'cache':   ['auth'],           # ← এখানেই লুপ: auth → session → db → cache → auth
}

names = sorted(bad_deps)
idx = {nm: i for i, nm in enumerate(names)}
n = len(names)
adj = [[] for _ in range(n)]
for pkg, deps in bad_deps.items():
    for d in deps:
        adj[idx[pkg]].append(idx[d])

def kahn_with_cycle_report(adj, n):
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if len(order) == n:
        return [names[i] for i in order], None
    alive = set(range(n)) - set(order)
    # unprocessed subgraph-এ সবার out-degree ≥ 1 — walk করলেই লুপ ধরা পড়ে
    start = next(iter(alive))
    pos, step = {}, 0
    u = start
    while u not in pos:
        pos[u] = step
        step += 1
        u = next(v for v in adj[u] if v in alive)
    cyc = [names[x] for x, s in pos.items() if s >= pos[u]]
    return None, cyc

order, cyc = kahn_with_cycle_report(adj, n)
if order is None:
    print('CIRCULAR DEPENDENCY DETECTED:')
    print('  ' + ' → '.join(cyc + [cyc[0]]))


# ---------- অংশ ২: SCC — এক digraph-এ দুই algorithm ----------
# a b c d e f g  →  0 1 2 3 4 5 6
edges = [('a','b'),('b','c'),('c','d'),('c','e'),
         ('e','a'),('g','f'),('f','g')]
lab = 'abcdefg'
N = 7
A = [[] for _ in range(N)]
for u, v in edges:
    A[lab.index(u)].append(lab.index(v))

def kosaraju(A, N):
    vis = [False]*N; fin = []
    for s in range(N):
        if vis[s]: continue
        vis[s] = True
        st = [(s, iter(A[s]))]
        while st:
            u, it = st[-1]
            adv = False
            for v in it:
                if not vis[v]:
                    vis[v] = True
                    st.append((v, iter(A[v])))
                    adv = True; break
            if not adv:
                fin.append(u); st.pop()
    R = [[] for _ in range(N)]
    for u in range(N):
        for v in A[u]:
            R[v].append(u)
    seen = [False]*N; comps = []
    for u in reversed(fin):
        if seen[u]: continue
        c, st = [], [u]
        seen[u] = True
        while st:
            x = st.pop(); c.append(x)
            for y in R[x]:
                if not seen[y]:
                    seen[y] = True; st.append(y)
        comps.append(sorted(lab[i] for i in c))
    return comps

def tarjan(A, N):
    idx = [-1]*N; low = [0]*N; onstk = [False]*N
    stk, comps, clock = [], [], 0
    for root in range(N):
        if idx[root] != -1: continue
        work = [(root, iter(A[root]))]
        idx[root] = low[root] = clock; clock += 1
        stk.append(root); onstk[root] = True
        while work:
            u, it = work[-1]
            adv = False
            for v in it:
                if idx[v] == -1:
                    idx[v] = low[v] = clock; clock += 1
                    stk.append(v); onstk[v] = True
                    work.append((v, iter(A[v])))
                    adv = True; break
                elif onstk[v]:
                    low[u] = min(low[u], idx[v])
            if not adv:
                work.pop()
                if work:
                    pu = work[-1][0]
                    low[pu] = min(low[pu], low[u])
                if low[u] == idx[u]:
                    c = []
                    while True:
                        x = stk.pop(); onstk[x] = False
                        c.append(x)
                        if x == u: break
                    comps.append(sorted(lab[i] for i in c))
    return comps

k = sorted(map(tuple, kosaraju(A, N)))
t = sorted(map(tuple, tarjan(A, N)))
print(f'\nKosaraju SCCs: {k}')
print(f'Tarjan   SCCs: {t}')
print(f'partition identical? {k == t}')


# ---------- অংশ ৩: এই সাইটের curriculum module graph ----------
curriculum_requires = {
    'mathematics': [],
    'computer-representation': ['mathematics'],
    'digital-logic': ['mathematics', 'computer-representation'],
    'computer-architecture': ['digital-logic'],
    'assembly': ['computer-architecture'],
    'operating-systems': ['computer-architecture', 'assembly'],
    'algorithms': ['mathematics', 'computer-representation'],
    'programming-languages': ['operating-systems', 'algorithms'],
    'compilers': ['programming-languages', 'assembly'],
    'networking': ['operating-systems'],
    'databases': ['operating-systems', 'algorithms'],
    'distributed-systems': ['networking', 'databases'],
    'security': ['operating-systems', 'networking'],
    'advanced-architecture': ['computer-architecture', 'operating-systems'],
    'virtualization-cloud': ['operating-systems', 'networking'],
    'cs-theory': ['algorithms', 'compilers'],
}

mods = sorted(curriculum_requires)
mid = {m: i for i, m in enumerate(mods)}
M = len(mods)
ADJ = [[] for _ in range(M)]
for mod, reqs in curriculum_requires.items():
    for r in reqs:
        ADJ[mid[mod]].append(mid[r])     # require করলে সেখান থেকে এদিকে arrow

indeg = [0]*M
for u in range(M):
    for v in ADJ[u]:
        indeg[v] += 1
q = deque(i for i in range(M) if indeg[i] == 0)
study = []
while q:
    u = q.popleft()
    study.append(mods[u])
    for v in ADJ[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)

print(f'\ncurriculum: {M} modules')
if len(study) == M:
    print(f'DAG ✓ — একটা বৈধ study order:')
    for i, m in enumerate(study, 1):
        reqs = curriculum_requires[m]
        tail = f'   (after {", ".join(reqs)})' if reqs else ''
        print(f'  {i:>2}. {m}{tail}')
else:
    stuck = [mods[i] for i in range(M) if mods[i] not in study]
    print(f'CYCLE! stuck: {stuck}')

# validity check: প্রতিটা module তার সব require-এর পরে আসছে?
pos = {m: i for i, m in enumerate(study)}
okall = all(all(pos[r] < pos[m] for r in rs) for m, rs in curriculum_requires.items())
print(f'order validity: {okall}')

সাধারণ ফলাফল:

CIRCULAR DEPENDENCY DETECTED:
  auth → session → db → cache → auth

Kosaraju SCCs: [('a', 'b', 'c', 'e'), ('d',), ('f', 'g')]
Tarjan   SCCs: [('a', 'b', 'c', 'e'), ('d',), ('f', 'g')]
partition identical? True

curriculum: 16 modules
DAG ✓ — একটা বৈধ study order:
   1. mathematics
   2. computer-representation   (after mathematics)
   3. digital-logic   (after mathematics, computer-representation)
   ...
  16. cs-theory   (after algorithms, compilers)
order validity: True

পড়ার নিয়ম:

১. Cycle-report নাম-ধরে বলে দেয় — ঠিক npm/make-এর error message-এর মতো, কারণ ইঞ্জিনটাই এটা।

২. দুই algorithm, এক partition — member-দের ক্রম ভিন্ন হলেও component-সেট bit-for-bit মেলে; এটাই SCC-র definition-level uniqueness (partition unique, representation না)।

৩. Curriculum নিজেই একটা live DAG — README-তে বলা studyOrder() ঠিক এই গণিত চালায় production-এ। আপনার লেখা ৫ লাইনের Kahn আজ এই সাইটের navigation ঠিক করে যে ভাবে কাজ করে।