Comment représentez-vous un graphique dans Haskell?

Il est assez facile de représenter un arbre ou une liste dans haskell en utilisant des types de données algébriques. Mais comment procéder pour représenter typographiquement un graphique? Il semble que vous ayez besoin de pointeurs. Je suppose que tu pourrais avoir quelque chose comme

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

Et ce serait réalisable. Cependant, cela semble un peu découplé; Les liens entre les différents nœuds de la structure ne "se sentent" pas vraiment aussi solides que les liens entre les éléments précédents et suivants actuels d'une liste, ou les parents et enfants d'un nœud dans un arbre. J'ai l'impression que faire des manipulations algébriques sur le graphique tel que je l'ai défini serait quelque peu gêné par le niveau d'indirection introduit par le système de balises.

C'est principalement ce sentiment de doute et cette perception d'inélégance qui m'amènent à poser cette question. Existe-t-il un moyen meilleur / plus élégant mathématiquement de définir des graphes dans Haskell? Ou suis-je tombé sur quelque chose de fondamentalement dur / fondamental? Les structures de données récursives sont douces, mais cela semble être autre chose. Une structure de données auto-référentielle dans un sens différent de la façon dont les arbres et les listes sont auto-référentiels. C'est comme si les listes et les arbres sont auto-référentiels au niveau du type, mais les graphiques sont auto-référentiels au niveau des valeurs.

Alors qu'est-ce qui se passe vraiment?

Je trouve également gênant d'essayer de représenter des structures de données avec des cycles dans un langage pur. Ce sont les cycles qui sont vraiment le problème; car les valeurs peuvent être partagées, tout ADT qui peut contenir un membre du type (y compris les listes et les arbres) est en réalité un DAG (Directed Acyclic Graph). Le problème fondamental est que si vous avez les valeurs A et B, avec A contenant B et B contenant A, aucune ne peut être créée avant que l'autre n'existe. Parce que Haskell est paresseux, vous pouvez utiliser une astuce connue sous le nom de Tying the Knot pour contourner cela, mais cela me fait mal au cerveau (car je n'en ai pas encore fait beaucoup). J'ai fait plus de ma programmation substantielle dans Mercury que Haskell jusqu'à présent, et Mercury est strict, donc nouer des nœuds n'aide pas.

Habituellement, lorsque j'ai rencontré cela avant, je viens de recourir à une indirection supplémentaire, comme vous le suggérez; souvent en utilisant une carte des identifiants aux éléments réels, et en faisant en sorte que les éléments contiennent des références aux identifiants plutôt qu'à d'autres éléments. La principale chose que je n'aimais pas faire cela (mis à part l'inefficacité évidente) est que cela semblait plus fragile, introduisant les erreurs possibles de recherche d'un identifiant qui n'existe pas ou d'essayer d'attribuer le même identifiant à plus d'un. élément. Vous pouvez écrire du code pour que ces erreurs ne se produisent pas, bien sûr, et même le cacher derrière des abstractions afin que les seuls endroits où de telles erreurs pourraient se produire soient délimités. Mais c'est encore une chose de se tromper.

Cependant, un rapide google pour "Haskell graph" m'a conduit à http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling , qui semble être une lecture intéressante.

Dans la réponse de shang, vous pouvez voir comment représenter un graphique en utilisant la paresse. Le problème avec ces représentations est qu'elles sont très difficiles à changer. L'astuce de nouage n'est utile que si vous allez créer un graphique une fois, et par la suite, il ne change jamais.

En pratique, si je veux réellement faire quelque chose avec mon graphique, j'utilise les représentations les plus piétonnes:

• Liste des bords
• Liste adjacente
• Donnez une étiquette unique à chaque nœud, utilisez l'étiquette au lieu d'un pointeur et conservez une carte finie des étiquettes aux nœuds

Si vous comptez changer ou éditer fréquemment le graphique, je vous recommande d'utiliser une représentation basée sur la fermeture éclair de Huet. Il s'agit de la représentation utilisée en interne dans GHC pour les graphiques de flux de contrôle. Vous pouvez lire à ce sujet ici:

• Un graphique de contrôle-flux applicatif basé sur la fermeture à glissière de Huet

• Hoopl: une bibliothèque modulaire et réutilisable pour l'analyse et la transformation des flux de données

Comme Ben l'a mentionné, les données cycliques dans Haskell sont construites par un mécanisme appelé "nouer le nœud". En pratique, cela signifie que nous écrivons des déclarations mutuellement récursives à l'aide de clauses letou where, ce qui fonctionne car les parties mutuellement récursives sont évaluées paresseusement.

Voici un exemple de type de graphique:

import Data.Maybe (fromJust)

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

data Graph a = Graph [Node a]

Comme vous pouvez le voir, nous utilisons des Noderéférences réelles au lieu de l'indirection. Voici comment implémenter une fonction qui construit le graphique à partir d'une liste d'associations d'étiquettes.

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

Nous prenons une liste de (nodeLabel, [adjacentLabel])paires et construisons les Nodevaleurs réelles via une liste de recherche intermédiaire (qui fait le nœud réel). L'astuce est que nodeLookupList(qui a le type [(a, Node a)]) est construit en utilisant mkNode, qui à son tour se réfère au nodeLookupListpour trouver les nœuds adjacents.

C'est vrai, les graphiques ne sont pas algébriques. Pour résoudre ce problème, vous avez plusieurs options:

1. Au lieu de graphiques, considérez des arbres infinis. Représentez les cycles dans le graphique comme leurs dépliages infinis. Dans certains cas, vous pouvez utiliser l'astuce connue sous le nom de "nouer le nœud" (bien expliqué dans certaines des autres réponses ici) pour même représenter ces arbres infinis dans un espace fini en créant un cycle dans le tas; cependant, vous ne serez pas en mesure d'observer ou de détecter ces cycles depuis Haskell, ce qui rend une variété d'opérations graphiques difficiles, voire impossibles.
2. Il existe une variété d'algèbres de graphes disponibles dans la littérature. Celui qui vient à l'esprit en premier est la collection de constructeurs de graphes décrits dans la section deux de Transformations de graphes bidirectionnelles . La propriété habituelle garantie par ces algèbres est que tout graphe peut être représenté algébriquement; cependant, de manière critique, de nombreux graphiques n'auront pas de représentation canonique . Donc, vérifier l'égalité structurellement ne suffit pas; le faire correctement revient à trouver un isomorphisme de graphe - connu pour être un problème difficile.
3. Abandonnez les types de données algébriques; représentent explicitement l'identité des nœuds en leur attribuant des valeurs uniques (disons, Ints) et en y faisant référence indirectement plutôt que algébriquement. Cela peut être rendu beaucoup plus pratique en rendant le type abstrait et en fournissant une interface qui jongle avec l'indirection pour vous. C'est l'approche adoptée, par exemple, par fgl et d'autres bibliothèques de graphes pratiques sur Hackage.
4. Proposez une toute nouvelle approche qui correspond exactement à votre cas d'utilisation. C'est une chose très difficile à faire. =)

Il y a donc des avantages et des inconvénients à chacun des choix ci-dessus. Choisissez celui qui vous convient le mieux.

Quelques autres ont brièvement mentionné fglles graphes inductifs et les algorithmes de graphes fonctionnels de Martin Erwig , mais il vaut probablement la peine d'écrire une réponse qui donne réellement une idée des types de données derrière l'approche de représentation inductive.

Dans son article, Erwig présente les types suivants:

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 représentation dans fglest légèrement différente et fait bon usage des classes de types - mais l'idée est essentiellement la même.)

Erwig décrit un multigraphe dans lequel les nœuds et les arêtes ont des étiquettes, et dans lequel toutes les arêtes sont dirigées. A Nodea une étiquette d'un certain type a; un bord a une étiquette d'un certain type b. A Contextest simplement (1) une liste d'arêtes étiquetées pointant vers un nœud particulier, (2) le nœud en question, (3) l'étiquette du nœud, et (4) la liste des arêtes étiquetées pointant à partir du nœud. A Graphpeut alors être conçu de manière inductive comme l'un Emptyou l' autre , ou comme Contextfusionné (avec &) dans un existant Graph.

Comme le note Erwig, nous ne pouvons pas générer librement un Graphavec Emptyet &, comme nous pourrions générer une liste avec les constructeurs Conset Nil, ou Treeavec Leafet Branch. De plus, contrairement aux listes (comme d'autres l'ont mentionné), il n'y aura pas de représentation canonique d'un Graph. Ce sont des différences cruciales.

Néanmoins, ce qui rend cette représentation si puissante et si similaire aux représentations Haskell typiques des listes et des arbres, c'est que le Graphtype de données est ici défini de manière inductive . Le fait qu'une liste soit définie de manière inductive est ce qui nous permet de faire une correspondance de modèle si succincte dessus, de traiter un seul élément et de traiter récursivement le reste de la liste; De même, la représentation inductive d'Erwig nous permet de traiter de manière récursive un graphe un Contextpar un. Cette représentation d'un graphe se prête à une définition simple d'un moyen de mapper sur un graphe ( gmap), ainsi qu'à un moyen d'effectuer des plis non ordonnés sur des graphes ( ufold).

Les autres commentaires sur cette page sont excellents. La principale raison pour laquelle j'ai écrit cette réponse, cependant, est que lorsque je lis des phrases telles que "les graphiques ne sont pas algébriques", je crains que certains lecteurs en reviennent inévitablement avec l'impression (erronée) que personne n'a trouvé une bonne façon de représenter les graphiques en Haskell d'une manière qui permet la correspondance de motifs sur eux, les mapper sur eux, les plier, ou généralement faire le genre de choses cool et fonctionnelles que nous avons l'habitude de faire avec des listes et des arbres.

J'ai toujours aimé l'approche de Martin Erwig dans «Graphiques inductifs et algorithmes de graphes fonctionnels», que vous pouvez lire ici . FWIW, j'ai également écrit une implémentation Scala, voir https://github.com/nicolast/scalagraphs .

Toute discussion sur la représentation des graphiques dans Haskell nécessite une mention de la bibliothèque data-reify d'Andy Gill (voici l'article ).

La représentation de style «nouer le nœud» peut être utilisée pour créer des DSL très élégants (voir l'exemple ci-dessous). Cependant, la structure des données est d'une utilité limitée. La bibliothèque de Gill vous offre le meilleur des deux mondes. Vous pouvez utiliser une DSL «nouant le nœud», mais ensuite convertir le graphique basé sur des pointeurs en un graphique basé sur des étiquettes afin que vous puissiez y exécuter les algorithmes de votre choix.

Voici un exemple 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

Pour exécuter le code ci-dessus, vous aurez besoin des définitions suivantes:

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

Je tiens à souligner qu'il s'agit d'un DSL simpliste, mais le ciel est la limite! J'ai conçu un DSL très fonctionnel, comprenant une belle syntaxe arborescente pour qu'un nœud diffuse une valeur initiale à certains de ses enfants, et de nombreuses fonctions pratiques pour construire des types de nœuds spécifiques. Bien sûr, le type de données Node et les définitions de mapDeRef étaient beaucoup plus impliqués.

J'aime cette implémentation d'un graphe tiré d' ici

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