हास्केल में स्थिर डेटा का प्रतिनिधित्व करने का कोई तरीका है? या हैस्केल में डीएफएस ट्रैवर्सल के लिए कोई अन्य सुरुचिपूर्ण एल्गोरिदम है?

Question

मैं रिकर्सिव एल्गोरिदम का उपयोग कर डीएफएस पेड़ बनाने की कोशिश कर रहा हूं। इस के लिए

छद्म कोड है:

DFF(G) 
Mark all nodes u as unvisited 
while there is an unvisited node u do 
    DFS(u) 

।

DFS(u) 
Mark u as visited 
for each v in u's neighbor do 
    if v is not marked 
     DFS(v) 

जबकि मैं काफी आसानी से इस सरल तरीके से अनिवार्य भाषा में, संयुक्त राष्ट्र/दौरा नोड्स के लिए डेटा संरचना में किसी प्रकार का निर्माण उन्हें गतिशील आवंटन या घोषणा के कुछ प्रकार, हास्केल के लिए बताए द्वारा पूरा कर सकते हैं, यह असंभव है ऐसा इसलिए करें क्योंकि हास्केल की शुद्धता मुझे पैरामीटर पास करते समय डेटा बदलने के लिए रोकती है।

data Graph a = Graph [(a,[a])] deriving (Ord, Eq, Show) 
data Tree a = Node a [Tree a] deriving (Ord, Eq, Show) 

type Point = (Int, Int) 
type Edges = [Point] 
type Path = [Point] 

pathGraphFy :: Graph Point -> Point -> Tree (Point,Path) 
pathGraphFy inputGraph point = getPathVertex inputGraph (point,[]) 

getPathVertex :: Graph Point -> (Point, Path) -> Tree (Point,Path) 
getPathVertex inputGraph (point,path) = 
    Node (point,point:path) (map (getPathVertex inputGraph) [(x,(point:path)) | x<- neighbors, x `notElem` path]) 
    where neighbors = pointNeighbor inputGraph point 

pointNeighbor :: Graph Point -> Point -> Edges 
pointNeighbor (Graph (x:xs)) point = 
    if fst x == point then snd x else pointNeighbor (Graph(xs)) point 

यह है कि मैं क्या डीएफएस-ish (या बल्कि BFS-ish) कलन विधि का उपयोग ग्राफ ट्रेवर्सल के लिए मिल गया है है, लेकिन समस्या यह है कि यह सभी बिंदुओं फिर से दौरा करेंगे कि 'अंक रास्ते में नहीं है। (यानी यदि कोई चक्र मौजूद है, तो यह घड़ी के विपरीत और विपरीत दिशा में दोनों तरफ घुमाएगा)

मैंने विज़िट किए गए बिंदुओं के साथ एक और ग्राफ को घुमाने का भी प्रयास किया है, लेकिन विफल रहा है क्योंकि पैरामीटर द्वारा पारित ग्राफ केवल ट्रैवर्सल में ग्राफ का डेटा रखता है (यानी वैश्विक नहीं है)

यदि वैश्विक स्तर के लिए डेटा रखने के लिए केवल गतिशील आवंटन या स्थैतिक डेटा संभव था, तो इसे आसानी से हल किया जा सकता है लेकिन मैं हास्केल के लिए नया हूं और मुझे इस पर वेब पर जवाब नहीं मिल सका मुद्दा। कृपया मेरी मदद करें :(अग्रिम धन्यवाद।

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

Answer 1

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

The paper linked in another उत्तर पत्र तथाकथित अपरिवर्तनीय ग्राफ के उपयोग की बजाय अकादमिक चर्चा प्रदान करता है। सौभाग्य से, कागज के लेखक हास्केल लाइब्रेरी, fgl के रूप में इस दृष्टिकोण को लागू करने के लिए काफी दयालु थे। मैं डेटा को नोड्स और व्हाट्नॉट से जोड़ने के बारे में कुछ विवरणों पर चमकने जा रहा हूं, और दिखाता हूं कि इस पुस्तकालय का उपयोग करके डीएफएस को कैसे कार्यान्वित किया जाए। सूचियों के बजाय पेड़ों का उत्पादन करने के लिए इस एल्गोरिदम को संशोधित करना आसान है, और सूची संस्करण काफी संक्षिप्त है।

dfs :: Graph gr => [Node] -> gr a b -> [Node] 
dfs [] _ = [] 
-- this equation isn't strictly necessary, but it can improve performance for very dense graphs. 
dfs _ g | isEmpty g = [] 
dfs (v:vs) g = case match v g of 
    (Just ctx, g') -> v:dfs (suc' ctx ++ vs) g' 
    _ -> dfs vs g 

कुंजी यहाँ match है, जो इतनी एक शीर्ष और शेष ग्राफ (मैच में वापस लौटकर अपनी Maybe Context, ग्राफ में एक शीर्ष के मामले को कवर नहीं) की Context कहा जाता है में एक ग्राफ विघटित हो जाता है है।

एक शीर्ष Context की धारणा आगमनात्मक रेखांकन के विचार के लिए केंद्रीय है: यह एक टपल

(adjIn, nodeId, nodeLabel, adjOut) 

जहां adjIn और adjOut(edgeLabel, nodeId) जोड़े की सूची नहीं है के रूप में परिभाषित किया है।

ध्यान दें कि शब्द लेबल का उपयोग यहां कम से कम किया जाता है, और यह लंबवत या किनारों से जुड़े सामान्य डेटा को संदर्भित करता है।

suc' फ़ंक्शन एक संदर्भ लेता है और संदर्भ में नोड के उत्तराधिकारी हैं (adjOut, बढ़ते लेबल के साथ)।

हम इस

testGraph :: DynGraph g => gr a b 
testGraph = 
    let nodes = [(i, "N" ++ show i) | i <- [1..5]] 
     edges = [(2,1,"E21") 
       ,(4,1, "E41") 
       ,(1,3, "E13") 
       ,(3,4, "E34") 
       ,(3,5,"E35") 
       ,(5,2, "E52")] 
     withNodes = insNodes nodes empty 
     in insEdges edges withNodes 

कॉलिंग dfs testGraph पैदा करता [1,3,4,5,2] की तरह कोड के साथ इस

की तरह एक ग्राफ बना सकते हैं।

नोट: मैं इस प्रश्न में ऊब गया था और ठोकर खा गया था, इसलिए जवाब सिर्फ कुछ घंटों की जांच और प्रयोगों का लेखन है।

Answer 2

कुछ भी नहीं समारोह तर्क/वापसी मूल्यों में राज्य एन्कोडिंग से आप रहता है एक क्लासिक डीएफएस ऐसा दिखाई दे सकता:।।

import qualified Data.Map as Map 
import qualified Data.Set as Set 

newtype Graph a = Graph (Map.Map a [a]) deriving (Ord, Eq, Show) 
data Tree a = Tree a [Tree a] deriving (Ord, Eq, Show) 

dfs :: (Ord a) => Graph a -> a -> Tree a 
dfs (Graph adj) start = fst $ dfs' (Set.singleton start) start 
    where 
    neighbors x = Map.findWithDefault [] x adj 
    dfs' vis x = 
     let (subtrees, vis') = 
      foldr 
       (\y (subtrees, vis) -> 
       if Set.member y vis 
        then (subtrees, vis) 
        else let vis' = Set.insert y vis 
          (t, vis'') = dfs' vis' y 
         in (t : subtrees, vis'') 
      ) 
       ([], vis) 
       (neighbors x) 
     in (Tree x subtrees, vis') 

Map/Set के बजाय, आप अपने नोड प्रकार के आधार पर persistent hash tables या integer maps/sets का भी उपयोग कर सकते हैं।

स्पष्ट राज्य बचने के लिए आप एक state monad उपयोग करना चाहिए:

import Control.Applicative 
import Control.Monad.State 
import Control.Monad 
import Data.Maybe 
{- ... -} 

dfs :: (Ord a) => Graph a -> a -> Tree a 
dfs (Graph adj) start = evalState (dfs' start) (Set.singleton start) 
    where 
    neighbors x = Map.findWithDefault [] x adj 
    dfs' x = Tree x . catMaybes <$> 
     forM (neighbors x) (\y -> get >>= \vis -> 
     if Set.member y vis 
      then return Nothing 
      else put (Set.insert y vis) >> Just <$> dfs' y)