রুবি দিয়ে ব্যাবহারিক গ্রাফ থিওরি মास্টার করুন

এটি "ব্যাবহারিক কম্পিউটার সায়েন্স" সিরিজের পরবর্তী ইনস্টলমেন্ট, যেখানে আপনি শিখবেন কীভাবে ক্লাসিক কম্পিউটার সায়েন্স কনসেপ্টগুলো রুবি ব্যবহার করে রিয়েল সমস্যা সমাধান করতে প্রয়োগ করা যায়।

আজ আমরা গ্রাফ থিওরি নিয়ে কথা বলব।

আপনি বাইনারি ট্রি সম্পর্কে শুনেছেন হতে পারে, সেগুলো এরকম দেখায়:

বিষয়টি হলো একটি বাইনারি ট্রি হলো একটি গ্রাফের স্পেশালাইজড ভার্সন, তাই এটা আপনাকে একটা ধারণা দিতে পারে গ্রাফ কতটা ব্যাপক।

চলুন গ্রাফ থিওরির ফান্ডামেন্টালের ওভারভিউ দিই, তারপর দেখি কিছু ব্যাবহারিক ব্যবহার এবং রুবিতে কীভাবে ইমপ্লিমেন্ট করতে হয়!

গ্রাফের মূলভিত্তি

একটি গ্রাফ দুটি এলিমেন্ট سے গঠিত:

• নোড (বা ভার্টেক্স)
• এজ

এক নোড গ্রাফে একটি এলিমেন্ট রিপ্রেজেন্ট করে, যেন একটি মানচিত্রে শহর বা রাস্তা। আউর এজগুলো নোডগুলোর মধ্যে সংযোগ রিপ্রেজেন্ট করে।

আপনি যদি কম্পিউটার সায়েন্স বা ম্যাথ বইতে তাকান তবে আপনি একটি গ্রাফকে এই ফর্মুলায় সংজ্ঞায়িত দেখবেন: G(V, E)।

যেখানে G মানে গ্রাফ, V হলো ভার্টেক্সের সেট এবং E হলো এজের সেট।

গ্রাফ ডিরেক্টেড বা আনডিরেক্টেড হতে পারে। অর্থাৎ আপনি শুধু এক দিকে যেতে পারেন (ডিরেক্টেড গ্রাফ) বা দুদিকে (আনডিরেক্টেড গ্রাফ)।

সবচেয়ে জনপ্রিয় টাইপের গ্রাফ হলো ডিরেক্টেড এসাইক্লিক গ্রাফ (DAG)। এসাইক্লিক মানে কোনো লুপ নেই, ব্যাকট্র্যাক করার কোনো উপায় নেই।

গ্রাফের ব্যবহার

এখন যেহেতু আমরা ফান্ডামেন্টালের ওভারভিউ দেখেছি, চলুন গ্রাফের কিছু সাধারণ ব্যবহার দেখি।

গ্রাফ ব্যবহার করে আপনি এ জিনিসগুলো করতে পারেন:

• দুটি লোকেশনের মধ্যে সবচেয়ে ছোট (বা বড়) পথ খুঁজে বের করা
• দুটি জিনিস একে অপরের সাথে সম্পর্কিত কিনা চেক করা
• রিকমেন্ডেশন ইঞ্জিন তৈরি করা
• ডিপেন্ডেন্সি বিশ্লেষণ করা

আরেকটি উদাহরণ হলো একটি ডেস্টিনেশনে যেতে সেরা রুট খুঁজে বের করা (GPS ডিভাইস ভাবুন)।

গ্রাফ ইমপ্লিমেন্ট ও ব্যবহার করা

আপনি নিজে গ্রাফ ইমপ্লিমেন্টেশন লিখতে পারেন, কিন্তু এই নিবন্ধে আমরা RGL জেম ব্যবহার করব যেটি ইতিমধ্যে ইমপ্লিমেন্ট করা আছে।

RGL ব্যবহার করে একটি বেসিক গ্রাফ তৈরি করতে:

 require 'rgl/adjacency' graph = RGL::DirectedAdjacencyGraph.new graph.add_edge 1,2 graph.add_edge 3,4 graph.add_edge 1,4 graph.add_edge 4,3 

এই কোডটি নিচের গ্রাফ তৈরি করে:

আপনি আপনার গ্রাফের গ্রাফিক্যাল রিপ্রেজেন্টেশন এইভাবে পেতে পারেন:

 require 'rgl/dot' graph.print_dotted_on 

তারপর সেই মেথডের আউটপুটকে ডট ল্যাঙ্গুয়েজ প্রসেস করতে পারা একটি সাইটে কপি করুন। যেন এইটি।

বিকল্পভাবে, আপনি আপনার মেশিনে Graphviz ইন্সটল করে লোকালি ইমেজ প্রোডিউস করতে পারেন।

এখন যেহেতু আমাদের একটি গ্রাফ আছে, আমরা সেটি ট্রাভার্স করতে চাইতে পারি তার তথ্য জানতে।

আপনার গ্রাফ সার্চ করার জন্য দুটি বেসিক অ্যালগরিদম আছে:

• ব্রেডথ-ফার্স্ট সার্চ (BFS)
• ডেপথ-ফার্স্ট সার্চ (DFS)

BFS-এ আপনি সবচেয়ে নিকটের নোডগুলো প্রথমে পান এবং DFS-এ আপনি প্রতিটি নোডের জন্য যতটা গভীর যেতে পারেন যান। এই অ্যালগরিদমগুলো স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করে ইমপ্লিমেন্ট করা যায়।

RGL জেম ইতিমধ্যে সেই অ্যালগরিদমগুলো ইমপ্লিমেন্ট করে রেখেছে:

 require 'rgl/traversal' graph.bfs_iterator.to_a # [1, 2, 4, 3] graph.dfs_iterator.to_a # [1, 4, 3, 2] 

গ্রাফটি আবার দেখুন এবং আপনার চোখ দিয়ে (অথবা আপনি আঙুলও ব্যবহার করতে পারেন) এই অ্যালগরিদমগুলো যে পথগুলো অনুসরণ করেছে সেগুলো ফলো করুন। এটি আপনাকে বুঝতে সাহায্য করবে কী হচ্ছে।

ওজনযুক্ত গ্রাফ (Weighted Graphs)

আমরা গ্রাফে ওজন (weights) হিসেবে আরও তথ্য যোগ করতে পারি যাতে সেটি আরও উপযোগী হয়।

ওজন এজগুলোর কাছে দেওয়া হয়, যেগুলো দুটি নোডের মধ্যে পথ (রინგের "ভার্টেক্স" হিসাবেও পরিচিত)। এই ওজনগুলো একটি পয়েন্ট থেকে অন্যটিতে যাওয়ার খরচ রিপ্রেজেন্ট করে।

উদাহরণস্বরূপ, যদি আমাদের একটি দেশের মানচিত্র থাকে গ্রাফ রূপে এবং আমরা সম্ভাব্য সবচেয়ে কম সময়ে একটি নির্দিষ্ট ডেস্টিনেশনে পৌঁছাতে চাই, তবে ওজনগুলো দুটি শহরের মধ্যে দূরত্ব হবে।

অথবা যদি আমাদের একটি কম্পিউটার নেটওয়ার্ক থাকে, তবে ওজনগুলো কত হপ লাগে একটি নির্দিষ্ট নেটওয়ার্কে পৌঁছাতে সেটি রিপ্রেজেন্ট করতে পারে।

"কম্পিউটার নেটওয়ার্কিং-এ, একটি হপ হলো সোর্স এবং ডেস্টিনেশনের মধ্যে পথের একটি অংশ। ডেটা প্যাকেট ব্রিজ, রাউটার এবং গেটওয়ে দিয়ে পাস করে যেতে হয় সোর্স থেকে ডেস্টিনেশনে যাওয়ার সময়। প্রতিবার প্যাকেটগুলো পরবর্তী নেটওয়ার্ক ডিভাইসে পাস করা হয়, একটি হপ ঘটে।" — উইকিপিডিয়া

এখানে একটি ওজনযুক্ত গ্রাফের জন্য কোড উদাহরণ:

 graph = RGL::DirectedAdjacencyGraph.new graph.add_vertices "Los Angeles", "New York", "Chicago", "Houston", "Seattle" edge_weights = { ["New York", "Los Angeles"] => 2445, ["Los Angeles", "Chicago"] => 2015, ["Los Angeles", "Houston"] => 1547, ["Chicago", "Houston"] => 939, ["Seattle", "Los Angeles"] => 1548 } edge_weights.each { |(city1, city2), w| graph.add_edge(city1, city2) } 

এখন আমরা একটি পয়েন্ট থেকে অন্যটিতে সবচেয়ে ছোট পথ খুঁজে বের করতে পারি। এবং সেটিই পরবর্তী সেকশনের বিষয়!

সবচেয়ে ছোট পথ খুঁজে বের করা

একটি ওজনযুক্ত গ্রাফের ভিতরে সবচেয়ে ছোট পথ খুঁজে বের করার জন্য একটি জনপ্রিয় অ্যালগরিদম হলো "ডাইজক্স্ট্রার শর্টেস্ট পাথ" অ্যালগরিদম।

একটি ওজনযুক্ত গ্রাফ দেওয়া থাকলে, আমরা ডাইজক্স্ট্রার অ্যালগরিদম ব্যবহার করে এই প্রশ্নের উত্তর দিতে পারি:

"পয়েন্ট A থেকে পয়েন্ট B-এ যেতে সবচেয়ে দ্রুত উপায় কী?"

এখানে একটি কোড উদাহরণ, RGL জেম ব্যবহার করে:

 p graph.dijkstra_shortest_path(edge_weights, "New York", "Houston") # ["New York", "Los Angeles", "Houston"] 

এটি আমাদের নিউ ইয়র্ক থেকে হিউস্টন পর্যন্ত সবচেয়ে ছোট পথ বলে, গ্রাফে উপলব্ধ তথ্য ব্যবহার করে।

সারসংক্ষেপ

আপনি শিখেছেন একটি গ্রাফ ডেটা স্ট্রাকচার কী এবং RGL জেম দিয়ে কীভাবে ব্যবহার করতে হয়।

আপনি গ্রাফের সাথে কাজ করার জন্য সাধারণ অ্যালগরিদমগুলোও শিখেছেন, যেমন DFS, BFS এবং ডাইজক্স্ট্রার।

এই পোস্টটি শেয়ার করা না ভুলেন যদি এটি উপযোগী লাগে যাতে আরও মানুষ এনজয় করতে পারে 🙂