2011-12-20 20 views
7

Estoy usando un Gráfico de Gráficos de Datos para modelar una simulación en Haskell. La simulación está limitada a una grilla 2D que modela mi gráfico. Un nodo en cada punto de la cuadrícula de abajo contendrá un tipo de Molécula Quizás para que haya una molécula presente o simplemente Nada.Editando/Actualizando Gráficos en Haskell

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

he levantado esta representación, pero cuando se trata de la actualización de la posición de una molécula que siento que voy por el camino largo en torno al tema. Lo que he hecho hasta ahora es quitar todos los nodos a una lista de nodos. He escrito una función para intercambiar los dos elementos en esta lista de nodos. Pero ahora, cuando vuelvo a comprimir todo de nuevo, tengo problemas porque para generar un nuevo gráfico necesito una lista de vértices que obtengo fácilmente de la función de gráfico de vértices. Pero también necesito comprimirlo con la lista de vértices que toca el borde. Desafortunadamente la función Graph de Data.Graph devuelve una lista de tuplas del tipo Edge que no es inmediatamente útil para generar un gráfico hasta donde puedo ver, aunque podría escribir una función para derivar los vértices de la lista que tienen bordes a un vértice. Hacerlo parece ser suficiente trabajo para que me pregunte ¿me estoy perdiendo el punto de que existe una función de Gráfico que simplemente toma un gráfico y devuelve un gráfico con un nodo actualizado?

Respuesta

7

FGL tiene esta gran "contexto" mecanismo que le permite coincidir con el patrón en una consulta de gráfico. Puedes imaginar esto como tirar de un vértice elegido para que quede al lado del resto del gráfico. Esto le permite ver cómo ese vértice está conectado al resto del gráfico.

{-# 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) 

Usted puede intentar ejecutar swapTest graph ver que las etiquetas de los nodos 4 y 7 en su diagrama se intercambian.

4

¿Hay alguna razón particular por la que está utilizando gráficos aquí? Me parece que el conjunto de bordes está bastante fijo y que las cuadrículas solo varían en las posiciones de las moléculas.

¿Por qué no utiliza matrices o alguna otra estructura de datos que le permita centrarse en las moléculas y sus posiciones? Por ejemplo:

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. 

(Si usted tiene buenas razones para utilizar gráficos, Por supuesto, estoy completamente fuera de aquí, en cuyo caso me disculpo ...)

+0

si uso gráficos, puedo ver si los nodos adyacentes están ocupados por otras moléculas para las comprobaciones de detección de colisión. – mikeyP

+0

@mikeyP Pero también puedes hacerlo con arreglos, ¿o no? –

+0

Tienes razón, debajo de un gráfico hay una matriz. Pero con un gráfico podré eliminar nodos en el gráfico, áreas por las que las moléculas no pueden pasar. No veo una forma clara de hacer eso con Arrays. – mikeyP