在Haskell中编辑/更新图形

Question

我正在使用Data.Graph Graph来模拟Haskell中的模拟.模拟仅限于我的图形模型的2D网格.下面网格上每个点的节点将包含一个可能的分子类型,因此可能存在分子或只有Nothing.

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的标签是否已交换.