Haskellでグラフを編集/更新する

Question

私はHaskellでシミュレーションをモデル化するためにData.Graphグラフを使用しています。シミュレーションは、私のグラフモデルの2Dグリッドに限定されています。下のグリッド上の各ポイントのノードには、Maybe Moleculeタイプが含まれているので、分子が存在するか、まったく存在しない可能性があります。

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

私はこの表現を設定しているが、それは私が、私は問題の周りの長い道のりを行くよ感じる分子の位置を更新することになると。私がこれまで行ってきたことは、すべてのノードをノードのリストに取り除いたものです。私はこのノードのリストにある2つのアイテムを交換する関数を書いています。しかし、今私がすべてを一緒に戻すようになったら、問題に遭遇します。なぜなら、新しいグラフを生成するためには、頂点グラフ関数から簡単に得られる頂点のリストが必要だからです。しかし、私はまた、エッジが触れる頂点のリストでそれを圧縮する必要があります。残念ながら、Data.Graphのedgesグラフ関数は、頂点までの辺を持つリスト頂点を派生させる関数を書くことができるけれども、私が見る限り、グラフを生成するのに直ちに役に立たない、タイプがEdgeのタプルのリストを返します。そうすることは、私がポイントを見逃しているのを驚かせるのに十分な仕事であるようです。そこには、グラフを取り、更新されたノードを持つグラフを返すグラフ関数がありますか？

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. 

（あなたはグラフを使用するには十分な理由がある場合は、私は私が謝罪、その場合には、ここで完全にラインのうち、もちろんだ...）