Topological sort আর DAG

১ · ক্রমের সমস্যা — কোনটা আগে, কোনটা পরে

ধরুন ঢাকার একটি বিশ্ববিদ্যালয়ের CSE বিভাগ নতুন শিক্ষার্থীদের জন্য কোর্সের পরিকল্পনা বানাচ্ছে। কোর্সের তালিকায় লেখা আছে, কোন কোর্স নেওয়ার আগে কোনটি পাস করতে হবে। Data Structures নিতে হলে আগে Programming আর Discrete Math লাগবে; Algorithms-এর আগে Data Structures; Database-এর আগে Data Structures আর OOP. প্রশ্ন হলো: কোন ক্রমে কোর্সগুলো নিলে কোনো নিয়ম ভাঙবে না? আর সব শেষ করতে অন্তত কয়টি সেমিস্টার লাগবে?

প্রতিটি কোর্স একটি vertex, আর “u পাস না করে v নেওয়া যাবে না” হলো একটি তীর u → v. তীরের দিক আছে, তাই এটি একটি directed graph: P → DS মানে P আগে, DS পরে — উল্টোটা নয়। এমন গ্রাফ, যেখানে তীর মানে “আগে লাগবে”, তাকে বলে dependency graph. শেষ কলামটিই প্রোগ্রামে রাখা হয় — প্রতিটি vertex-এর পরের vertex-গুলোর তালিকা, অর্থাৎ adjacency list (পর্ব ৩৯):

P   -> DS, OOP        DS  -> ALG, DB        ALG -> AI
DM  -> DS, AI         OOP -> DB             DB, AI -> (none)

একই ছাঁচ সবখানে। বিয়েবাড়ির কাচ্চি: বেরেস্তা ভাজা না হলে মাংস মেরিনেট হয় না, চাল না ভিজিয়ে আধা-সেদ্ধ হয় না, আর মাংস, চাল, আলু — তিনটিই তৈরি না হলে হাঁড়িতে স্তর সাজিয়ে দমে বসানো যায় না। Build system: একটি C++ প্রজেক্টে main.o বানাতে আগে main.cpp আর তার header লাগে, আর শেষ app.exe বানাতে সব .o. ১৯৭৬ সালে Bell Labs-এ Stuart Feldman-এর লেখা make ঠিক এই নির্ভরতা পড়ে ঠিক করে কোন ফাইল আগে compile হবে। প্যাকেজ ইনস্টল: apt বা pip দিয়ে একটি লাইব্রেরি বসাতে গেলে আগে তার নির্ভর লাইব্রেরিগুলো বসাতে হয়, আর সেগুলোর নির্ভরগুলো তারও আগে।

২ · DAG আর topological order — সংজ্ঞা আর প্রমাণ

সংজ্ঞা: একটি directed গ্রাফ G = (V, E)-এর topological order হলো সব vertex-এর এমন একটি সারি v₁, v₂, …, v_n, যাতে প্রতিটি edge u → v-তে u সারিতে v-এর আগে থাকে। এমন সারি বের করার কাজটির নাম topological sort. একে “sort” বলা হলেও এখানে সংখ্যার তুলনা নেই — আছে শুধু “আগে-পরে”-র নিয়ম। কোর্সের গ্রাফে P, DM, OOP, DS, ALG, DB, AI একটি বৈধ ক্রম; DM, P, DS, OOP, ALG, AI, DB আরেকটি। কিন্তু DS, P, … বৈধ নয়, কারণ P → DS ভেঙে যায়।

যদি তালিকায় ভুল করে লেখা থাকে “Data Structures-এর আগে Algorithms লাগবে”? তাহলে DS → ALG আর ALG → DS — কেউ কারও আগে বসতে পারে না। তীর ধরে হেঁটে শুরুর vertex-এ ফিরে আসার পথকে বলে directed cycle. যে directed গ্রাফে কোনো directed cycle নেই, তার নাম directed acyclic graph, সংক্ষেপে DAG (উচ্চারণ “ড্যাগ”).

(⇒) order থাকলে cycle নেই। বিরোধ দিয়ে প্রমাণ: ধরুন একটি topological order আছে, তবু একটি cycle c₁ → c₂ → … → c_k → c₁ আছে। সারিতে vertex-এর অবস্থান pos(·) লিখুন। প্রতিটি edge-এ pos বাড়ে, তাই pos(c₁) < pos(c₂) < … < pos(c_k) < pos(c₁) — একটি সংখ্যা নিজের চেয়ে ছোট, অসম্ভব। ∎

(⇐) cycle না থাকলে order আছে। প্রথমে একটি ছোট সত্য। লেমা: প্রতিটি অশূন্য DAG-এ অন্তত একটি vertex আছে, যাতে কোনো edge ঢোকে না। একটি vertex-এ কয়টি edge ঢোকে, তার নাম in-degree; in-degree ০-এর vertex-কে বলে source. লেমার প্রমাণ: ধরুন কোনো source নেই। যেকোনো vertex থেকে শুরু করে বারবার একটি ঢোকা edge ধরে পেছনে হাঁটুন — প্রতিটি vertex-এ অন্তত একটি ঢোকা edge আছে, তাই হাঁটা কখনো থামে না। কিন্তু vertex মাত্র n টি, তাই n + 1 ধাপের মধ্যে কোনো vertex দ্বিতীয়বার আসবে (pigeonhole নীতি) — সেই দুই সাক্ষাতের মাঝের অংশটি একটি cycle. বিরোধ। ∎

এবার n-এর ওপর induction. n = 1 হলে সারিটি সেই একটি vertex. n > 1 হলে লেমা থেকে একটি source s নিন, তাকে সারির প্রথমে বসান, আর গ্রাফ থেকে s ও তার edge-গুলো মুছে দিন। বাকি গ্রাফও DAG (edge মুছলে নতুন cycle তৈরি হয় না), তাই induction-এ তার একটি topological order আছে; তার আগে s বসালেই পুরো গ্রাফের order. কেন বৈধ? s-এ কোনো edge ঢোকে না, তাই s-কে প্রথমে বসানো কোনো নিয়ম ভাঙে না; বাকি সব edge বাকি গ্রাফের ভেতরে। ∎

লক্ষ করুন, “আগে-পরে” সম্পর্কটি সব জোড়ার জন্য নির্ধারিত নয়: P আর DM-এর মধ্যে কেউ কারও আগে হওয়ার নিয়ম নেই। গণিতে এমন সম্পর্ককে বলে partial order, আর topological sort সেটিকে একটি পূর্ণ সারিতে বাড়িয়ে দেয়। তাই সাধারণত একাধিক বৈধ ক্রম থাকে — কখন ঠিক একটি, তা অংশ ৬-এ।

৩ · Kahn-এর অ্যালগরিদম — in-degree শূন্যের সারি

অংশ ২-এর প্রমাণকে দক্ষ করতে একটাই কৌশল লাগে: প্রতিবার পুরো গ্রাফ ঘুরে source খোঁজার বদলে প্রতিটি vertex-এর বাকি in-degree একটি অ্যারেতে রাখুন। একটি vertex u আউটপুট হলে u → v প্রতিটি edge “মুছে” যায়, অর্থাৎ indeg[v] এক কমে; শূন্য হলেই v নতুন source, তাকে একটি queue-তে রাখুন। ১৯৬২ সালে A. B. Kahn Communications of the ACM-এ “Topological sorting of large networks” প্রবন্ধে এই পদ্ধতি প্রকাশ করেন, তাই এর নাম Kahn-এর অ্যালগরিদম.

Pseudocode — Kahn's algorithm (0-based)

indeg[v] = number of edges into v            // one pass over all edges: O(V + E)
Q = queue of every v with indeg[v] == 0
order = empty list
while Q is not empty:
    u = Q.pop_front();  order.append(u)
    for each v in adj[u]:                    // "delete" the edge u -> v
        indeg[v] = indeg[v] - 1
        if indeg[v] == 0:  Q.push_back(v)    // v has no unmet prerequisite left
if length(order) < V:  report "cycle"       // the leftovers wait on each other
return order

কোর্সের গ্রাফে চালিয়ে দেখুন। প্রতিবার queue-র সামনে থেকে একটি কোর্স বের হয়। পাশে “স্তর” (level) সারিটিও দেখুন — এটি পরের অংশের সেমিস্টার-হিসাব, এখনই বুঝতে হবে না।

কেন ঠিক — আর কীভাবে cycle ধরা পড়ে

বৈধতা: একটি vertex v queue-তে ঢোকে কেবল যখন indeg[v] শূন্য — অর্থাৎ v-তে ঢোকা প্রতিটি edge u → v-এর u ইতিমধ্যে আউটপুটে। তাই আউটপুটে প্রতিটি edge-এর লেজ মাথার আগে আসে। এটি একটি invariant: যেকোনো মুহূর্তে indeg[v] = v-এর এমন পূর্বশর্তের সংখ্যা, যারা এখনো আউটপুট হয়নি।

cycle ধরা: একটি cycle-এর কোনো vertex কখনো আউটপুট হয় না — cycle-এর যে vertex প্রথম আউটপুট হতো, তার cycle-এর আগের vertex তখনো আউটপুট হয়নি, তাই তার in-degree শূন্য হতে পারত না। উল্টো দিকে, শেষে কিছু vertex বাকি থাকলে, বাকিদের প্রত্যেকের in-degree ≥ ১, আর সেই edge-গুলো আসে বাকিদের মধ্য থেকেই (আউটপুট হওয়াদের edge আগেই বিয়োগ হয়েছে)। বাকিদের নিয়ে গঠিত গ্রাফে তাই কোনো source নেই, আর অংশ ২-এর লেমা বলে সেখানে একটি cycle আছে। সংক্ষেপে: আউটপুটে V টি vertex ⇔ গ্রাফটি DAG.

জটিলতা: in-degree গোনায় সব edge একবার — O(V + E). প্রতিটি vertex queue-তে ঢোকে আর বের হয় ঠিক একবার — O(V). প্রতিটি vertex বের হওয়ার সময় তার adjacency list একবার পড়া হয়, তাই সব মিলিয়ে প্রতিটি edge একবার — O(E). মোট Θ(V + E) সময়, আর adjacency list, indeg ও queue মিলিয়ে Θ(V + E) জায়গা। Queue-র বদলে stack নিলেও অ্যালগরিদম ঠিক থাকে, শুধু অন্য একটি বৈধ ক্রম আসে — কোন source আগে, তাতে বৈধতা বদলায় না।

৪ · স্তরে স্তরে — ন্যূনতম কয় সেমিস্টারে সব কোর্স

এবার দ্বিতীয় প্রশ্ন: এক সেমিস্টারে যত খুশি কোর্স নেওয়া গেলে, সব শেষ করতে অন্তত কয়টি সেমিস্টার লাগবে? প্রতিটি কোর্সের স্তর সংজ্ঞায়িত করুন: source-এর স্তর ১, আর অন্যদের স্তর = তার পূর্বশর্তগুলোর সর্বোচ্চ স্তর + ১. Kahn চলার সময়ই এটি হিসাব হয়: u বের হলে প্রতিটি u → v-তে level[v] = max(level[v], level[u] + 1). v queue-তে ঢোকার আগে তার সব পূর্বশর্ত বের হয়ে গেছে, তাই তখন তার স্তর চূড়ান্ত।

দাবি: ন্যূনতম সেমিস্টার = সর্বোচ্চ স্তর = গ্রাফের সবচেয়ে লম্বা নির্ভরতার শিকলে কোর্সের সংখ্যা। নিচের সীমা: P → DS → ALG → AI শিকলের চারটি কোর্স চারটি আলাদা সেমিস্টারে, ক্রমানুসারে নিতেই হবে — কোনো সূচিতেই ৪-এর কম সম্ভব নয়। ওপরের সীমা: স্তর s-এর সব কোর্স সেমিস্টার s-এ নিন। প্রতিটি পূর্বশর্তের স্তর কঠোরভাবে ছোট, তাই সে আগের কোনো সেমিস্টারে শেষ — সূচিটি বৈধ। দুই সীমা মিলে গেল, তাই উত্তর ঠিক ৪. একই যুক্তিতে make -j একই স্তরের ফাইলগুলো একসাথে compile করতে পারে — স্তরের সংখ্যাই সময়ের নিচের সীমা।

নিচের কোডে kahn ফাংশনটি একটি ক্রম আর সেমিস্টারভিত্তিক ভাগ ছাপে, অথবা cycle পেলে কারা আটকে আছে তা বলে। দ্বিতীয় ডাকে তালিকায় একটি “ছাপার ভুল” যোগ করা হয়েছে: ALG → DS.

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;
void kahn(const vector<string>& name, const vector<pair<int, int>>& edges) {
    int n = name.size();
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0), level(n, 1), order;
    for (auto [u, v] : edges) { adj[u].push_back(v); ++indeg[v]; }   // u must come before v
    queue<int> q;
    for (int v = 0; v < n; ++v) if (indeg[v] == 0) q.push(v);
    while (!q.empty()) {
        int u = q.front(); q.pop(); order.push_back(u);
        for (int v : adj[u]) { level[v] = max(level[v], level[u] + 1); if (--indeg[v] == 0) q.push(v); }
    }
    if ((int)order.size() < n) {                                     // someone never reached in-degree 0
        cout << "cycle! only " << order.size() << " of " << n << " placed; stuck:";
        for (int v = 0; v < n; ++v) if (indeg[v] > 0) cout << ' ' << name[v];
        cout << '\n'; return;
    }
    cout << "order:"; for (int v : order) cout << ' ' << name[v];
    for (int s = 1; s <= *max_element(level.begin(), level.end()); ++s) {
        cout << "\nsemester " << s << ":";
        for (int v : order) if (level[v] == s) cout << ' ' << name[v];
    }
    cout << '\n';
}
int main() {
    vector<string> name = {"Programming", "Discrete", "DataStruct", "OOP", "Algorithms", "Database", "AI"};
    kahn(name, {{0, 2}, {1, 2}, {0, 3}, {2, 4}, {2, 5}, {3, 5}, {4, 6}, {1, 6}});
    kahn(name, {{0, 2}, {1, 2}, {0, 3}, {2, 4}, {2, 5}, {3, 5}, {4, 6}, {1, 6}, {4, 2}});   // typo: DataStruct needs Algorithms
}

order: Programming Discrete OOP DataStruct Algorithms Database AI
semester 1: Programming Discrete
semester 2: OOP DataStruct
semester 3: Algorithms Database
semester 4: AI
cycle! only 3 of 7 placed; stuck: DataStruct Algorithms Database AI

from collections import deque

def kahn(names, edges):
    n = len(names)
    adj = [[] for _ in range(n)]
    indeg, level = [0] * n, [1] * n
    for u, v in edges:                 # u must be taken before v
        adj[u].append(v)
        indeg[v] += 1
    q = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            level[v] = max(level[v], level[u] + 1)
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if len(order) < n:                 # someone never reached in-degree 0
        stuck = [names[v] for v in range(n) if indeg[v] > 0]
        print(f"cycle! only {len(order)} of {n} placed; stuck:", *stuck)
        return
    print("order:", *(names[v] for v in order))
    for s in range(1, max(level) + 1):
        print(f"semester {s}:", *(names[v] for v in order if level[v] == s))

names = ["Programming", "Discrete", "DataStruct", "OOP", "Algorithms", "Database", "AI"]
edges = [(0, 2), (1, 2), (0, 3), (2, 4), (2, 5), (3, 5), (4, 6), (1, 6)]
kahn(names, edges)
kahn(names, edges + [(4, 2)])          # catalogue typo: DataStruct now needs Algorithms

order: Programming Discrete OOP DataStruct Algorithms Database AI
semester 1: Programming Discrete
semester 2: OOP DataStruct
semester 3: Algorithms Database
semester 4: AI
cycle! only 3 of 7 placed; stuck: DataStruct Algorithms Database AI

৫ · DFS দিয়ে topological sort — শেষ হওয়ার উল্টো ক্রম

দ্বিতীয় পদ্ধতিটি আসে DFS থেকে (পর্ব ৪১)। DFS একটি vertex u-তে ঢুকে তার প্রতিটি অদেখা প্রতিবেশীতে যতদূর যাওয়া যায় যায়, তারপর ফিরে আসে। যে মুহূর্তে u-এর সব প্রতিবেশী ঘোরা শেষ, সেটি u-এর finishing time f[u]. মূল পর্যবেক্ষণ: DAG-এ u → v থাকলে v সবসময় u-এর আগে শেষ হয় — কারণ u নিজের কাজ শেষ করার আগে v-কে ঘুরে আসে। তাই vertex-গুলোকে শেষ হওয়ার ক্রমে একটি তালিকায় লিখে তালিকাটি উল্টে দিলেই topological order.

প্রতিটি vertex-এর একটি রং রাখুন: সাদা (এখনো দেখা হয়নি), ধূসর (ঢুকেছি, কাজ চলছে — call stack-এ আছে), কালো (শেষ)। এই তিন-রঙের DFS একই সাথে cycle-ও ধরে।

Pseudocode — DFS-based topological sort (0-based)

color[v] = WHITE for every v;   L = empty list
for v = 0 to V-1:
    if color[v] == WHITE:  visit(v)
return reverse(L)                         // largest finishing time first

visit(u):
    color[u] = GRAY                       // u is on the recursion stack
    for each v in adj[u]:
        if color[v] == GRAY:  report "cycle"     // back edge u -> v
        if color[v] == WHITE: visit(v)
    color[u] = BLACK;  L.append(u)        // u finishes now

একই কোর্সের গ্রাফে, vertex-গুলো P, DM, DS, OOP, ALG, DB, AI ক্রমে চেষ্টা করে, adjacency list-এর ক্রমে প্রতিবেশী নিয়ে। d/f মানে প্রবেশ আর শেষের সময় (প্রতিটি ঘটনায় ঘড়ি এক বাড়ে)।

প্রমাণ — কেন প্রতিটি edge-এ f[u] > f[v]

একটি DAG-এ DFS চলার সময় যে মুহূর্তে edge u → v পরীক্ষা হয়, তখন u ধূসর। v-এর রং তিনটির একটি হতে পারে। (১) v সাদা: DFS এখনই v-তে ঢুকবে, আর u-এর কাজ শেষ হওয়ার আগেই v-এর কাজ পুরো শেষ হবে — f[v] < f[u]. (২) v কালো: v আগেই শেষ, u এখনো শেষ হয়নি — f[v] < f[u]. (৩) v ধূসর: v তখনো call stack-এ, অর্থাৎ u আসলে v থেকে শুরু হওয়া পথের ভেতরে: v ⇝ u. তার সাথে u → v মিলে একটি cycle — DAG-এ অসম্ভব। তাই সব edge-এ f[u] > f[v], আর f-এর বড় থেকে ছোট ক্রমে সাজালে প্রতিটি edge-এর লেজ আগে আসে। ∎

(৩) নম্বর ক্ষেত্রটিই cycle ধরার নিয়ম: ধূসর vertex-এ যাওয়া edge-কে বলে back edge, আর directed গ্রাফে cycle আছে ⇔ DFS কোনো back edge পায়। উল্টো দিকটিও সত্য: cycle থাকলে cycle-এর যে vertex DFS প্রথম ছোঁয়, বাকি cycle তার নিচে ঘোরা হবে, আর cycle-এর শেষ vertex থেকে তার দিকে ফেরার edge-টি তখন ধূসর vertex-এ পড়বে। লক্ষ করুন, এখানে দুই রং যথেষ্ট নয়: শুধু “দেখা হয়েছে কি না” রাখলে ডায়াগ্রামের পঞ্চম ধাপের OOP → DB-কেও cycle ভেবে ভুল হবে। Undirected গ্রাফে DSU দিয়ে cycle ধরা গেলেও (পর্ব ৩৩) directed গ্রাফে সেটি ভুল উত্তর দেয় — এখানে লাগে ঠিক এই ধূসর-রং।

জটিলতা: প্রতিটি vertex একবার সাদা থেকে ধূসর আর একবার কালো হয়, প্রতিটি edge একবার পরীক্ষা হয় — Θ(V + E) সময়; রং, তালিকা আর call stack মিলে O(V) বাড়তি জায়গা। কিন্তু recursion-এর গভীরতা V পর্যন্ত যেতে পারে — একটি লম্বা শিকলে ১০^৫ গভীর। C++-এ সাধারণত চলে, Python-এ recursion-এর সীমা (সাধারণত ১০০০) ছাড়িয়ে RecursionError. তখন নিজের stack দিয়ে iterative DFS লিখুন, অথবা সোজা Kahn ব্যবহার করুন।

৬ · একটাই ক্রম, নাকি অনেক? — অনন্যতা আর lexicographic ক্রম

কোর্সের গ্রাফে আমরা অন্তত দুটি বৈধ ক্রম দেখেছি। কখন ক্রম ঠিক একটি? উপপাদ্য: একটি DAG-এর topological order অনন্য ⇔ সেই ক্রমের প্রতিটি পরপর জোড়া (v_i, v_i+1)-এর মধ্যে একটি edge আছে — অর্থাৎ গ্রাফে একটি Hamiltonian path আছে, যে পথ সব vertex একবার করে ছোঁয়।

প্রমাণ. (⇐) যদি v₁ → v₂ → … → v_n পথটি থাকে, যেকোনো বৈধ ক্রমে v₁ অবশ্যই v₂-এর আগে, v₂ অবশ্যই v₃-এর আগে, ইত্যাদি — ক্রম পুরোপুরি বাঁধা, তাই অনন্য। (⇒) ধরুন কোনো একটি বৈধ ক্রমে v_i আর v_i+1-এর মধ্যে edge নেই। তাদের জায়গা অদলবদল করুন। অন্য কোনো vertex-এর সাপেক্ষে তাদের অবস্থান বদলায়নি, আর তাদের দুজনের মধ্যে কোনো নিয়ম নেই — তাই নতুন ক্রমটিও বৈধ, অর্থাৎ ক্রম অনন্য নয়। ∎

ব্যবহারিক রূপ: Kahn চালানোর সময় queue-তে কখনো দুই বা ততোধিক vertex একসাথে থাকলে ক্রম অনন্য নয় (যেকোনোটি আগে নেওয়া যেত); সবসময় ঠিক একটি থাকলে প্রতিটি পদক্ষেপ বাধ্যতামূলক, তাই অনন্য। এতে O(V + E)-এ সাধারণ গ্রাফের একটি কঠিন প্রশ্ন — Hamiltonian path আছে কি না — DAG-এর জন্য সহজ হয়ে যায়।

Lexicographically সবচেয়ে ছোট ক্রম — queue-র বদলে min-heap

অনেক সমস্যায় শর্ত থাকে: “একাধিক বৈধ উত্তর থাকলে lexicographically সবচেয়ে ছোটটি ছাপুন” — অর্থাৎ প্রতিটি অবস্থানে সম্ভাব্য সবচেয়ে ছোট নম্বর। সমাধান সরল: Kahn-এর queue-র জায়গায় একটি min-heap (পর্ব ২৩) রাখুন, আর প্রতিবার প্রস্তুতদের মধ্যে সবচেয়ে ছোটটি নিন। প্রতিটি vertex একবার heap-এ ঢোকে আর বের হয় (O(log V) করে), প্রতিটি edge O(1) — মোট O(V log V + E). নিচের ছোট গ্রাফে (ধরুন ৬টি প্যাকেজ, নম্বর 0–5) edge-গুলো 3 → 0, 5 → 1, 3 → 2, 2 → 1, 4 → 2:

একটি সূক্ষ্ম ফাঁদ: “0 নম্বর যত আগে সম্ভব, তারপর 1 যত আগে সম্ভব…” — এটি lexicographically ছোট ক্রম নয়. যেমন তিনটি vertex 0, 1, 2 আর একটি edge 2 → 0. Lexicographically ছোট ক্রম 1 2 0, কিন্তু “0 যত আগে সম্ভব” চাইলে উত্তর 2 0 1. দ্বিতীয়টির প্রচলিত কৌশল: সব edge উল্টে দিন, max-heap দিয়ে Kahn চালান, আর পাওয়া ক্রমটি উল্টে দিন।

৭ · DAG-এ DP — দীর্ঘতম পথ, critical path আর পথ গোনা

Topological order-এর সবচেয়ে বড় উপহার: প্রতিটি vertex-এ পৌঁছানোর আগে তার সব পূর্বসূরি প্রস্তুত. ঠিক এটাই dynamic programming-এর দরকার (পর্ব ৫২) — প্রতিটি উপ-সমস্যা তার ওপর নির্ভরশীল উপ-সমস্যাগুলোর পরে। আসলে যেকোনো DP-র উপ-সমস্যাগুলো একটি DAG, আর tabulation-এর লুপের ক্রম সেই DAG-এর একটি topological order.

দীর্ঘতম আর সংক্ষিপ্ততম পথ, O(V + E)-এ

Edge-এ ওজন w(u, v) থাকলে, s থেকে প্রতিটি v পর্যন্ত দীর্ঘতম পথ: dist[s] = 0, অন্য সবার −∞; তারপর topological order-এ প্রতিটি u নিয়ে প্রতিটি u → v-তে dist[v] = max(dist[v], dist[u] + w(u, v)). প্রমাণ (order-এর অবস্থানের ওপর induction): v-এ পৌঁছানো যেকোনো পথের শেষ edge কোনো u → v, আর u order-এ v-এর আগে; তাই v-এর পালা আসার আগে প্রতিটি পূর্বসূরি u-এর dist চূড়ান্ত (induction), আর তাদের প্রত্যেকটি থেকে v-কে একবার হালনাগাদ করা হয়েছে। প্রতিটি edge একবার — Θ(V + E). max-কে min আর −∞-কে +∞ করলে সংক্ষিপ্ততম পথ, এমনকি ঋণাত্মক ওজনেও — cycle নেই, তাই Dijkstra-র সমস্যা (পর্ব ৪৩) বা Bellman-Ford-এর V − 1 বার ঘোরা (পর্ব ৪৪) কিছুই লাগে না।

Critical path method — বিয়েবাড়ির কাচ্চি কখন নামবে?

প্রজেক্ট পরিকল্পনায় প্রতিটি কাজের একটি সময় (duration) থাকে, আর কাজগুলোর মধ্যে নির্ভরতা। প্রশ্ন: সব কাজ শেষ হতে সবচেয়ে কম কত সময় লাগবে, যদি পরস্পর-নির্ভর নয় এমন কাজ একসাথে চলতে পারে? প্রতিটি কাজ v-এর সবচেয়ে আগে শুরুর সময় start[v] = তার পূর্বশর্তগুলোর সর্বোচ্চ (start[u] + dur[u]) — একটি দীর্ঘতম পথ, যেখানে edge u → v-এর ওজন dur[u]. পুরো প্রজেক্টের সময় = সবচেয়ে দেরিতে শেষ হওয়া কাজের শেষ সময়, আর যে পথ এই সময় ঠিক করে, তার নাম critical path: তার যেকোনো কাজ দেরি করলে পুরো প্রজেক্ট দেরি করে। এই পদ্ধতির নাম critical path method (CPM); ১৯৫০-এর দশকের শেষে DuPont কোম্পানিতে CPM আর মার্কিন নৌবাহিনীর Polaris প্রকল্পে প্রায় একই ধাঁচের PERT তৈরি হয়। আজও বড় সেতু বা ভবন নির্মাণ থেকে সফটওয়্যার রিলিজ পর্যন্ত Gantt chart আর project-management সফটওয়্যার এই হিসাবের ওপর দাঁড়িয়ে।

#include <cstdio>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int main() {
    vector<string> name = {"FryOnion", "Marinate", "SoakRice", "BoilRice", "FryPotato", "Layer", "Dum"};
    vector<int> dur = {25, 60, 30, 15, 20, 10, 60};                   // minutes
    vector<pair<int, int>> edges = {{0, 1}, {2, 3}, {1, 5}, {3, 5}, {4, 5}, {5, 6}};
    int n = name.size();
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0), order, start(n, 0), best(n, -1);        // earliest start, critical predecessor
    for (auto [u, v] : edges) { adj[u].push_back(v); ++indeg[v]; }
    queue<int> q;
    for (int v = 0; v < n; ++v) if (indeg[v] == 0) q.push(v);
    while (!q.empty()) {                                              // Kahn: a topological order
        int u = q.front(); q.pop(); order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    for (int u : order)                                               // longest-path DP, edge weight = dur[u]
        for (int v : adj[u])
            if (start[u] + dur[u] > start[v]) { start[v] = start[u] + dur[u]; best[v] = u; }
    printf("order:"); for (int v : order) printf(" %s", name[v].c_str()); printf("\n");
    int end = 0;
    for (int v : order) {
        printf("%-10s start %3d  finish %3d\n", name[v].c_str(), start[v], start[v] + dur[v]);
        if (start[v] + dur[v] > start[end] + dur[end]) end = v;
    }
    vector<string> path;
    for (int v = end; v != -1; v = best[v]) path.push_back(name[v]);
    printf("total %d min; critical path:", start[end] + dur[end]);
    for (int i = path.size() - 1; i >= 0; --i) printf(i ? " %s ->" : " %s", path[i].c_str());
    printf("\n");
}

order: FryOnion SoakRice FryPotato Marinate BoilRice Layer Dum
FryOnion   start   0  finish  25
SoakRice   start   0  finish  30
FryPotato  start   0  finish  20
Marinate   start  25  finish  85
BoilRice   start  30  finish  45
Layer      start  85  finish  95
Dum        start  95  finish 155
total 155 min; critical path: FryOnion -> Marinate -> Layer -> Dum

from collections import deque

names = ["FryOnion", "Marinate", "SoakRice", "BoilRice", "FryPotato", "Layer", "Dum"]
dur = [25, 60, 30, 15, 20, 10, 60]                     # minutes
edges = [(0, 1), (2, 3), (1, 5), (3, 5), (4, 5), (5, 6)]
n = len(names)
adj, indeg = [[] for _ in range(n)], [0] * n
for u, v in edges:
    adj[u].append(v)
    indeg[v] += 1
q = deque(v for v in range(n) if indeg[v] == 0)
order = []
while q:                                               # Kahn: a topological order
    u = q.popleft()
    order.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)
start, best = [0] * n, [-1] * n                        # earliest start, critical predecessor
for u in order:                                        # longest-path DP, edge weight = dur[u]
    for v in adj[u]:
        if start[u] + dur[u] > start[v]:
            start[v], best[v] = start[u] + dur[u], u
print("order:", *(names[v] for v in order))
for v in order:
    print(f"{names[v]:<10} start {start[v]:>3}  finish {start[v] + dur[v]:>3}")
end = max(range(n), key=lambda v: start[v] + dur[v])
path = []
while end != -1:
    path.append(names[end])
    end = best[end]
print("total", max(s + d for s, d in zip(start, dur)), "min; critical path:", " -> ".join(reversed(path)))

order: FryOnion SoakRice FryPotato Marinate BoilRice Layer Dum
FryOnion   start   0  finish  25
SoakRice   start   0  finish  30
FryPotato  start   0  finish  20
Marinate   start  25  finish  85
BoilRice   start  30  finish  45
Layer      start  85  finish  95
Dum        start  95  finish 155
total 155 min; critical path: FryOnion -> Marinate -> Layer -> Dum

পথ গোনা

একই ছাঁচে, “কত ভাবে” প্রশ্নও। ways[v] = v-এ শেষ হওয়া পথের সংখ্যা: source-এ ১, অন্যদের ways[v] = সব পূর্বসূরি u-র ways[u]-এর যোগফল, topological order-এ হিসাব। কোর্সের গ্রাফে P = 1, DM = 1, OOP = 1, DS = 1 + 1 = 2, ALG = 2, DB = 2 + 1 = 3, AI = ALG + DM = 2 + 1 = 3 — AI-তে শেষ হওয়া তিনটি পূর্বশর্ত-শিকল: P → DS → ALG → AI, DM → DS → ALG → AI, আর DM → AI. পথের সংখ্যা ঘাতের হারে বাড়তে পারে (প্রতিটি “হীরা” আকৃতির অংশ সংখ্যাকে দ্বিগুণ করে), তাই কনটেস্টে উত্তর সাধারণত 10⁹ + 7 দিয়ে ভাগশেষ চাওয়া হয় (modular arithmetic). গ্রিডে শুধু ডানে আর নিচে চলার পথ গোনা, বা সিঁড়ির ধাপ গোনা — সবই আসলে DAG-এ পথ গোনা।

৮ · নির্ভরতার চক্র — circular import থেকে spreadsheet পর্যন্ত

বাস্তব সফটওয়্যারে topological sort-এর অর্ধেক কাজ ক্রম বানানো, বাকি অর্ধেক circular dependency ধরা আর পরিষ্কার ভাষায় জানানো। কয়েকটি পরিচিত রূপ:

• Python-এর circular import: a.py লেখে from b import f, আর b.py লেখে from a import g. প্রথম import চলার মাঝপথে দ্বিতীয়টি অর্ধেক-তৈরি module খুঁজে পায় — আর ImportError আসে, যেখানে “partially initialized module” আর “circular import” কথাগুলো থাকে। Go ভাষা আরও কড়া: compile-এর সময়ই “import cycle not allowed”.
• Build system: make চক্র পেলে সতর্ক করে আর একটি নির্ভরতা বাদ দেয়; আধুনিক build system (Ninja, Bazel) সাধারণত পুরো চক্রটি ছেপে থেমে যায়।
• Spreadsheet: A1 = B1 + 1 আর B1 = A1 × 2 লিখলে Excel “circular reference” সতর্কবার্তা দেয়। একটি ঘর বদলালে কোন ঘরগুলো কোন ক্রমে নতুন করে হিসাব হবে, তা-ও ঘরগুলোর নির্ভরতার DAG থেকে আসে।
• প্যাকেজ আর ডেটাবেস: প্যাকেজ ম্যানেজার নির্ভরতার ক্রমে ইনস্টল করে; ডেটাবেসে foreign key-যুক্ত টেবিল তৈরি বা মোছার ক্রমও topological order.

সব ক্ষেত্রে ভালো ত্রুটি-বার্তার জন্য শুধু “cycle আছে” যথেষ্ট নয় — ব্যবহারকারী জানতে চান কোন চক্র। DFS-এর call stack এখানে কাজে আসে: back edge u → v পেলে v থেকে u পর্যন্ত stack-এর অংশ আর সেই edge মিলে চক্রটি (অনুশীলন ৪)। একাধিক চক্র জড়িয়ে থাকলে strongly connected component (পর্ব ৪৬) দিয়ে প্রতিটি “জট” আলাদা করা যায় — আর সেই জটগুলোকে একটি করে বিন্দু ধরলে বাকি গ্রাফটি আবার একটি DAG.

৯ · AI-এর যুগে topological sort — ঠিক দেখতে, ভুল চলতে

“Course schedule সমস্যার কোড দাও” — এটি AI-কে দেওয়া সবচেয়ে প্রচলিত গ্রাফ-অনুরোধগুলোর একটি, আর উত্তর প্রায় সবসময় ঝকঝকে। কিন্তু topological sort-এর ভুলগুলো চুপচাপ থাকে: cycle-যুক্ত ইনপুটে কোড একটি আংশিক ক্রম ফেরত দিয়ে খুশি থাকে, বা DFS-এ finishing তালিকা উল্টাতে ভুলে যায়, আর ছোট উদাহরণে অনেক সময় উত্তর তবুও “ঠিক” দেখায়।

Topological sort-এ AI সাধারণত যেসব ভুল করে

Topological sort-এর কোড যাচাইয়ের চেকলিস্ট

• Edge-এর দিক ঠিক: “u আগে লাগবে v-এর জন্য” মানে u → v, আর in-degree গোনা হয়েছে v-এ
• ফলাফল যাচাইয়ের ছোট ফাংশন লিখেছি: প্রতিটি edge-এ pos[u] < pos[v], আর আউটপুটে প্রতিটি vertex ঠিক একবার
• Edge case: V = 1, কোনো edge নেই, নিজের দিকে edge (u → u), একই edge দুবার, কয়েকটি বিচ্ছিন্ন অংশ, পুরো শিকল
• Cycle-যুক্ত ইনপুটে কোড স্পষ্টভাবে ব্যর্থতা জানায়, আংশিক ক্রমকে উত্তর বলে না
• ছোট এলোমেলো DAG-এ brute force-এর সাথে মিলিয়েছি (সব permutation থেকে বৈধগুলো, বা lexicographic ক্ষেত্রে সবচেয়ে ছোটটি) — stress testing
• বড় ইনপুটে Python-এ deque আর recursion-মুক্ত কোড; AI-এর complexity দাবিতে V আর E দুটোই আছে কি না দেখেছি