在Haskell中编辑/更新图表

Question

我正在使用Data.Graph Graph来模拟Haskell中的一个仿真。这个仿真被限制在一个2D网格内，我的图形模型也是如此。在网格上每个点上的节点将包含一个Maybe Molecule类型，因此可能存在分子或仅为Nothing。

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

我已经建立了这个表示，但是当我需要更新一个分子的位置时，我感觉自己在绕弯路。目前为止，我已经将所有节点剥离成一个节点列表。我编写了一个函数来交换这个节点列表中的两个项目。但是现在当我尝试将所有内容重新压缩在一起时，我遇到了问题，因为要生成一个新图形，我需要一个顶点列表，而我可以轻松从Graph函数的顶点中获取。但是，我还需要将其与边缘接触的顶点列表压缩在一起。不幸的是，Data.Graph的edges Graph函数返回Edge类型的元组列表，这对于我来说并不是立即有用的，虽然我可以编写一个函数来推导具有连接到顶点的边缘的顶点列表。这样做似乎足够让我想知道是否我错过了点什么，是否有一个Graph函数存在，它只需要一个图形，并返回一个带有更新节点的图形？

- mikeyP

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的标签是否被交换。

- Anthony

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.

（如果您有使用图形的充分理由，那么我当然是不正确的，如果是这样，我道歉...）

- Stefan Holdermans

---

如果我使用图形，我可以看到相邻节点是否被其他分子占据，以进行碰撞检测。 - mikeyP

@mikeyP 但是你也可以用数组来做到这一点，不是吗？ - Stefan Holdermans

你说得对，在图形下面是一个数组。但是用图形，我可以删除图形上的节点，也可以划定分子无法穿过的区域。使用数组，并不会有一个简洁的方法来实现这一点。 - mikeyP