एफजीएल

Question

के साथ सबसे छोटा रास्ता ढूंढना मैं निम्नलिखित सरल निर्देशित भारित ग्राफ का प्रतिनिधित्व करने के लिए मार्टिन एर्विग की कार्यात्मक ग्राफ लाइब्रेरी (एफजीएल) का उपयोग कर रहा हूं।

genLNodes :: [LNode String] 
genLNodes = zip [1..5] ["A","B","C","D","E"] 

genLEdges :: [LEdge Int] 
genLEdges = [(1,2,4),(1,3,1),(2,4,2),(3,4,2),(2,5,1),(4,5,1), 
      (2,1,4),(3,1,1),(4,2,2),(4,3,2),(5,2,1),(5,4,1)] 

mygraph :: Gr String Int 
mygraph = mkGraph genLNodes genLEdges 

अब मैं एक और उदाहरण के लिए एक नोड से कम से कम पथ लगाना चाहते हैं A से E डिजस्ट्रा के एल्गोरिदम का उपयोग कर। वहाँ Data.Graph.Inductive.Query.SP में ऐसा करने के लिए एक समारोह हो रहा है:

dijkstra :: (Graph gr, Real b) => Heap b (LPath b) -> gr a b -> LRTree b 

लेकिन मैं कैसे प्रदान किए गए इंटरफ़ेस से इसका इस्तेमाल करने की यह पता लगाने में सक्षम नहीं हूँ। कोई भी सहायताकाफी प्रशंसनीय होगी। अगर मैं निर्देशित भारित ग्राफ को सही तरीके से बना रहा हूं, या यदि ऐसा करने के लिए कोई अन्य (बेहतर) पैकेज है, तो मैं किसी अन्य सुझाव को भी सुनना चाहूंगा?

Answer 1

दो नोड्स के बीच कम से कम पथ पाने के लिए, मॉड्यूल एक विशेष समारोह, sp, तो सबसे आसान तरीका सबसे छोटा रास्ता पाने के लिए ("कम से कम पथ", शायद का संक्षिप्त रूप) प्रदान करता है

sp 1 5 mygraph 

sp है dijkstra उपयोग करता है:

spTree :: (Graph gr, Real b) => Node -> gr a b -> LRTree b 
spTree v = dijkstra (H.unit 0 (LP [(v,0)])) 

sp :: (Graph gr, Real b) => Node -> Node -> gr a b -> Path 
sp s t = getLPathNodes t . spTree s 

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