Modifica/aggiornamento di grafici in Haskell

Question

Sto utilizzando un grafico Data.Graph per modellare una simulazione in Haskell. La simulazione è limitata a una griglia 2D che i miei modelli di grafico. Un nodo in ogni punto della griglia sottostante conterrà un tipo di Forse Molecola quindi potrebbe esserci una molecola presente o solo Nulla.

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

Ho creato questa rappresentazione, ma quando si tratta di aggiornare la posizione di una molecola sento che sto andando lungo modo per aggirare il problema. Quello che ho fatto finora è spogliato tutti i nodi in una lista di nodi. Ho scritto una funzione per scambiare i due elementi in questo elenco di nodi. Ma ora, quando arrivo a rimettere tutto a posto, mi capitano dei problemi perché per generare un nuovo grafico ho bisogno di un elenco di vertici che ottengo facilmente dalla funzione Graph dei vertici. Ma devo anche comprimerlo con l'elenco dei vertici che il bordo tocca. Sfortunatamente la funzione Graph di Data.Graph restituisce una lista di tuple di tipo Edge che non è immediatamente utile per generare un grafico per quanto posso vedere, anche se potrei scrivere una funzione per ricavare i vertici della lista che hanno i bordi su un vertice. Fare così sembra essere abbastanza lavoro per me da meravigliarsi mi manca il punto è lì una funzione grafica là fuori che fa solo prendere un grafico e restituire un grafico con un nodo aggiornato?

Answer 1

FGL ha questo grande "contesto" meccanismo che consente di eseguire la corrispondenza del modello su una query del grafico. Puoi immaginarlo come se stessi tirando su un vertice scelto in modo che si posizioni sul lato del resto del grafico. Questo ti permette di vedere come quel vertice è collegato al resto del grafico.

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

Si può provare a eseguire swapTest graph di vedere che le etichette per i nodi 4 e 7 nel diagramma sono scambiati.

Answer 2

C'è un motivo particolare per cui si stanno utilizzando i grafici qui? Mi sembra che l'insieme dei bordi sia praticamente fisso e che le tue griglie differiscano solo nelle posizioni delle molecole.

Perché non usi solo matrici o qualche altra struttura dati che ti permetta di concentrarti sulle molecole e le loro posizioni? Per esempio:

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. 

(Se avete buone ragioni per utilizzare i grafici, sono ovviamente del tutto fuori linea qui, nel qual caso mi scuso ...)