গ্রাফ ভিত্তিক ডেটা স্ট্রাকচার: Directed Acyclic Graph (DAG)

গ্রাফ ভিত্তিক ডেটা স্ট্রাকচার: Directed Acyclic Graph (DAG)

Directed Acyclic Graph (DAG) হল এমন একটি গ্রাফ যা ডিরেক্টেড (Directed) এবং অ্যাসাইক্লিক (Acyclic), অর্থাৎ:

1. ডিরেক্টেড (Directed): গ্রাফের প্রতিটি এজ একটি নির্দিষ্ট দিক নির্দেশ করে, অর্থাৎ একটি ভেরটেক্স থেকে অন্য ভেরটেক্সে যাওয়ার জন্য একটি দিক থাকে।
2. অ্যাসাইক্লিক (Acyclic): এই গ্রাফে কোনো সাইকেল (Cycle) নেই, অর্থাৎ একক কোনো পাথ বা রাস্তা কোনোভাবেই নিজেই ফিরে আসতে পারে না।

DAG একটি গুরুত্বপূর্ণ গ্রাফ ডেটা স্ট্রাকচার যা বিভিন্ন বাস্তবসম্মত সমস্যার সমাধানে ব্যবহৃত হয়, যেমন টাস্ক শিডিউলিং, ডিপেনডেন্সি রেজল্যুশন, এবং অপটিমাইজেশন অ্যালগরিদম।

DAG এর বৈশিষ্ট্য

1. ডিরেক্টেড এজ: প্রতিটি এজ একটি নির্দিষ্ট দিক নির্দেশ করে, যেমন A → B (এ থেকে বি পর্যন্ত)।
2. অ্যাসাইক্লিক: গ্রাফে কোনো সাইকেল বা চক্র থাকে না। কোনো ভেরটেক্স থেকে যদি অন্য ভেরটেক্সে যাওয়া হয়, তবে সেই পাথটি একবারই ব্যবহার করা যেতে পারে। ফলে একটি ভেরটেক্স থেকে আরেকটি ভেরটেক্সে ফিরে আসার কোন সম্ভাবনা নেই।
3. পাঠ্যক্রমিক (Topological): DAG-এ একটি "টপোলজিকাল অর্ডার" থাকতে পারে, যেখানে ভেরটেক্সগুলো এমনভাবে সাজানো থাকে যে, প্রতিটি এজটি তার শুরুর পয়েন্ট থেকে শেষ পয়েন্টে চলে। এই টপোলজিকাল অর্ডার গণনা করার জন্য DAG ব্যবহার করা হয়।

DAG এর ব্যবহার

1. টাস্ক শিডিউলিং:
   • বিভিন্ন টাস্কের মধ্যে নির্ভরশীলতা নির্দেশ করতে DAG ব্যবহৃত হয়। যেমন, একটি টাস্ক সম্পূর্ণ হওয়ার পরেই আরেকটি টাস্ক শুরু হতে পারে।
2. ডিপেনডেন্সি রেজল্যুশন:
   • ডিপেনডেন্সি (dependency) গ্রাফ হিসেবে DAG ব্যবহার করা হয় যাতে কোনো কাজের জন্য অপর কাজের নির্ভরতা তুলে ধরা যায়।
3. কম্পাইলার ডিজাইন:
   • কম্পাইলারের অপটিমাইজেশনে DAG ব্যবহার করা হয় যাতে ইনস্ট্রাকশনগুলোর নির্ভরতা সহজে ট্র্যাক করা যায়।
4. অ্যালগরিদম অপটিমাইজেশন:
   • বিভিন্ন অপটিমাইজেশন অ্যালগরিদমে DAG ব্যবহার করা হয়, যেমন, shortest path এবং critical path calculation।

DAG এর গঠন

DAG গঠনে কিছু সাধারণ উপাদান থাকে:

1. ভেরটেক্স (Vertex): গ্রাফের মূল উপাদান, যা সাধারণত কিছু মান বা টাস্ককে প্রতিনিধিত্ব করে।
2. এজ (Edge): দুটি ভেরটেক্সের মধ্যে একটি দিক নির্দেশিত সম্পর্ক বা সংযোগ।

DAG এর উদাহরণ

ধরা যাক, আমাদের একটি টাস্ক শিডিউলিং প্রোগ্রাম রয়েছে যেখানে কিছু টাস্ক পরস্পরের উপর নির্ভরশীল। আমরা DAG ব্যবহার করে এগুলোকে মডেল করতে পারি।

    A
   / \
  B   C
   \ /
    D

এখানে:

• A-এর উপরে দুটি টাস্ক B এবং C নির্ভরশীল।
• B এবং C উভয়ই D-এর উপরে নির্ভরশীল।
• এই গ্রাফের কোনো সাইকেল নেই, অর্থাৎ কোনও টাস্কে ফিরে আসা সম্ভব নয়।

DAG এর গঠন সি প্রোগ্রামে

এখানে আমরা একটি DAG তৈরি করার জন্য অ্যাডজেসেন্সি লিস্ট ব্যবহার করব।

সি প্রোগ্রামে DAG এর ইমপ্লিমেন্টেশন:

#include <stdio.h>
#include <stdlib.h>

// গ্রাফের জন্য একটি স্ট্রাকচার (ভেরটেক্স এবং এর নোডের পয়েন্টার)
struct Node {
    int vertex;
    struct Node* next;
};

// গ্রাফের জন্য একটি স্ট্রাকচার (ভেরটেক্সের জন্য অ্যাডজেসেন্সি লিস্ট)
struct Graph {
    int V;  // ভেরটেক্সের সংখ্যা
    struct Node** adjList;  // অ্যাডজেসেন্সি লিস্ট
};

// নোড তৈরি ফাংশন
struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// গ্রাফ তৈরি ফাংশন
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->adjList = (struct Node**)malloc(V * sizeof(struct Node*));

    // প্রতিটি অ্যাডজেসেন্সি লিস্টকে NULL দিয়ে ইনিশিয়ালাইজ করা
    for (int i = 0; i < V; i++) {
        graph->adjList[i] = NULL;
    }

    return graph;
}

// একটি এজ যোগ করার ফাংশন
void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
}

// গ্রাফ প্রিন্ট করা ফাংশন
void printGraph(struct Graph* graph) {
    for (int i = 0; i < graph->V; i++) {
        struct Node* temp = graph->adjList[i];
        printf("\nVertex %d: ", i);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    struct Graph* graph = createGraph(4);

    addEdge(graph, 0, 1);  // A -> B
    addEdge(graph, 0, 2);  // A -> C
    addEdge(graph, 1, 3);  // B -> D
    addEdge(graph, 2, 3);  // C -> D

    printGraph(graph);

    return 0;
}

ব্যাখ্যা:

1. createNode() ফাংশন একটি নতুন নোড তৈরি করে এবং তার মধ্যে ভেরটেক্সের মান রাখে।
2. createGraph() ফাংশন একটি নতুন গ্রাফ তৈরি করে এবং তার অ্যাডজেসেন্সি লিস্টে ইনিশিয়ালাইজ করে।
3. addEdge() ফাংশন একটি ডিরেক্টেড এজ যোগ করে, অর্থাৎ একটি ভেরটেক্স থেকে অন্য ভেরটেক্সে নির্দেশিত সংযোগ তৈরি করে।
4. printGraph() ফাংশন গ্রাফের সমস্ত ভেরটেক্স এবং তাদের সংযুক্ত নোড প্রদর্শন করে।

DAG এর জন্য টপোলজিকাল সোর্ট (Topological Sort)

DAG-এ একটি গুরুত্বপূর্ণ অপারেশন হল টপোলজিকাল সোর্ট। এতে একটি গ্রাফের সমস্ত ভেরটেক্স এমনভাবে সাজানো হয়, যাতে প্রতিটি এজের জন্য শুরুর ভেরটেক্স আগে আসে। টপোলজিকাল সোর্ট একটি DAG-এর অর্ডার সরবরাহ করে যা টাস্ক শিডিউলিং, ডিপেনডেন্সি রেজল্যুশন ইত্যাদিতে ব্যবহৃত হয়।

Topological Sort Algorithm:

1. DAG-এর মধ্যে সমস্ত ইনডিগ্রি (incoming degree) শূন্য ভেরটেক্স বের করুন।
2. সেগুলিকে একটি কিউতে রাখুন।
3. কিউ থেকে একটি ভেরটেক্স বের করুন, এবং তার সংযুক্ত সকল নোডের ইনডিগ্রি কমিয়ে দিন। যদি কোন নোডের ইনডিগ্রি শূন্য হয়ে যায়, তবে সেটিকে কিউতে যোগ করুন।
4. এই প্রক্রিয়া চলতে থাকে যতক্ষণ না সমস্ত ভেরটেক্স প্রসেস করা হয়।

সারসংক্ষেপ

• DAG (Directed Acyclic Graph) একটি গ্রাফ ডেটা স্ট্রাকচার যা ডিরেক্টেড এবং অ্যাসাইক্লিক হয়। এতে কোনো সাইকেল বা চক্র থাকে না এবং প্রতিটি এজ একটি নির্দিষ্ট দিক নির্দেশ করে।
• এটি বিভিন্ন অ্যাপ্লিকেশন যেমন টাস্ক শিডিউলিং, ডিপেনডেন্সি রেজল্যুশন এবং অপটিমাইজেশন সমস্যায় ব্যবহৃত হয়।
• DAG-এ টপোলজিকাল সোর্ট একটি গুরুত্বপূর্ণ অপারেশন যা ভেরটেক্সগুলোকে নির্দিষ্ট একটি অর্ডারে সাজাতে সাহায্য করে।