Trees এবং Graphs এর ইমপ্লিমেন্টেশন

ট্রি এবং গ্রাফ হল জনপ্রিয় ডেটা স্ট্রাকচার যা বিভিন্ন অ্যালগরিদম এবং সমস্যার সমাধানে ব্যবহৃত হয়। LISP একটি ফাংশনাল প্রোগ্রামিং ভাষা, এবং এখানে এই ডেটা স্ট্রাকচারগুলি বাস্তবায়ন করতে আমরা লিস্ট এবং অ্যোসোসিয়েটিভ অ্যারে (Associative Arrays) ব্যবহার করতে পারি। LISP-এ ট্রি এবং গ্রাফের ধারণা এবং কার্যকলাপ খুবই নমনীয় এবং শক্তিশালী, এবং সেগুলি খুব সহজেই ইমপ্লিমেন্ট করা যায়।

এখানে আমরা ট্রি (Tree) এবং গ্রাফ (Graph) ডেটা স্ট্রাকচার তৈরি এবং ব্যবহারের পদ্ধতি আলোচনা করব।

১. ট্রি (Tree) ইমপ্লিমেন্টেশন

ট্রি হলো একটি ডেটা স্ট্রাকচার যা হায়ারার্কিক্যাল (Hierarchical) কাঠামোতে ডেটা সংরক্ষণ করে। একটি ট্রিতে একটি রুট নোড থাকে এবং তার সাথে সম্পর্কিত অন্যান্য নোডগুলির একটি শাখা থাকে।

ট্রি নোডের গঠন

একটি ট্রি গঠন করতে আমরা LISP-এ লিস্ট ব্যবহার করতে পারি, যেখানে প্রতিটি নোডের প্রথম উপাদানটি তার মান (value) এবং বাকি উপাদানগুলি তার সন্তানের তালিকা।

উদাহরণ: বাইনারি ট্রি ইমপ্লিমেন্টেশন

;; একটি সিম্পল বাইনারি ট্রি তৈরি করা
(setq my-tree '(10 (5 () ()) (20 () ())))

;; ইনসার্ট ফাংশন
(defun insert (tree value)
  (if (null tree)
      (list value nil nil)  ; যদি ট্রি ফাঁকা হয়, নতুন নোড যোগ করবে
      (let ((node-value (first tree))
            (left (second tree))
            (right (third tree)))
        (cond ((< value node-value) 
               (list node-value (insert left value) right))  ; বাম দিকে ইনসার্ট
              ((> value node-value) 
               (list node-value left (insert right value)))  ; ডান দিকে ইনসার্ট
              (t tree)))))

(setq my-tree (insert my-tree 15))  ; 15 যোগ করা হবে

এখানে, my-tree একটি বাইনারি ট্রি, এবং insert ফাংশনটি একটি মান value ট্রিতে সঠিক অবস্থানে ইনসার্ট করে।

ট্রি traversal (পূর্নতা, ইনঅর্ডার, পোস্টঅর্ডার):

;; ইনঅর্ডার ট্রাভার্সাল
(defun inorder (tree)
  (if tree
      (append (inorder (second tree)) (list (first tree)) (inorder (third tree)))
      nil))

(inorder my-tree)  ; আউটপুট: (5 10 15 20)

এখানে inorder ফাংশনটি ট্রির ইনঅর্ডার ট্রাভার্সাল সম্পাদন করে, অর্থাৎ প্রথমে বাম পা, তারপর মূল, তারপর ডান পা।

২. গ্রাফ (Graph) ইমপ্লিমেন্টেশন

গ্রাফ হলো একটি ডেটা স্ট্রাকচার যা নোড (vertices) এবং তাদের মধ্যে সংযোগ (edges) দিয়ে গঠিত। একটি গ্রাফে অথবা একমুখী (directed) অথবা দ্বিমুখী (undirected) হতে পারে।

LISP-এ একটি গ্রাফ ইমপ্লিমেন্ট করতে আমরা সাধারণত অ্যোসোসিয়েটিভ অ্যারে বা লিস্ট ব্যবহার করি। গ্রাফের প্রতিটি নোডের জন্য একটি কীগুচি (key) এবং সেই নোডের সাথে যুক্ত অন্যান্য নোডের একটি তালিকা (list) থাকে।

উদাহরণ: আন্ডাইরেক্টেড গ্রাফ

;; গ্রাফের আন্ডাইরেক্টেড ইমপ্লিমেন্টেশন
(setq graph '((1 . (2 3)) (2 . (1 4)) (3 . (1 5)) (4 . (2)) (5 . (3))))

;; নোড থেকে প্রতিবেশী বের করা
(defun get-neighbors (graph node)
  (cdr (assoc node graph)))

(get-neighbors graph 1)  ; আউটপুট: (2 3)

এখানে, graph একটি অ্যাসোসিয়েটিভ অ্যারে যা গ্রাফের নোডের জন্য সংযুক্ত প্রতিবেশী (neighbors) ধারণ করে। get-neighbors ফাংশনটি একটি নির্দিষ্ট নোডের প্রতিবেশী বের করতে ব্যবহৃত হয়।

গ্রাফ ট্রাভার্সাল (Depth-First Search - DFS):

;; DFS ট্রাভার্সাল
(defun dfs (graph start &optional (visited '()))
  (if (member start visited)
      visited
      (let ((new-visited (cons start visited)))
        (dolist (neighbor (get-neighbors graph start) new-visited)
          (dfs graph neighbor new-visited)))))
          
(dfs graph 1)  ; আউটপুট: (1 3 5 2 4)

এখানে dfs ফাংশনটি গ্রাফের ডেপথ-ফার্স্ট সার্চ (DFS) ট্রাভার্সাল বাস্তবায়ন করেছে, যেখানে প্রতিটি নোড এবং তার প্রতিবেশীদের পরিদর্শন করা হয়।

৩. ডিরেক্টেড গ্রাফ (Directed Graph)

ডিরেক্টেড গ্রাফে নোডের মধ্যে একমুখী সংযোগ থাকে, অর্থাৎ একটি নোড থেকে অন্য নোডে আর্ক (edge) থাকে, কিন্তু তার বিপরীত দিকে আর্ক থাকে না।

উদাহরণ: ডিরেক্টেড গ্রাফ

;; ডিরেক্টেড গ্রাফের ইমপ্লিমেন্টেশন
(setq directed-graph '((1 . (2 3)) (2 . (4)) (3 . (5)) (4 . ()) (5 . ())))

;; ডিরেক্টেড গ্রাফ থেকে প্রতিবেশী বের করা
(get-neighbors directed-graph 1)  ; আউটপুট: (2 3)

এখানে, directed-graph একটি ডিরেক্টেড গ্রাফ যেখানে একটি নোড থেকে অন্য নোডে একমুখী সংযোগ আছে।

৪. গ্রাফের উপর অপারেশনস

গ্রাফে বিভিন্ন অপারেশন যেমন এডজ (edge) যোগ করা, নোডে নতুন প্রতিবেশী যোগ করা, বা গ্রাফের বিভিন্ন ট্রাভার্সাল (যেমন BFS, DFS) করতে পারেন।

উদাহরণ: এডজ যোগ করা

(defun add-edge (graph node1 node2)
  (let ((node1-neighbors (cdr (assoc node1 graph))))
    (if (not (member node2 node1-neighbors))
        (setf (cdr (assoc node1 graph)) (cons node2 node1-neighbors)))))

;; নতুন এডজ যোগ করা
(add-edge graph 1 4)

এখানে, add-edge ফাংশনটি দুটি নোডের মধ্যে একটি নতুন এডজ যোগ করে। এইভাবে গ্রাফে নতুন সম্পর্ক যোগ করা সম্ভব।

৫. গ্রাফে সাইকেল চেক করা

গ্রাফে সাইকেল (cycle) থাকলে এটি কিছু অ্যালগরিদমের জন্য সমস্যার সৃষ্টি করতে পারে, বিশেষ করে ডিপথ-ফার্স্ট সার্চ বা ব্রেডথ-ফার্স্ট সার্চে। সাইকেল চেক করার জন্য আপনি DFS ব্যবহার করতে পারেন।

উদাহরণ: সাইকেল চেক করা

(defun has-cycle (graph start)
  (let ((visited '()))
    (labels ((dfs (node path)
               (if (member node path)
                   t  ; সাইকেল পাওয়া গেছে
                   (or (some #'(lambda (neighbor) (dfs neighbor (cons node path))) 
                             (get-neighbors graph node)))))
      (dfs start '()))))

(has-cycle graph 1)  ; আউটপুট: T (যদি সাইকেল থাকে)

এখানে, has-cycle ফাংশনটি গ্রাফে সাইকেল চেক করে এবং যদি সাইকেল থাকে তবে T রিটার্ন করে।

সারসংক্ষেপ

ট্রি এবং গ্রাফ হল শক্তিশালী ডেটা স্ট্রাকচার যা LISP-এ খুব সহজে ইমপ্লিমেন্ট করা যায়। ট্রি এবং গ্রাফের জন্য LISP-এ:

1. ট্রি ইমপ্লিমেন্টেশন: বাইনারি ট্রি তৈরি এবং ট্রাভার্সাল (Inorder, Preorder, Postorder) করা।
2. গ্রাফ ইমপ্লিমেন্টেশন: আন্ডাইরেক্টেড এবং ডিরেক্টেড গ্রাফ তৈরি করা এবং ট্রাভার্সাল (DFS, BFS) করা।
3. গ্রাফ অপারেশন: এডজ যোগ, সাইকেল চেক, এবং প্রতিবেশী নির্ধ

ারণ।

LISP-এ এই ডেটা স্ট্রাকচারগুলির মাধ্যমে আপনি অনেক শক্তিশালী অ্যালগরিদম তৈরি করতে পারবেন এবং বিভিন্ন সমস্যা সহজে সমাধান করতে পারবেন।