¿Cómo se representa un gráfico en Haskell?

Es bastante fácil representar un árbol o una lista en Haskell utilizando tipos de datos algebraicos. Pero, ¿cómo harías para representar tipográficamente un gráfico? Parece que necesitas tener punteros. Supongo que podrías tener algo como

type Nodetag = String
type Neighbours = [Nodetag]
data Node a = Node a Nodetag Neighbours

Y eso sería viable. Sin embargo, se siente un poco desacoplado; Los enlaces entre diferentes nodos en la estructura realmente no "se sienten" tan sólidos como los enlaces entre los elementos actuales anteriores y siguientes en una lista, o los padres e hijos de un nodo en un árbol. Tengo el presentimiento de que realizar manipulaciones algebraicas en el gráfico, tal como lo definí, se vería obstaculizado por el nivel de indirección introducido a través del sistema de etiquetas.

Es principalmente este sentimiento de duda y percepción de inelegancia lo que me hace hacer esta pregunta. ¿Existe una forma mejor / más matemáticamente elegante de definir gráficos en Haskell? ¿O me he topado con algo inherentemente duro / fundamental? Las estructuras de datos recursivas son dulces, pero esto parece ser otra cosa. Una estructura de datos autorreferencial en un sentido diferente a cómo los árboles y las listas son autorreferenciales. Es como si las listas y los árboles fueran autorreferenciales a nivel de tipo, pero los gráficos son autorreferenciales a nivel de valor.

Entonces, ¿qué está pasando realmente?

También me resulta incómodo tratar de representar estructuras de datos con ciclos en un lenguaje puro. Son los ciclos los que realmente son el problema; porque los valores se pueden compartir, cualquier ADT que pueda contener un miembro del tipo (incluidas listas y árboles) es realmente un DAG (Gráfico Acíclico Dirigido). El problema fundamental es que si tiene valores A y B, con A que contiene B y B que contiene A, entonces ninguno puede crearse antes de que exista el otro. Debido a que Haskell es perezoso, puedes usar un truco conocido como Tying the Knot para evitar esto, pero eso hace que me duela el cerebro (porque todavía no lo he hecho mucho). He hecho más de mi programación sustancial en Mercurio que Haskell hasta ahora, y Mercurio es estricto, por lo que atar nudos no ayuda.

Por lo general, cuando me he encontrado con esto antes, he recurrido a la indirección adicional, como estás sugiriendo; a menudo mediante el uso de un mapa de identificadores a los elementos reales, y tener elementos que contienen referencias a los identificadores en lugar de a otros elementos. Lo principal que no me gustó de hacer eso (aparte de la ineficiencia obvia) es que se sintió más frágil, introduciendo los posibles errores de buscar una identificación que no existe o tratar de asignar la misma identificación a más de uno elemento. Puede escribir código para que estos errores no ocurran, por supuesto, e incluso ocultarlo detrás de abstracciones para que los únicos lugares donde tales errores puedan ocurrir estén limitados. Pero todavía es una cosa más equivocarse.

Sin embargo, un rápido google para el "gráfico de Haskell" me llevó a http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling , que parece una lectura que vale la pena.

En la respuesta de shang puedes ver cómo representar un gráfico usando la pereza. El problema con estas representaciones es que son muy difíciles de cambiar. El truco de atar nudos es útil solo si vas a construir un gráfico una vez, y luego nunca cambia.

En la práctica, si realmente quisiera hacer algo con mi gráfico, utilizo las representaciones más peatonales:

• Lista de borde
• Lista de adyacencia
• Dé una etiqueta única a cada nodo, use la etiqueta en lugar de un puntero y mantenga un mapa finito de etiquetas a nodos

Si va a cambiar o editar el gráfico con frecuencia, le recomiendo usar una representación basada en la cremallera de Huet. Esta es la representación utilizada internamente en GHC para gráficos de flujo de control. Usted puede leer sobre ello aquí:

• Un gráfico de control de flujo aplicativo basado en la cremallera de Huet

• Hoopl: una biblioteca modular y reutilizable para el análisis y la transformación del flujo de datos

Como mencionó Ben, los datos cíclicos en Haskell se construyen mediante un mecanismo llamado "atar el nudo". En la práctica, significa que escribimos declaraciones recursivas recíprocas usando leto wherecláusulas, lo que funciona porque las partes recursivas recíprocas se evalúan perezosamente.

Aquí hay un ejemplo de tipo de gráfico:

import Data.Maybe (fromJust)

data Node a = Node
    { label    :: a
    , adjacent :: [Node a]
    }

data Graph a = Graph [Node a]

Como puede ver, usamos Nodereferencias reales en lugar de indirección. Aquí se explica cómo implementar una función que construya el gráfico a partir de una lista de asociaciones de etiquetas.

mkGraph :: Eq a => [(a, [a])] -> Graph a
mkGraph links = Graph $ map snd nodeLookupList where

    mkNode (lbl, adj) = (lbl, Node lbl $ map lookupNode adj)

    nodeLookupList = map mkNode links

    lookupNode lbl = fromJust $ lookup lbl nodeLookupList

Tomamos una lista de (nodeLabel, [adjacentLabel])pares y construimos los Nodevalores reales a través de una lista de búsqueda intermedia (que hace el nudo real). El truco es que nodeLookupList(que tiene el tipo [(a, Node a)]) se construye utilizando mkNode, lo que a su vez se refiere nodeLookupListal encontrar los nodos adyacentes.

Es cierto, los gráficos no son algebraicos. Para solucionar este problema, tiene un par de opciones:

1. En lugar de gráficos, considere árboles infinitos. Representa los ciclos en el gráfico como sus desarrollos infinitos. En algunos casos, puede usar el truco conocido como "atar el nudo" (explicado bien en algunas de las otras respuestas aquí) para incluso representar estos árboles infinitos en el espacio finito creando un ciclo en el montón; sin embargo, no podrá observar ni detectar estos ciclos desde Haskell, lo que hace que una variedad de operaciones de gráficos sea difícil o imposible.
2. Hay una variedad de álgebras gráficas disponibles en la literatura. Lo que viene a la mente primero es la colección de constructores de gráficos descritos en la sección dos de Transformaciones de gráficos bidireccionales . La propiedad habitual garantizada por estas álgebras es que cualquier gráfico puede representarse algebraicamente; sin embargo, críticamente, muchos gráficos no tendrán una representación canónica . Por lo tanto, verificar la igualdad estructuralmente no es suficiente; hacerlo correctamente se reduce a encontrar isomorfismo gráfico, conocido por ser un problema difícil.
3. Renunciar a los tipos de datos algebraicos; represente explícitamente la identidad del nodo dándoles valores únicos (por ejemplo, Ints) y refiriéndose a ellos indirectamente en lugar de algebraicamente. Esto se puede hacer significativamente más conveniente haciendo que el tipo sea abstracto y proporcionando una interfaz que haga malabarismos con la indirección para usted. Este es el enfoque adoptado por, por ejemplo, fgl y otras bibliotecas gráficas prácticas en Hackage.
4. Cree un enfoque completamente nuevo que se adapte exactamente a su caso de uso. Esto es algo muy difícil de hacer. =)

Por lo tanto, hay ventajas y desventajas para cada una de las opciones anteriores. Elige el que te parezca mejor.

Algunos otros mencionaron brevemente fgllos gráficos inductivos y los algoritmos de gráficos funcionales de Martin Erwig , pero probablemente valga la pena escribir una respuesta que realmente dé una idea de los tipos de datos detrás del enfoque de representación inductiva.

En su artículo, Erwig presenta los siguientes tipos:

type Node = Int
type Adj b = [(b, Node)]
type Context a b = (Adj b, Node, a, Adj b)
data Graph a b = Empty | Context a b & Graph a b

(La representación en fgles ligeramente diferente y hace un buen uso de las clases de tipos, pero la idea es esencialmente la misma).

Erwig está describiendo un multigrafo en el que los nodos y los bordes tienen etiquetas, y en el que todos los bordes están dirigidos. A Nodetiene una etiqueta de algún tipo a; un borde tiene una etiqueta de algún tipo b. A Contextes simplemente (1) una lista de bordes etiquetados que apuntan a un nodo en particular, (2) el nodo en cuestión, (3) la etiqueta del nodo y (4) la lista de bordes etiquetados que apuntan desde el nodo. A Graphpuede entonces concebirse inductivamente como cualquiera Empty, o como una Contextfusión (con &) en una existente Graph.

Como señala Erwig, no podemos generar libremente un Graphcon Emptyy &, como podríamos generar una lista con los constructores Consy Nil, o un Treecon Leafy Branch. Además, a diferencia de las listas (como han mencionado otros), no habrá ninguna representación canónica de a Graph. Estas son diferencias cruciales.

No obstante, lo que hace que esta representación sea tan poderosa y tan similar a las representaciones típicas de Haskell de listas y árboles, es que el Graphtipo de datos aquí se define inductivamente . El hecho de que una lista se defina inductivamente es lo que nos permite hacer una concordancia de patrones tan sucintamente en ella, procesar un solo elemento y procesar recursivamente el resto de la lista; igualmente, la representación inductiva de Erwig nos permite procesar recursivamente un gráfico uno Contexta la vez. Esta representación de un gráfico se presta a una definición simple de una forma de mapear sobre un gráfico ( gmap), así como a una forma de realizar pliegues desordenados sobre gráficos ( ufold).

Los otros comentarios en esta página son geniales. Sin embargo, la razón principal por la que escribí esta respuesta es que cuando leo frases como "los gráficos no son algebraicos", me temo que algunos lectores inevitablemente saldrán con la impresión (errónea) de que nadie encontró una buena manera de representar gráficos en Haskell de una manera que permite la coincidencia de patrones en ellos, mapearlos, doblarlos o, en general, hacer el tipo de cosas geniales y funcionales que estamos acostumbrados a hacer con listas y árboles.

Siempre me gustó el enfoque de Martin Erwig en "Gráficos inductivos y algoritmos de gráficos funcionales", que puedes leer aquí . FWIW, una vez escribí una implementación de Scala también, vea https://github.com/nicolast/scalagraphs .

Cualquier discusión sobre la representación de gráficos en Haskell necesita una mención de la biblioteca de datos de Andy Gill (aquí está el artículo ).

La representación de estilo "atar el nudo" se puede utilizar para hacer DSL muy elegantes (ver ejemplo a continuación). Sin embargo, la estructura de datos es de uso limitado. La biblioteca de Gill te permite lo mejor de ambos mundos. Puede usar un DSL "atar el nudo", pero luego convertir el gráfico basado en puntero en un gráfico basado en etiquetas para que pueda ejecutar sus algoritmos de elección en él.

Aquí hay un ejemplo simple:

-- Graph we want to represent:
--    .----> a <----.
--   /               \
--  b <------------.  \
--   \              \ / 
--    `----> c ----> d

-- Code for the graph:
a = leaf
b = node2 a c
c = node1 d
d = node2 a b
-- Yes, it's that simple!



-- If you want to convert the graph to a Node-Label format:
main = do
    g <- reifyGraph b   --can't use 'a' because not all nodes are reachable
    print g

Para ejecutar el código anterior, necesitará las siguientes definiciones:

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
import Data.Reify
import Control.Applicative
import Data.Traversable

--Pointer-based graph representation
data PtrNode = PtrNode [PtrNode]

--Label-based graph representation
data LblNode lbl = LblNode [lbl] deriving Show

--Convenience functions for our DSL
leaf      = PtrNode []
node1 a   = PtrNode [a]
node2 a b = PtrNode [a, b]


-- This looks scary but we're just telling data-reify where the pointers are
-- in our graph representation so they can be turned to labels
instance MuRef PtrNode where
    type DeRef PtrNode = LblNode
    mapDeRef f (PtrNode as) = LblNode <$> (traverse f as)

Quiero enfatizar que este es un DSL simplista, ¡pero el cielo es el límite! Diseñé un DSL muy funcional, que incluye una buena sintaxis similar a un árbol para que un nodo transmita un valor inicial a algunos de sus hijos, y muchas funciones convenientes para construir tipos de nodo específicos. Por supuesto, el tipo de datos de nodo y las definiciones mapDeRef estuvieron mucho más involucradas.

Me gusta esta implementación de un gráfico tomado de aquí

import Data.Maybe
import Data.Array

class Enum b => Graph a b | a -> b where
    vertices ::  a -> [b]
    edge :: a -> b -> b -> Maybe Double
    fromInt :: a -> Int -> b