रूबी में प्रैक्टिकल ग्राफ थ्योरी

यह "प्रैक्टिकल कंप्यूटर साइंस" श्रृंखला में अगली किस्त है, जहां आप सीखेंगे कि रूबी का उपयोग करके वास्तविक समस्याओं को हल करने के लिए क्लासिक कंप्यूटर विज्ञान अवधारणाओं को कैसे लागू किया जाए।

आज हम बात करने जा रहे हैं ग्राफ थ्योरी . के बारे में ।

आपने बाइनरी ट्री के बारे में सुना होगा, वे इस तरह दिखते हैं:

बात यह है कि बाइनरी ट्री ग्राफ़ का केवल एक विशिष्ट संस्करण है, जिससे आपको यह पता चल सके कि ग्राफ़ कितने व्यापक हैं।

आइए ग्राफ थ्योरी फंडामेंटल्स के अवलोकन के साथ शुरू करें, फिर हम यह देखने जा रहे हैं कि रूबी में कुछ व्यावहारिक उपयोग क्या हैं और इसे कैसे लागू किया जाए!

ग्राफ की बुनियादी बातें

एक ग्राफ दो तत्वों से बना होता है:

• नोड्स (या कोने)
• किनारों

एक नोड ग्राफ़ में एक तत्व का प्रतिनिधित्व करता है, जैसे शहर या सड़क, एक मानचित्र का प्रतिनिधित्व करने वाले ग्राफ़ में। जबकि किनारे नोड्स के बीच कनेक्शन का प्रतिनिधित्व करते हैं।

यदि आप किसी कंप्यूटर विज्ञान या गणित की पुस्तक को देखते हैं तो आपको इस सूत्र द्वारा परिभाषित एक ग्राफ दिखाई देगा:G(V, E) ।

जहां G मतलब ग्राफ़, V शीर्षों का समुच्चय है और E किनारों का समूह है।

रेखांकन निर्देशित या अप्रत्यक्ष हो सकते हैं। इसका मतलब है कि आप केवल एक दिशा (निर्देशित ग्राफ़) या दोनों दिशाओं (अप्रत्यक्ष ग्राफ़) पर जा सकते हैं।

सबसे लोकप्रिय प्रकार का ग्राफ है निर्देशित चक्रीय ग्राफ (डीएजी)। एसाइक्लिक का मतलब है कि कोई लूप नहीं है, पीछे हटने का कोई रास्ता नहीं है।

ग्राफ़ के लिए उपयोग

अब जबकि हमने बुनियादी बातों का अवलोकन कर लिया है, आइए ग्राफ़ के कुछ सामान्य उपयोग देखें।

ग्राफ़ का उपयोग करके आप निम्न कार्य कर सकते हैं:

• दो स्थानों के बीच सबसे छोटा (या सबसे लंबा) पथ खोजें
• जांचें कि क्या दो चीजें एक दूसरे से संबंधित हैं
• अनुशंसा इंजन बनाएं
• निर्भरता का विश्लेषण करें

एक अन्य उदाहरण में गंतव्य के लिए सबसे अच्छा मार्ग खोजना शामिल है (जीपीएस उपकरणों के बारे में सोचें)।

ग्राफ़ को कैसे लागू करें और उसका उपयोग कैसे करें

आप अपना खुद का ग्राफ कार्यान्वयन लिख सकते हैं, लेकिन इस लेख के लिए हम 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

फिर उस विधि के आउटपुट को उस साइट पर कॉपी करें जो डॉट भाषा को प्रोसेस कर सके। इस तरह।

वैकल्पिक रूप से, आप स्थानीय रूप से छवि बनाने के लिए अपनी मशीन पर ग्राफ़विज़ स्थापित कर सकते हैं।

अब जब हमारे पास एक ग्राफ है, तो हम इसके बारे में जानकारी प्राप्त करने के लिए इसे पार करना चाहेंगे।

आपके ग्राफ़ को खोजने के लिए दो बुनियादी एल्गोरिदम हैं :

• ब्रेडथ-फर्स्ट सर्च (बीएफएस)
• गहराई-पहली खोज (डीएफएस)

बीएफएस में आपको सबसे पहले निकटतम नोड मिलते हैं और डीएफएस में आप हर नोड के लिए जितना संभव हो उतना गहरा जाते हैं। इन एल्गोरिदम को स्टैक डेटा संरचना का उपयोग करके कार्यान्वित किया जा सकता है।

RGL रत्न आपके लिए पहले से ही उन एल्गोरिदम को लागू करता है:

require 'rgl/traversal'

graph.bfs_iterator.to_a
# [1, 2, 4, 3]

graph.dfs_iterator.to_a
# [1, 4, 3, 2]

ग्राफ को फिर से देखें और उस पथ का अनुसरण करें जो इन एल्गोरिदम ने सिर्फ आपकी आंखों का उपयोग करके किया था (या आप चाहें तो एक उंगली का भी उपयोग कर सकते हैं)। इससे आपको यह समझने में मदद मिलेगी कि क्या हो रहा है।

भारित ग्राफ़

ग्राफ़ को अधिक उपयोगी बनाने के लिए हम वज़न के रूप में अधिक जानकारी जोड़ सकते हैं।

किनारों को वज़न दिया जाता है, जो दो नोड्स के बीच के पथ . हैं (जिसे "कोने" के रूप में भी जाना जाता है)। ये भार एक बिंदु से दूसरे स्थान पर जाने की लागत का प्रतिनिधित्व करते हैं।

उदाहरण के लिए, यदि हमारे पास ग्राफ के रूप में किसी देश का नक्शा है और हम कम से कम समय में एक निश्चित गंतव्य तक पहुंचना चाहते हैं, तो वजन दो शहरों के बीच की दूरी का प्रतिनिधित्व करेगा।

या यदि हमारे पास एक कंप्यूटर नेटवर्क है, तो वज़न यह दर्शा सकता है कि एक निश्चित नेटवर्क तक पहुँचने में कितने हॉप्स लगते हैं।

"कंप्यूटर नेटवर्किंग में, हॉप स्रोत और गंतव्य के बीच पथ का एक हिस्सा है। स्रोत और गंतव्य के बीच यात्रा करते समय डेटा पैकेट ब्रिज, राउटर और गेटवे से गुजरते हैं। हर बार पैकेट को अगले नेटवर्क डिवाइस में पास किया जाता है, एक हॉप होता है।" - विकिपीडिया

भारित ग्राफ़ के लिए यहां एक कोड उदाहरण दिया गया है:

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 रत्न के साथ इसका उपयोग कैसे किया जाता है।

आपने डीएफएस, बीएफएस और डिजस्ट्रा जैसे ग्राफ़ के साथ काम करने के लिए सामान्य एल्गोरिदम के बारे में भी सीखा है।

इस पोस्ट को शेयर करना न भूलें यदि आप इसे उपयोगी पाते हैं तो अधिक लोग इसका आनंद ले सकते हैं 🙂