हास्केल

Question

में ग्राफ (शायद निर्देशित या अप्रत्यक्ष) के चक्रों का पता लगाना मैंने इस समस्या को अनिवार्य तरीके से हल करना शुरू किया और यह काम करता है (पारंपरिक तीन रंग तकनीकों के साथ डीएफएस)। हालांकि, मुझे यह पता लगाने में तीन गुना समय लगता है कि हास्केल को कैसे किया जाए और मैं असफल रहा! मान लीजिए कि मैं अपने आसन्न नोड्स के साथ नोड के सूची (या मानचित्र) के रूप में ग्राफ़ का प्रतिनिधित्व करता हूं।

type Node = Int 
type Graph = [(Node, [Node])] 

नोट करें उपर्युक्त प्रतिनिधित्व निर्देशित या अप्रत्यक्ष किया जा सकता है। मैं बैक ट्रैक एज का पता लगाने के लिए खोज करते समय देखा गया सेट और समाप्त सेट को तर्क के रूप में भी पास करता हूं (क्योंकि कार्यात्मक में कोई दुष्प्रभाव पसंद नहीं किया जाता है)। हालांकि, मैं इसे हास्केल में नहीं कर सकता! मुझे पता है कि राज्य मोनड का उपयोग हो सकता है, लेकिन यह बात मेरे दिमाग से काफी अच्छी तरह से नहीं आई है। मुझे यह जानकर उत्सुकता है कि कोई भी मुझे "सुंदर" हास्केल शैली में कैसे करना है?

Answer 1

शायद मैं सिर्फ और components और इसी तरह के अंतर्निहित डीएफएस कार्यों का उपयोग करता हूं।

Answer 2

सबसे पहले, हास्केल में ग्राफ संग्रहीत करने के लिए डेटा प्रकार है; इसे containers पैकेज में कहा जाता है। यह सूची के बजाय Data.Array का उपयोग करता है, लेकिन अन्यथा आपके प्रतिनिधित्व के समान है।

type Graph = Array Int [Int] 

यह प्रतिनिधित्व बहुत कम स्मृति का उपयोग करते हुए, अधिक कुशल ग्राफ की ओर जाता है। मैं इस पुस्तकालय का उपयोग इस प्रकार करता हूं:

import Data.Graph (Graph) 
import qualified Data.Graph as Graph 
import Data.Array 

संभवतः आप अपने ग्राफ में न्यूनतम और अधिकतम नोड्स को जानते हैं; यदि नहीं, तो इस समारोह आप के लिए उन्हें गणना करता है और बनाता है एक Graph: अगर एक नोड एक चक्र का हिस्सा है

makeGraph :: [(Node, [Node])] -> Graph 
makeGraph list = 
    array (minimum nodes, maximum nodes) list 
    where 
    nodes = map fst list 

देखने के लिए, एक, एक नोड से जांच करना चाहिए कि क्या नोड्स पहुंच योग्य नोड को छोड़कर ही है, जिसमें यह शामिल हो नोड। किसी दिए गए नोड (उस नोड सहित) से पहुंचने योग्य नोड्स प्राप्त करने के लिए कोई reachable फ़ंक्शन का उपयोग कर सकता है। चूंकि GraphArray है, इसलिए टाइप किए गए सूची को वापस पाने के लिए assocs का उपयोग कर सकते हैं। हम इन तीन तथ्यों का उपयोग दो कार्यों के निर्माण के लिए:

-- | Calculates all the nodes that are part of cycles in a graph. 
cyclicNodes :: Graph -> [Node] 
cyclicNodes graph = 
    map fst . filter isCyclicAssoc . assocs $ graph 
    where 
    isCyclicAssoc = uncurry $ reachableFromAny graph 

-- | In the specified graph, can the specified node be reached, starting out 
-- from any of the specified vertices? 
reachableFromAny :: Graph -> Node -> [Node] -> Bool 
reachableFromAny graph node = 
    elem node . concatMap (Graph.reachable graph) 

आप कैसे reachable समारोह काम करता है, मैं इसके बारे में सभी के माध्यम से यहां जा सकता है में रुचि रखते हैं, लेकिन यह समझने के लिए जब आप the code को देखने काफी सीधी-सपाट है ।

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

ध्यान दें कि मैं इस तथ्य कोस रहा है कि इस मामले में Node ~ Graph.Vertex ~ Int, इसलिए यदि आपके Node रों परिवर्तन प्रकार, आप graphFromEdges तरह Data.Graph में उचित रूपांतरण कार्यों का उपयोग करने के लिए, एक Graph और संबद्ध रूपांतरण कार्यों पाने के लिए की जरूरत है।

fgl लाइब्रेरी एक और विकल्प है जो ग्राफ-संबंधित कार्यक्षमता का एक पूर्ण सूट भी प्रदान करता है जो बेहद अनुकूलित है।

Answer 3

यह प्रयास के अनुभवहीन तरीका नहीं है, कि इस तरह दिखता है:

route :: Graph -> Label -> Label -> Bool 
route g dest from | from == dest = True 
route g dest from = any (route g dest) (neighbours g from) 

लेकिन उस रेखांकन पाशन में विफल रहता है। (मुझे यह भी लगता है कि आपके पास पड़ोसियों को परिभाषित किया गया है)

तो, क्या करना है लेकिन पहले से देखे गए नोड्स की सूची को पास करना है।

route2 :: Graph -> Label -> Label -> [Label] -> Bool 
route2 g dest from seen 
    | dest == from = True 
    | otherwise = any (\x -> route2 g dest x (from:seen)) (neighbours g from) 

लेकिन अगर आप ग्राफ यहाँ पर यह चल रहे थे। आप एक निशान है कि (कुछ इस तरह योजना बहाना देखा मिलेगा, मैं बेशर्म मेरी सीएस वर्ग से इन चित्रों को चोरी कर लिया है fr है खोजने के मार्ग, और fr-एल कि एक सूची लेता है इसका एक संस्करण है। दूसरा पैरामीटर संचायक)

आप देख सकते हैं है, यह नोड्स कश्मीर और एच दो बार दौरा समाप्त होता है। यह बुरा है, देखते हैं कि यह क्यों कर रहा है।

चूंकि यह any में रिकर्सिव कॉल से किसी भी जानकारी का बैक अप नहीं लेता है, तो यह नहीं देख सकता कि यह शाखाओं में क्या हुआ जो असफल रहा, केवल वर्तमान नोड के पथ पर क्या था।

अब इसे ठीक करने के लिए, हम दो पथ ले सकते हैं। मेरी कक्षा ने एक सतत उत्तीर्ण दृष्टिकोण लिया जो कि उपन्यास है, इसलिए मैं इसे राज्य के मोनड संस्करण से पहले दिखाऊंगा।

routeC :: Graph -> Label -> Label -> [Label] -> ([Label] -> Bool) -> Bool 
routeC g dest from seen k 
    | dest == from  = True 
    | from `elem` seen = k (from:seen) 
    | otherwise  = routeCl g dest (neighbours g from) (from:seen) k 

routeCl :: Graph -> Label -> [Label] -> [Label] -> ([Label] -> Bool) -> Bool 
routeCl g dest []  seen k = k seen 
routeCl g dest (x:xs) seen k = 
    routeC g dest x seen (\newSeen -> routeCl g dest xs newSeen k) 

यह किसी भी के बजाय कार्यों की एक जोड़ी का उपयोग करता है। routeC बस यह देखने के लिए जांचता है कि क्या हम गंतव्य पर पहुंचे हैं, या यदि हमने लूप किया है, अन्यथा यह वर्तमान नोड के पड़ोसियों के साथ रूटसीएल को कॉल करता है।

यदि हमने लूप किया है, तो केवल False लौटने की बजाय, हम निरंतरता को कॉल करते हैं, लेकिन उन नोड्स के साथ जिन्हें हमने वर्तमान में देखा है (वर्तमान में सहित)।

routeCL नोड्स की एक सूची लेता है, और यदि सूची खाली है, तो निरंतरता चलाता है, अन्यथा यह कुछ दिलचस्प करता है। यह पहले नोड पर routeC चलाता है, और इसे एक निरंतरता पास करता है जो शेष नोड्स की नई सूची के साथ शेष सूची में routeCl चलाएगा। तो यह असफल शाखाओं के इतिहास में देखने में सक्षम हो जाएगा।

(एक अतिरिक्त चीज़ के रूप में, हम इसे थोड़ा और सामान्य कर सकते हैं, और इसे निरंतर उत्तीर्ण शैली में बदल सकते हैं। मैंने कार्यों की जोड़ी का उपयोग करने के बजाय किसी भी को सामान्यीकृत किया है। यह वैकल्पिक है, और प्रकार हस्ताक्षर आप के लिए, राज्य इकाई संस्करण क्या इंतजार कर रहे थे के लिए,

anyK :: (a -> s -> (s -> r) -> (s -> r) -> r) -> 
     [a] -> s -> (s -> r) -> (s -> r) -> r 
anyK p []  s tK fK = fK s 
anyK p (x:xs) s tK fK = p x s tK (\s' -> anyK p xs s' tK fK) 

routeK2 :: Graph -> Label -> Label -> ([Label] -> r) -> ([Label] -> r) -> r 
routeK2 g dest from' trueK falseK = route from' [] trueK falseK 
    where route from seen tK fK 
     | from == dest = tK seen 
     | from `elem` seen = fK seen 
     | otherwise = anyK route (neighbours g from) (from:seen) tK fK 

यही बात है, लेकिन अधिक जानकारी के साथ में पारित किया जा रहा कोड से डरावना है।)।

अब।

routeS :: Graph -> Label -> Label -> State [Label] Bool 
routeS g dest from | dest == from = return True 
routeS g dest from = do 
     seen <- get 
     if from `elem` seen then return False else do 
     put (from:seen) 
     anyM (routeS g dest) (neighbours g from) 

लेकिन उस अंतिम पंक्ति, क्या हम साथ शुरू की तरह एक बहुत कुछ नहीं दिखता है तो बस कुछ अतिरिक्त पाइपलाइन के साथ? तुलना करें:

any (route g dest) (neighbours g from) -- Simple version 
anyM (routeS g dest) (neighbours g from) -- State Version 
anyK route   (neighbours g from) (from:seen) tK fK -- CPS version 

कोर पर, सभी तीन एक ही काम कर रहे हैं। राज्य संस्करण में मोनड हमारे लिए देखे गए नोड्स की नलसाजी को अच्छी तरह से संभालता है।और सीपीएस संस्करण हमें दिखाता है कि राज्य के मोनैड की तुलना में अधिक स्पष्ट फैशन में नियंत्रण का प्रवाह कैसा होगा।

ओह, लेकिन anyM मानक लाइब्रेरी में प्रतीत नहीं होता है। यहां यह दिखता है:

anyM :: (Monad m) => (a -> m Bool) -> [a] -> m Bool 
anyM p [] = return False 
anyM p (x:xs) = do 
    y <- p x 
    if y 
     then return True 
     else anyM p xs