Topological Sort

কম্পিউটার বিজ্ঞানে টাস্ক অর্ডারিং করার জন্য টপোলজিক্যাল শর্ট অনেক জনপ্রিয়। কম্পিউটারকে যখন অনেক টাস্ক হ্যান্ডেল করতে হয়, তখন এই এলগোরিদমটি অনেক সাহায্য করে। আমাদের দৈনন্দিন জীবনেও বিভিন্ন টাস্ক অর্ডারিং করতে টপোলজিক্যাল শর্টের অনেক গুরুত্ব রয়েছে। কম্পিউটার বিজ্ঞানে তোমাকে অনেকগুলো কোর্স পড়তে হয়। তোমাকে সি, সি++, ফিজিক্স, কেমিস্ট্রি, ডাটা স্ট্রাকচার, এলগোরিদম ইত্যাদি কোর্স পড়তে হয়। এইসব সাবজেক্ট কি তোমার ইচ্ছা মতো  অর্ডারিং এ পড়তে পারো ??? যেমন আগে এলগোরিদম এরপর সি। উত্তরটি হবে না!!! সাবজেক্টগুলো একটি নির্দিষ্ট অর্ডার ফলো করে তোমাকে পড়তে হয়। কোন কোর্সের পর কোন কোর্স পড়তে হবে নিচে তার একটি তালিকা দেয়া হল।

ফিজিক্স ->সি; কেমিস্ট্রি ->সি; সি ->সি ++; সি -> এলগোরিদম; সি -> ডাটা স্ট্রাকচার; সি++ -> ডাটা স্ট্রাকচার; সি++ -> এলগোরিদম; ডাটা স্ট্রাকচার-> এলগোরিদম; 

এখন প্রতিটি কোর্সকে একটি নোড হিসেবে কল্পনা করে একটি ডিরেক্টেড গ্রাফ আঁকি।

প্রতিটি কোর্স বা নোডের পাশে সংখ্যা দ্বারা ইনডিগ্রী বোঝানো হয়েছে। কোন নোডে যতটি এজ প্রবেশ করে তার সংখ্যা হিসেবে করে ইনডিগ্রী নির্ণয় করা হয়। টপোলজিক্যাল শর্ট এ যে নোডের ইনডিগ্রী জিরো সেই নোড নিয়ে অর্ডারিং শুরু করতে হয়। এখানে ফিজিক্স ও কেমিস্ট্রি দুটি নোডেরই ইনডিগ্রী শূন্য। তাই যেকোন একটি নিয়ে শুরু করতে পারি। যে নোড নিয়ে কাজ করব সেই নোড থেকে যেসব এজ বের হয়েছে সেই গুলো ডিলিট করব।

এখন মনেকর, আমরা আগে ফিজিক্স পড়ব। তাই ফিজিক্স থেকে সি এর এজটি ডিলিট করে দেই এবং সি এর ইনডিগ্রি এক কমবে।

এবার যেহেতু কেমিস্ট্রি এর ইনডিগ্রী শূন্য তাই কেমিস্ট্রি পড়ব। কেমিস্ট্রি থেকে সি এর এজটি ডিলিট করে দেই এবং সি এর ইনডিগ্রী এক কমিয়ে দেই।

এবার যেহেতু সি এর ইনডিগ্রী শূন্য তাই সি পড়ব। সি থেকে যেসব এজ বের হয়েছে সবগুলো ডিলিট করে দেই।

এবার যেহেতু সি++ এর ইনডিগ্রী শূন্য তাই সি++ পড়ব। সি++ থেকে যেসব এজ বের হয়েছে সবগুলো ডিলিট করে দেই।

এবার যেহেতু ডাটা স্ট্রাকচার এর ইনডিগ্রী শূন্য তাই ডাটা স্ট্রাকচার পড়ব। ডাটা স্ট্রাকচার থেকে যেসব এজ বের হয়েছে সবগুলো ডিলিট করে দেই।

এখন যেহেতু এলগোরিদম এর ইনডিগ্রী শূন্য তাই এলগোরিদম পড়ব। এভাবে তুমি কোর্স গুলো পড়ার অর্ডারিং পেয়ে গেছো। অর্ডারিংটি এমন- ফিজিক্স->কেমিস্ট্রি->সি->সি++ -> ডাটা স্ট্রাকচার-> এলগোরিদম। এভাবেই টপোলজিক্যাল শর্ট কাজ করে। এবার টপোলজিক্যাল শর্ট এর এলগোরিদমটি দেখ নিচে-

1. প্রথমে প্রতিটি নোডের ইনডিগ্রী নির্ণয় করতে হবে
2. যেসব নোডের ইনডিগ্রি শূন্য সেই নোড গুলোকে একটি কিউতে রাখি।
3. যতক্ষণ পর্যন্ত কিউ খালি না হয়, 4 ও 5 নম্বর ষ্টেপের জন্য লুপ চালাই
4.          কিউ থেকে ফ্রন্টের নোড N রিমুভ করি
5.          নোড N এর সাথে যুক্ত প্রতিটি নোড M এর জন্য নিচের দুটি স্টেপ রিপিট করি        

• নোড N ও নোড M এর এজ ডিলিট করি
• যেসব নোডের ইনডিগ্রী শূন্য হবে সেই গুলো কিউতে রাখি

আমরা টপোলজিক্যাল শর্ট বোঝার জন্য একটি উদাহরণ ও এলগোরিদম দেখলাম। এখন এলগোরিদমটির ইমপ্লিমেন্টেশন দেখব।

Code: 

/*  Topological Sort-Indegree  */

#include<bits/stdc++.h>
using namespace std;

vector <int> G[105];
vector <int> processed;
queue <int> q;
int indegree[105];
int n, m;

void topsort()
{
    int u;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        processed.push_back(u);
        for(int i=0; i<G[u].size(); i++)
        {
            int v=G[u][i];
            indegree[v]--;
            if(indegree[v]==0)
            {
                q.push(v);
            }
        }
    }
}

int main()
{
    int u, v;
    while(scanf("%d%d", &n, &m)==2)
    {
        if(n==0 && m==0)
            break;
        memset(indegree, 0, sizeof(indegree)); // Initialize indegree of all node to zero
        for(int i=0; i<m; i++)
        {
            scanf("%d%d", &u, &v);
            indegree[v]++;  // Increment indegree of nodes
            G[u].push_back(v);
        }

        /* Finding nodes having zero indegree and push them into queue */
        for(int i=1; i<=n; i++)
        {
            if(indegree[i]==0)
            {
                q.push(i);
            }
        }

        topsort();

        for(int i=0; i<processed.size(); i++)
        {
            printf("%d ", processed[i]);
        }
        processed.clear();
        for(int i=1; i<=n; i++)
        {
            G[i].clear();
        }
        printf("\n");
    }
    return 0;
}

টপোলজিক্যাল শর্ট রিলেটেড প্রোগ্রামিং প্রবলেমের লিংক- UVA 10305-Ordering Tasks