Prolog এ গ্রাফের মডেলিং এবং Traversal

গ্রাফ মডেলিং এবং traversal (গ্রাফের মধ্যে পথ অনুসন্ধান) প্রোলগে সাধারণভাবে নোডস এবং এজেস (edges) এর মাধ্যমে তৈরি করা হয়। প্রোলগের মধ্যে গ্রাফের বিভিন্ন প্রকার মডেলিং করা এবং তার মধ্যে ব্রেডথ-ফার্স্ট সার্চ (BFS) এবং ডিপথ-ফার্স্ট সার্চ (DFS) এর মতো traversal পদ্ধতি ব্যবহার করে গ্রাফের বিভিন্ন নোডে পৌঁছানো যায়।

গ্রাফ মডেলিং (Graph Modeling) প্রোলগে

গ্রাফ মডেলিংয়ে আমরা নোড (nodes) এবং এজ (edges) ব্যবহার করি। একে প্রোলগে ফ্যাক্ট হিসেবে মডেল করা হয়, যেখানে প্রতিটি সম্পর্ক একটি এজ (এটা হতে পারে directed বা undirected)। সাধারণত edge/2 সম্পর্ক দিয়ে গ্রাফের এজ গঠন করা হয়, যেখানে দুটি ভেরিয়েবল একটি নোডের মধ্যে সংযোগ (এজ) বোঝায়।

গ্রাফ মডেলিং উদাহরণ:

ধরা যাক, আমাদের একটি গ্রাফ আছে যেখানে চারটি নোড এবং কয়েকটি এজ রয়েছে:

• A → B
• B → C
• C → D
• A → C

এটা প্রোলগে নিম্নরূপ মডেল করা হতে পারে:

% Directed edges
edge(a, b).
edge(b, c).
edge(c, d).
edge(a, c).

এখানে, edge/2 ফ্যাক্টের মাধ্যমে চারটি directed edge (এজ) তৈরি করা হয়েছে। এখন আমরা এই গ্রাফের মধ্যে বিভিন্ন traversal পদ্ধতি ব্যবহার করতে পারি।

1. ডিপথ-ফার্স্ট সার্চ (DFS):

DFS হল একটি পদ্ধতি যেখানে প্রথমে যতদূর সম্ভব একটি শাখায় যাওয়া হয় এবং তারপর সেই শাখার সমস্ত নোড পরীক্ষা করা হয়। যখন কোনো শাখা শেষ হয়ে যায়, তখন আমরা পূর্ববর্তী শাখায় ফিরে এসে অন্য শাখা অনুসন্ধান করি। প্রোলগে DFS সাধারণত পুনঃপ্রবেশের মাধ্যমে সম্পন্ন হয়।

DFS এর জন্য পেডিকেট:

% DFS: Traversing from Node to its connected nodes recursively
dfs(Node, Path) :-
    dfs_helper(Node, [], Path).

% Helper predicate: Traversing recursively
dfs_helper(Node, Visited, [Node|Visited]) :-
    \+ member(Node, Visited),  % Avoid visiting the same node again
    edge(Node, NextNode),      % Check if there is an edge to the next node
    dfs_helper(NextNode, [Node|Visited], _).

এখানে:

• dfs/2 পেডিকেটটি গ্রাফের একটি নোড থেকে DFS traversal শুরু করে।
• dfs_helper/3 হল সেই রিকার্সিভ পেডিকেট যা নোডের সাথে সম্পর্কিত নোডগুলিতে পৌঁছাতে ব্যবহৃত হয় এবং পরবর্তী নোডে যাওয়ার জন্য edge/2 চেক করে।

কোয়ারি:

?- dfs(a, Path).

এটি গ্রাফের মধ্যে a থেকে শুরু করে DFS traversal এর Path বের করবে। ফলস্বরূপ:

Path = [a, c, b, d].

এখানে, a → c → b → d পথ অনুসন্ধান করে পাওয়া গেছে।

2. ব্রেডথ-ফার্স্ট সার্চ (BFS):

BFS একটি সার্চ পদ্ধতি যেখানে প্রথমে সকল নিকটবর্তী নোড পরীক্ষা করা হয় এবং তারপর আরও দূরের নোডগুলো পরীক্ষা করা হয়। BFS সাধারণত কিউ (Queue) ব্যবহার করে বাস্তবায়ন করা হয়, যেখানে প্রথমে আনা নোডটি আগে পরীক্ষা করা হয়।

BFS এর জন্য পেডিকেট:

% BFS: Traversing from Node to its connected nodes using Queue
bfs(Start, Path) :-
    bfs_helper([Start], [], Path).

% Helper predicate: Traversing nodes using Queue
bfs_helper([], _, []).  % No more nodes to visit
bfs_helper([Node|Queue], Visited, [Node|Path]) :-
    \+ member(Node, Visited),  % Avoid visiting the same node again
    findall(NextNode, edge(Node, NextNode), Neighbors),  % Find neighbors
    append(Queue, Neighbors, NewQueue),  % Add neighbors to queue
    bfs_helper(NewQueue, [Node|Visited], Path).

এখানে:

• bfs/2 পেডিকেটটি BFS traversal শুরু করে Start নোড থেকে।
• bfs_helper/3 পেডিকেটটি Queue ব্যবহার করে BFS traversal সম্পন্ন করে।

কোয়ারি:

?- bfs(a, Path).

এটি a থেকে শুরু করে BFS traversal এর Path বের করবে। ফলস্বরূপ:

Path = [a, b, c, d].

এখানে, a → b → c → d পথ অনুসন্ধান করে পাওয়া গেছে।

3. গ্রাফের ডিরেক্টেড এবং আনডিরেক্টেড কেস

যদি গ্রাফ ডিরেক্টেড না হয়ে আনডিরেক্টেড (যেখানে উভয় দিকেই সম্পর্ক থাকে) হয়, তবে edge/2 এর জন্য দুইটি এজ তৈরি করতে হবে, যেমন:

edge(a, b).
edge(b, a).
edge(b, c).
edge(c, b).
edge(a, c).
edge(c, a).

এখন DFS বা BFS ব্যবহার করলে আপনি গ্রাফের যেকোনো দিকের দিকে যাচাই করতে পারবেন। তবে edge/2 সম্পর্কটি দ্বিমুখী (bidirectional) হবে।

4. গ্রাফের মধ্যে সাইকেল চেকিং

গ্রাফে সাইকেল (cycle) চেক করার জন্য, অর্থাৎ কোনো নোডে ফিরে আসা কি না, তার জন্য DFS ব্যবহার করা যেতে পারে। যদি কোনো নোডে পৌঁছানোর পর আবার সেই নোডে ফিরে আসা যায়, তবে গ্রাফে সাইকেল রয়েছে।

has_cycle(Node) :-
    dfs(Node, Path),
    member(Node, Path).  % If the node is in the path, there is a cycle

এখানে, has_cycle/1 পেডিকেটটি চেক করে যে গ্রাফে কোনো সাইকেল রয়েছে কিনা।

সারসংক্ষেপ:

• গ্রাফ মডেলিং প্রোলগে এজেস এবং নোডস ব্যবহার করে ফ্যাক্ট হিসেবে করা হয়, যেখানে edge/2 ফ্যাক্ট দ্বারা দুটি নোডের মধ্যে সম্পর্ক তৈরি করা হয়।
• DFS এবং BFS গ্রাফের মধ্যে traversal করতে ব্যবহৃত হয়। DFS পদ্ধতি পুনরাবৃত্তি (recursion) ব্যবহার করে এবং BFS পদ্ধতি কিউ (Queue) ব্যবহার করে।
• গ্রাফে সাইকেল চেক করার জন্য DFS এর মাধ্যমে যদি কোনো নোডে আবার ফিরে আসা যায়, তবে তা সাইকেল হিসেবে গণ্য করা হয়।

এভাবে, প্রোলগে গ্রাফের মডেলিং এবং traversal এর মাধ্যমে আমরা অনেক ধরনের সমস্যা সমাধান করতে পারি।