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

types graph

Question

Es bastante fácil representar un árbol o una lista en haskell usando tipos de datos algebraicos. ¿Pero cómo harías para representar typographically un gráfico? Parece que debes 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 factible. Sin embargo, se siente un poco desacoplado; Los enlaces entre diferentes nodos en la estructura en realidad no se "sienten" tan sólidos como los enlaces entre los elementos actuales previos y siguientes en una lista, o los padres e hijos de un nodo en un árbol. Tengo el presentimiento de que al hacer manipulaciones algebraicas en el gráfico, como lo definí, el nivel de indirección introducido a través del sistema de etiquetas podría obstaculizarlo.

Es principalmente esta sensación de duda y percepción de inelegancia lo que me hace formular esta pregunta. ¿Hay alguna manera mejor / más matemáticamente elegante de definir gráficos en Haskell? ¿O me he tropezado 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 que las listas y los árboles son autorreferenciales en el nivel de tipo, pero los gráficos son autorreferenciales en el nivel de valor.

Entonces, ¿qué está pasando realmente?

Answer 1

Algunos otros han mencionado brevemente los here fgl y 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 fgl es 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 se dirigen todos los bordes. Un Node tiene una etiqueta de algún tipo a ; un borde tiene una etiqueta de algún tipo b . Un Context es simplemente (1) una lista de bordes etiquetados que apuntan a un nodo particular, (2) el nodo en cuestión, (3) la etiqueta del nodo y (4) la lista de bordes etiquetados que apuntan desde el nodo. Un Graph puede concebirse inductivamente como Empty o como un Context combinado (con & ) en un Graph existente.

Como señala Erwig, no podemos generar libremente un Graph con Empty y & , ya que podríamos generar una lista con los constructores Cons y Nil , o un Tree con Leaf y Branch . Además, a diferencia de las listas (como han mencionado otros), no habrá ninguna representación canónica de un 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 tipo de datos Graph aquí se define inductivamente . El hecho de que una lista se defina inductivamente es lo que nos permite concordar de manera tan sucinta con el patrón, procesar un solo elemento y procesar recursivamente el resto de la lista; igualmente, la representación inductiva de Erwig nos permite procesar de forma recursiva un gráfico un Context a 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. La razón principal por la que escribí esta respuesta, sin embargo, 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 ha encontrado una buena manera de representar gráficos en Haskell de una manera que permita 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.

Answer 2

Como mencionó Ben, los datos cíclicos en Haskell están construidos por un mecanismo llamado "atar el nudo". En la práctica, significa que escribimos declaraciones mutuamente recursivas usando las cláusulas let o where , que funciona porque las partes mutuamente recursivas son evaluadas 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 referencias de Node reales en lugar de indirectas. Aquí se explica cómo implementar una función que construye 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]) y construimos los valores de Node reales a través de una lista de búsqueda intermedia (que hace el nudo-atado real). El truco es que nodeLookupList (que tiene el tipo [(a, Node a)] ) se construye utilizando mkNode , que a su vez hace referencia a nodeLookupList para buscar los nodos adyacentes.

Answer 3

Cualquier discusión sobre la representación de gráficos en Haskell necesita una mención de la biblioteca de datos-reificación 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 "atando el nudo", pero luego convierta 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 sintaxis similar a un árbol para que un nodo difunda un valor inicial para algunos de sus elementos secundarios, y muchas funciones de conveniencia para construir tipos de nodos específicos. Por supuesto, el tipo de datos Node y las definiciones mapDeRef fueron mucho más complicados.

Answer 4

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 del nudo es útil solo si vas a construir un gráfico una vez, y después nunca cambia.

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

• Lista de bordes
• Lista de adyacencia
• Asigne una etiqueta única a cada nodo, use la etiqueta en lugar de un puntero y mantenga un mapa finito desde las etiquetas hasta los nodos

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

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

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

Answer 5

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

1. En lugar de gráficos, considere árboles infinitos. Representa ciclos en el gráfico como sus despliegues infinitos. En algunos casos, puede usar el truco conocido como "atar el nudo" (explicado bien en algunas de las otras respuestas aquí) para representar incluso estos árboles infinitos en espacio finito creando un ciclo en el montón; sin embargo, no podrá observar ni detectar estos ciclos desde dentro de Haskell, lo que hace que una variedad de operaciones gráficas sea difícil o imposible.
2. Hay una variedad de álgebras gráficas disponibles en la literatura. Lo primero que viene a la mente es la colección de constructores de gráficos que se describe 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 . Entonces, verificar la igualdad estructuralmente no es suficiente; hacerlo correctamente se reduce a encontrar el isomorfismo gráfico, conocido por ser un problema difícil.
3. Renunciar a los tipos de datos algebraicos; representar explícitamente la identidad del nodo al darles valores únicos (por ejemplo, Int s) y referirse a ellos de forma indirecta en lugar de algebraicamente. Esto se puede hacer mucho más conveniente al hacer que el tipo sea abstracto y proporcionar una interfaz que combine la indirección por usted. Este es el enfoque adoptado por, por ejemplo, fgl y otras bibliotecas de gráficos prácticos en Hackage.
4. Propón un nuevo enfoque que se adapte exactamente a tu caso de uso. Esto es algo muy difícil de hacer. =)

Entonces, existen ventajas y desventajas para cada una de las opciones anteriores. Elija el que le parezca mejor.

Answer 6

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

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

Answer 7

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

Answer 8

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 los valores A y B, con A que contiene B y B que contienen A, ninguno puede crearse antes de que exista el otro. Debido a que Haskell es flojo, puedes usar un truco conocido como Tying the Knot para evitar esto, pero eso me daña el cerebro (porque todavía no he hecho mucho). He hecho más de mi programación sustancial en Mercurio que Haskell hasta el momento, y Mercurio es estricto así que atar los nudos no ayuda.

Por lo general, cuando me encuentro con esto antes, acabo de recurrir a la indirección adicional, como estás sugiriendo; a menudo usando un mapa de los identificadores a los elementos reales, y teniendo elementos que contienen referencias a los identificadores en lugar de a otros elementos. Lo principal que no me gustó al hacer eso (aparte de la obvia ineficiencia) es que se sentía más frágil, presentando los posibles errores al buscar una identificación que no existe o tratando de asignar la misma identificación a más de un elemento. Puede escribir código para que estos errores no se produzcan, por supuesto, e incluso ocultarlo detrás de las abstracciones para que los únicos lugares donde puedan ocurrir dichos errores estén acotados. Pero aún es una cosa más equivocarse.

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