하스켈에서 그래프 편집/업데이트

Question

하스켈에서 시뮬레이션을 모델링하기 위해 Data.Graph 그래프를 사용하고 있습니다. 시뮬레이션은 내 그래프 모델 인 2D 그리드로 제한됩니다. 아래 그리드의 각 점에있는 노드에는 Maybe Molecule 유형이 포함되어 있으므로 분자가 있거나 아니면 아무 것도 없을 수 있습니다.

1 - 2 - 3 
| | | 
4 - 5 - 6 
| | | 
7 - 8 - 9 

나는이 표현을 설정하지만, 한 그것은 내가이 문제를 해결 먼 길을 갈거야 기분이 분자의 위치를 ​​업데이트하기 때. 지금까지 내가 한 것은 모든 노드를 노드 목록으로 제거한 것입니다. 이 노드 목록에서 두 항목을 서로 바꾸는 함수를 작성했습니다. 그러나 이제는 모든 것을 다시 집어 넣으려고 할 때 문제가 생깁니다. 새 그래프를 생성하려면 꼭 그래프 그래프 함수에서 쉽게 얻을 수있는 꼭지점 목록이 필요합니다. 하지만 꼭지점 목록에서 지퍼를 눌러야합니다. 불행히도 Data.Graph의 가장자리 그래프 함수는 내가 볼 수있는 한 그래프를 생성하는 데 즉시 도움이되지 않는 유형의 튜플 목록을 반환합니다. 그러나 꼭지점에 대한 가장자리를 가진 목록 꼭지점을 유도하는 함수를 작성할 수는 있습니다. 그렇게하면 저에게 그래프를 가져 와서 업데이트 된 노드가있는 그래프를 반환하는 Graph 함수가 있다는 점을 놓치고 싶습니다.

Answer 1

FGL이 위대한 "컨텍스트"가 메커니즘을 사용하면 그래프 쿼리에서 패턴 일치를 수행 할 수 있습니다. 선택된 꼭지점을 잡아 당겨서 그래프의 나머지 부분에 위치하도록 상상할 수 있습니다. 이를 통해 해당 버텍스가 나머지 그래프에 어떻게 연결되어 있는지 볼 수 있습니다.

{-# LANGUAGE TupleSections #-} 
import Control.Applicative 
import Control.Arrow 
import Data.Graph.Inductive 

-- Example graph from SO question. 
graph :: Gr (Maybe Int)() 
graph = mkGraph (map (id&&&Just) [1,2,3,4,5,6,7,8,9]) 
       (map (\(x,y) -> (x,y,())) $ 
        concatMap gridNeighbors [1..9]) 
    where gridNeighbors n = map (n,) 
         . filter ((&&) <$> valid <*> not . boundary n) 
         $ [n-3,n-1,n+1,n+3] 
     valid x = x > 0 && x < 10 
     boundary n x = case n `rem` 3 of 
         0 -> x == n + 1 
         1 -> x == n - 1 
         _ -> False 

-- Swap the labels of nodes 4 and 7 
swapTest g = case match 4 g of 
       (Just c4, g') -> case match 7 g' of 
            (Just c7, g'') -> setLabel c4 (lab' c7) & 
                (setLabel c7 (lab' c4) & 
                g'') 
            _ -> error "No node 7!" 
       _ -> error "No node 4!" 
    where setLabel :: Context a b -> a -> Context a b 
     setLabel (inEdges, n, _, outEdges) l = (inEdges, n, l, outEdges) 

당신은 노드 4와 그림 7의 레이블이 교환되는 것을 볼 수 swapTest graph을 실행 시도 할 수 있습니다.

Answer 2

여기에 그래프를 사용하는 특별한 이유가 있습니까? 가장자리 집합은 꽤 고정되어 있고 그리드는 분자의 위치 만 다릅니다.

배열이나 분자 및 그 위치에 집중할 수있는 다른 데이터 구조를 사용하는 이유는 무엇입니까? 예를 들면 :

import Data.Array 

data Molecule = H2O | CO2 | NH3 

type Grid = Array (Int, Int) (Maybe Molecule) 

-- creates an empty grid               
grid :: Int -> Int -> Grid 
grid m n = array ((0, 0), (m - 1, n - 1)) assocs 
    where 
    assocs = [((i, j), Nothing) | i <- [0 .. m - 1], j <- [0 .. n - 1]] 

-- swap the molecules at the specified indices         
swap :: (Int, Int) -> (Int, Int) -> Grid -> Grid 
swap (i, j) (u, v) grid = 
    grid // [((i, j), grid ! (u, v)), ((u, v), grid ! (i, j))] 

-- etc. 

(당신이 그래프를 사용하는 이유가 있다면, 내가 ... 내가 사과하는 경우에, 완전히 여기 온라인에서 물론입니다)