Chỉnh sửa/Cập nhật Đồ thị trong Haskell

Question

Tôi đang sử dụng Biểu đồ Dữ liệu để mô phỏng mô phỏng trong Haskell. Mô phỏng được giới hạn ở một lưới 2D mà các mô hình đồ thị của tôi. Một nút tại mỗi điểm trên lưới bên dưới sẽ chứa một loại Phân tử Có thể để có thể có một phân tử có mặt hoặc chỉ là Không có gì.

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

Tôi đã thiết lập đại diện này nhưng khi nói đến việc cập nhật vị trí của phân tử, tôi cảm thấy tôi đang đi rất xa xung quanh vấn đề. Những gì tôi đã làm cho đến nay là tước tất cả các nút vào một danh sách các nút. Tôi đã viết một hàm để hoán đổi hai mục trong danh sách các nút này. Nhưng bây giờ khi tôi đến để zip tất cả mọi thứ lại với nhau tôi đi vào vấn đề bởi vì để tạo ra một đồ thị mới, tôi cần một danh sách các đỉnh mà tôi có được dễ dàng từ các chức năng đồ thị đỉnh. Nhưng tôi cũng cần phải nén mà với danh sách các đỉnh chạm cạnh. Rất tiếc, hàm Graph trả về một danh sách các bộ kiểu Edge không có ích để tạo một đồ thị theo như tôi có thể thấy, mặc dù tôi có thể viết một hàm để lấy ra các đỉnh danh sách có cạnh tới đỉnh. Làm như vậy có vẻ là đủ công việc cho tôi để tự hỏi tôi có thiếu điểm là có một chức năng Graph ra khỏi đó mà chỉ mất một đồ thị và trả về một đồ thị với một nút cập nhật?

Answer 1

FGL có "bối cảnh" này lớn cơ chế cho phép bạn khớp mẫu trên truy vấn biểu đồ. Bạn có thể tưởng tượng điều này khi kéo vào một đỉnh đã chọn để nó nằm ở bên cạnh phần còn lại của biểu đồ. Điều này cho phép bạn xem cách mà đỉnh đó được kết nối với phần còn lại của biểu đồ.

{-# 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) 

Bạn có thể thử chạy swapTest graph để xem nhãn cho nút 4 và 7 trong sơ đồ của bạn có hoán đổi không.

Answer 2

Có lý do cụ thể nào khiến bạn đang sử dụng biểu đồ ở đây không? Dường như với tôi rằng tập hợp các cạnh được cố định khá nhiều và lưới của bạn chỉ thay đổi ở vị trí của các phân tử.

Tại sao bạn không chỉ sử dụng mảng hoặc một số cấu trúc dữ liệu khác cho phép bạn tập trung vào các phân tử và vị trí của chúng? Ví dụ:

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. 

(Nếu bạn có lý do chính đáng để sử dụng đồ thị, tôi dĩ nhiên hoàn toàn ra khỏi dòng ở đây, trong trường hợp này tôi xin lỗi ...)