編輯/更新Haskell中的圖形

Question

我正在使用Data.Graph圖形模擬Haskell中的模擬。仿真僅限於我的圖形模型的2D網格。下面網格上每個點上的一個節點將包含一個Maybe Molecule類型，因此可能存在一個分子或者沒有分子。

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

我已經建立了這種表示，但是當涉及到更新分子的位置時，我覺得我要解決這個問題很長的路要走。到目前爲止，我所做的是將所有節點都刪除到節點列表中。我寫了一個函數來交換這個節點列表中的兩個項目。但是現在當我把所有東西都拉回來時，我遇到了問題，因爲要生成一個新圖，我需要一個頂點列表，我可以從頂點Graph函數輕鬆獲得這些頂點。但我也需要用邊緣觸摸的頂點列表來壓縮。不幸的是，Data.Graph的邊緣Graph函數返回一個類型爲Edge的元組列表，儘管我可以編寫一個函數來派生具有邊緣到頂點的列表頂點，但它並不直接有助於生成圖形。這樣做似乎對我來說足夠的工作，我想知道我是否錯過了一個有一個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) 

你可以嘗試運行swapTest graph地看到，節點4和你的圖7中的標籤交換。

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. 

（如果你有很好的理由來使用圖表，我當然完全在這裏行，在這種情況下，我道歉......）