Редактирование / обновление графиков в Haskell - PullRequest
Новая
       19

Редактирование / обновление графиков в Haskell

8 голосов
/ 20 декабря 2011

Я использую Data.Graph Graph для моделирования симуляции в Haskell.Симуляция ограничена двумерной сеткой, которую моделирует мой график.Узел в каждой точке на сетке ниже будет содержать тип «Может быть, молекула», поэтому может присутствовать молекула или просто ничего. 

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

Я настроил это представление, но когда дело доходит до обновления позициимолекула, я чувствую, я иду долгий путь вокруг проблемы.То, что я сделал до сих пор, это раздетые все узлы в список узлов.Я написал функцию, чтобы поменять местами два элемента в этом списке узлов.Но теперь, когда я возвращаюсь назад, я сталкиваюсь с проблемами, потому что для генерации нового графа мне нужен список вершин, который я легко получаю из функции Graph вершин.Но мне также нужно застегнуть это со списком вершин, к которому касается край.К сожалению, функция Graph ребер Data.Graph возвращает список кортежей типа Edge, который, насколько я вижу, не сразу полезен для генерации графа, хотя я мог бы написать функцию для выведения вершин списка, у которых есть ребра в вершине.Мне кажется, этого достаточно, чтобы задаться вопросом, не упустил ли я точку, есть ли функция Graph, которая просто берет график и возвращает график с обновленным узлом?

Ответы [ 2 ]

8 голосов
/ 20 декабря 2011

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 на диаграмме поменялись местами.

4 голосов
/ 20 декабря 2011

Есть ли конкретная причина, по которой вы используете графики здесь?Мне кажется, что набор ребер в значительной степени фиксирован и что ваши сетки меняются только в положениях молекул.

Почему бы вам просто не использовать массивы или какую-либо другую структуру данных, которая позволяет вам фокусироватьсяна молекулы и их позиции?Например: 

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.

(Если у вас есть веские причины использовать графики, я, конечно, совершенно не согласен, и в этом случае я прошу прощения ...)

...