एक विकल्प आगमनात्मक रेखांकन है, जो का प्रतिनिधित्व करने और मनमाने ढंग से ग्राफ संरचनाओं के साथ काम करने का एक तरीका है कार्यात्मक उपयोग करने के लिए है। उन्हें हास्केल के fgl लाइब्रेरी द्वारा प्रदान किया गया है और मार्टिन एरविग द्वारा "Inductive Graphs and Funtional Graph Algorithms" में वर्णित किया गया है।
एक सज्जन परिचय के लिए (चित्रण के साथ!), मेरे ब्लॉग पोस्ट Generating Mazes with Inductive Graphs देखें।
अपरिवर्तनीय ग्राफ के साथ चाल यह है कि वे आपको ग्राफ़ पर पैटर्न मिलान देते हैं। सूचियों के साथ काम करने के लिए आम कार्यात्मक मुहावरा उन्हें एक सिर तत्व और सूची के बाकी में विघटित है, तो उस पर recurse:
map f [] = []
map f (x:xs) = f x : map f xs
प्रेरक रेखांकन आप एक ही काम करते हैं, लेकिन रेखांकन के लिए। आप एक नोड, उसके किनारों और शेष ग्राफ में एक अपरिवर्तनीय ग्राफ विघटित कर सकते हैं।
pattern matching on a node http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/match1.png
यहाँ हम नोड 1 और उसके किनारों के सभी (नीले रंग में हाइलाइट), ग्राफ के बाकी हिस्सों से अलग पर मेल खाते हैं।
यह हमें रेखांकन के लिए एक map लिखने (Haskellish स्यूडोकोड कि पैटर्न समानार्थक शब्द के साथ महसूस किया जा सकता में) कर सकते हैं:
gmap f Empty = Empty
gmap f ((in, node, out) :& rest) = f (in, node, out) :& gmap f rest
के रूप में सूचियों का विरोध करने के लिए इस दृष्टिकोण का मुख्य कमी है कि रेखांकन एक नहीं है विघटन करने का एक प्राकृतिक तरीका: एक ही ग्राफ कई तरीकों से बनाया जा सकता है। उपरोक्त नक्शा कोड सभी शीर्षकों पर जायेगा, लेकिन मनमाने ढंग से (कार्यान्वयन-निर्भर) आदेश में।
इसे दूर करने के लिए, हम एक और निर्माण जोड़ते हैं: match फ़ंक्शन जो एक विशिष्ट नोड लेता है। यदि वह नोड हमारे ग्राफ में है, तो हम ऊपर की तरह एक सफल मैच प्राप्त करते हैं; यदि यह नहीं है, तो पूरा मैच विफल रहता है।
यह निर्माण एक डीएफएस या बीएफएस लिखने के लिए पर्याप्त है- सुरुचिपूर्ण कोड के साथ जो दोनों के लिए लगभग समान दिखता है!
मैन्युअल अंकन नोड्स के रूप में दौरा किया है, हम बस नोड अब हम देख रहे हैं छोड़कर ग्राफ
के बाकी पर recurse की बजाय: हर कदम पर, हम मूल ग्राफ की एक और छोटे छोटे हिस्से के साथ काम कर रहे हैं । अगर हम किसी नोड तक पहुंचने का प्रयास करते हैं तो हम पहले से ही match के साथ देख चुके हैं, यह शेष ग्राफ में नहीं होगा और वह शाखा विफल हो जाएगी। इससे हमारे ग्राफ-प्रसंस्करण कोड सूचियों पर हमारे सामान्य रिकर्सिव फ़ंक्शंस की तरह दिखते हैं।
इस प्रकार के ग्राफ के लिए यहां एक डीएफएस है। यह सूची (फ्रंटियर) के रूप में पर जाने के लिए नोड्स के ढेर को रखता है, और प्रारंभिक सीमा शुरू करने के लिए लेता है। आउटपुट क्रम में घुसने वाले नोड्स की एक सूची है। (यहाँ सटीक कोड कुछ कस्टम पैटर्न समानार्थी शब्दों के बिना सीधे पुस्तकालय के साथ लिखा नहीं किया जा सकता।)
dfs _frontier Empty = []
dfs [] _graph = []
dfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
dfs (neighbors' ctx ++ ns) rest
dfs (n:ns) graph = -- visited n
dfs ns graph
एक बहुत सरल पुनरावर्ती क्रिया। यह एक चौड़ाई-पहले खोज में चालू करने के लिए, सभी हम क्या करना है एक कतार के साथ हमारे ढेर सीमा की जगह है: सूची के सामने पर पड़ोसियों डालने के बजाय, हम उन्हें पर वापस डाल:
bfs _frontier Empty = []
bfs [] _graph = []
bfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
bfs (ns ++ neighbors' ctx) rest
bfs (n:ns) graph = -- visited n
bfs ns graph
हाँ, हमें बस इतना ही चाहिए! जब हम ग्राफ पर भर्ती करते हैं, तो हमें नोड्स का ट्रैक रखने के लिए कुछ भी विशेष करने की ज़रूरत नहीं होती है, जैसे कि हमें हमारे द्वारा देखी गई सूची कक्षों का ट्रैक रखने की आवश्यकता नहीं होती है: हर बार जब हम पुन: कार्य करते हैं, तो हम ' केवल ग्राफ़ का हिस्सा प्राप्त करने के बाद हम नहीं देखे गए हैं।
पायथन में आप 'ओ (एन) 'के बजाय लुकअप' ओ (1) 'बनाकर, देखे गए नोड्स का' सेट 'बना सकते हैं। – jonrsharpe
मैं शर्त लगाता हूं, * monads * इसे संभाल सकता है .. –
उपयुक्त डेटा संरचना * नहीं * गेम का उद्देश्य कैसे उपयोग कर रहा है? – chepner