টপোলজিক্যাল সর্ট

১ · টপোলজিক্যাল সর্ট কী এবং কেন এটি গুরুত্বপূর্ণ

একটি ডাইরেক্টেড গ্রাফ $G=(V,E)$-এর একটি টপোলজিক্যাল অর্ডারTopological Orderভার্টেক্সগুলোর একটি লিনিয়ার সিকোয়েন্স যেখানে প্রতিটি ডাইরেক্টেড এজ $u \to v$-এর জন্য $u$, $v$-এর আগে আসে। হলো ভার্টেক্সগুলোর এমন একটি লিনিয়ার সাজানো $v_1, v_2, \ldots, v_n$ যেখানে প্রতিটি এজ $(u,v) \in E$-এর জন্য $u$, $v$-এর আগে আসে। বাস্তব-জীবনের উদাহরণ: কোর্স প্রি-রিকুইজিট (একটি কোর্স নেওয়ার আগে তার প্রি-রিকুইজিট কোর্স শেষ করতে হবে), বিল্ড সিস্টেম ডিপেন্ডেন্সি (একটি ফাইল কম্পাইল করার আগে তার ডিপেন্ডেন্সি কম্পাইল করতে হবে), স্প্রেডশিট সেল ইভ্যালুয়েশন অর্ডার ইত্যাদি।

মূল দাবি: একটি গ্রাফের অন্তত একটি টপোলজিক্যাল অর্ডার থাকে যদি এবং শুধুমাত্র যদি গ্রাফে কোনো ডাইরেক্টেড সাইকেল না থাকে — অর্থাৎ এটি একটি DAG (Directed Acyclic Graph)। এটি স্বজ্ঞাতভাবেই বোঝা যায়: যদি একটি সাইকেল $v_1 \to v_2 \to \cdots \to v_k \to v_1$ থাকে, তাহলে $v_1$-কে $v_2$-এর আগে আসতে হবে (এজ $v_1 \to v_2$), কিন্তু আবার $v_k \to v_1$ এজের কারণে $v_k$-কেও $v_1$-এর আগে আসতে হবে, এবং $v_1,\ldots,v_k$ চেইনের মাধ্যমে $v_1$-কে নিজের আগে আসতে হবে — একটি স্ববিরোধিতা। তাই সাইকেলযুক্ত গ্রাফের কোনো টপোলজিক্যাল অর্ডার থাকতে পারে না।

২ · Kahn's অ্যালগরিদম — ইন-ডিগ্রি ট্র্যাকিং

প্রতিটি ভার্টেক্স $v$-এর ইন-ডিগ্রি হলো তার দিকে আসা এজের সংখ্যা। মূল অন্তর্দৃষ্টি: যদি একটি ভার্টেক্সের ইন-ডিগ্রি ০ হয়, তার মানে কোনো এজ তার আগে থাকার দাবি করছে না — তাই এটিকে নিরাপদে অর্ডারে এখনই বসানো যায়। এটি বসানোর পর, এর আউটগোয়িং এজগুলো "সরিয়ে ফেলা" (এবং সেই প্রতিবেশীদের ইন-ডিগ্রি ১ কমানো) যায়, যা নতুন শূন্য-ইন-ডিগ্রি ভার্টেক্স তৈরি করতে পারে।

যদি সব ভার্টেক্স অর্ডারে যোগ হয়ে যায় (আউটপুট লেন্থ $=|V|$), গ্রাফটি একটি DAG ছিল এবং আমরা একটি বৈধ টপোলজিক্যাল অর্ডার পেয়েছি। কিন্তু যদি প্রক্রিয়া থেমে যাওয়ার পরও কিছু ভার্টেক্স বাকি থেকে যায় (তাদের ইন-ডিগ্রি কখনো ০-তে পৌঁছায়নি), তার মানে সেই বাকি ভার্টেক্সগুলো একটি সাইকেলের অংশ — Kahn's অ্যালগরিদম বাড়তি কাজ ছাড়াই সাইকেল ডিটেকশন বিনামূল্যে দেয়। এই কোর্সে আমরা Kahn's অ্যালগরিদম বেছে নিয়েছি (বিকল্প: DFS-ভিত্তিক ফিনিশ-টাইম রিভার্সাল পদ্ধতি, যা L32-এর কোসারাজু অ্যালগরিদমে ব্যবহৃত ধারণার সাথে সম্পর্কিত)।

৩ · ইমপ্লিমেন্টেশন ও যাচাই — প্রতিটি এজ চেক করা

একটি আউটপুট অর্ডার "সঠিক" প্রমাণ করার সবচেয়ে বিশ্বাসযোগ্য উপায় হলো প্রতিটি এজ $(u,v)$-এর জন্য সরাসরি চেক করা যে অর্ডারে $u$-এর পজিশন $v$-এর পজিশনের আগে কি না — এটি সংজ্ঞা থেকে সরাসরি আসা একটি এক্সহস্টিভ চেক, তাই এটি অ্যালগরিদমের নিজস্ব লজিকের উপর নির্ভর না করেই সঠিকতা প্রমাণ করে।

from collections import deque

def kahn_topo_sort(edges, vertices):
    in_degree = {v: 0 for v in vertices}
    for u in vertices:
        for v in edges.get(u, []):
            in_degree[v] += 1

    queue = deque([v for v in vertices if in_degree[v] == 0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in edges.get(u, []):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    return order

def verify_topo_order(edges, order):
    # সংজ্ঞা থেকে সরাসরি: প্রতিটি এজ (u, v)-এর জন্য order-এ u অবশ্যই v-এর আগে থাকতে হবে
    position = {v: i for i, v in enumerate(order)}
    violations = []
    for u in edges:
        for v in edges[u]:
            if position[u] > position[v]:
                violations.append((u, v))
    return violations

test_dags = [
    {  # DAG ১: কোর্স প্রি-রিকুইজিট চেইন
        "vertices": ["A", "B", "C", "D", "E", "F"],
        "edges": {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": ["F"], "E": ["F"], "F": []},
    },
    {  # DAG ২: প্রশস্ত (wide) গ্রাফ, একাধিক ইন-ডিগ্রি-০ ভার্টেক্স একসাথে
        "vertices": list(range(8)),
        "edges": {0: [1, 2], 1: [3], 2: [3, 4], 3: [5], 4: [5, 6], 5: [7], 6: [7], 7: []},
    },
    {  # DAG ৩: একাধিক ডিসকানেক্টেড কম্পোনেন্ট + একটি আইসোলেটেড ভার্টেক্স
        "vertices": ["x", "y", "z", "w", "iso"],
        "edges": {"x": ["y"], "y": ["z"], "z": [], "w": ["z"], "iso": []},
    },
]

for i, dag in enumerate(test_dags, 1):
    vertices, edges = dag["vertices"], dag["edges"]
    order = kahn_topo_sort(edges, vertices)
    violations = verify_topo_order(edges, order)
    complete = len(order) == len(vertices)
    print(f"DAG {i}: order = {order}")
    print(f"  সব ভার্টেক্স অর্ডারে আছে: {complete} | এজ লঙ্ঘন: {violations if violations else 'নেই'}")
    assert complete, f"DAG {i}: কিছু ভার্টেক্স অর্ডারে অনুপস্থিত -- সাইকেল সন্দেহজনক!"
    assert not violations, f"DAG {i}: এজ লঙ্ঘন পাওয়া গেছে -- অর্ডার ভুল!"

print("\nসব DAG-এ Kahn's অ্যালগরিদমের আউটপুট প্রতিটি এজ সম্মান করেছে।")

# একটি সাইকেলযুক্ত গ্রাফে Kahn's অ্যালগরিদম যে অসম্পূর্ণ অর্ডার দেয় তা দেখা
cyclic_edges = {"P": ["Q"], "Q": ["R"], "R": ["P"]}
cyclic_vertices = ["P", "Q", "R"]
cyclic_order = kahn_topo_sort(cyclic_edges, cyclic_vertices)
print(f"\nসাইকেলযুক্ত গ্রাফে Kahn's আউটপুট: {cyclic_order} (দৈর্ঘ্য {len(cyclic_order)}, মোট ভার্টেক্স {len(cyclic_vertices)})")
print("সাইকেল ডিটেক্টেড:", len(cyclic_order) < len(cyclic_vertices))