Comment représentez-vous un graphique dans Haskell?

125

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?

TheIronKnuckle
la source
12
Vous pourriez être intéressé par l'article de Martin Erwig sur les algorithmes de graphes fonctionnels: web.engr.oregonstate.edu/~erwig/papers/abstracts.html#JFP01 . Le fglpackage s'est développé à partir de cela.
John L
La page des 99 problèmes Haskell montre quelques exemples de graphiques utilisés dans un contexte de résolution de problèmes. Il a également une courte introduction sur différentes représentations.
dopamane

Réponses:

47

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.

Ben
la source
62

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:

Norman Ramsey
la source
2
Un autre problème avec le fait de faire le nœud est qu'il est très facile de le détacher accidentellement et de perdre beaucoup d'espace.
hugomg
Il semble que quelque chose ne va pas avec le site Web de Tuft (du moins pour le moment), et aucun de ces liens ne fonctionne actuellement. J'ai réussi à trouver des miroirs alternatifs pour ceux-ci: Un graphique de flux de contrôle 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
gntskn
37

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.

shang
la source
20
Vous devez également mentionner que cette structure de données n'est pas en mesure de décrire les graphiques. Il ne décrit que leurs déroulements. (dépliages infinis dans un espace fini, mais quand même ...)
Rotsor
1
Sensationnel. Je n'ai pas eu le temps d'examiner toutes les réponses en détail, mais je dirai qu'exploiter une évaluation paresseuse comme celle-ci donne l'impression de patiner sur de la glace mince. Serait-il facile de se glisser dans une récursion infinie? Encore des trucs géniaux, et se sent bien mieux que le type de données que j'ai proposé dans la question.
TheIronKnuckle
@TheIronKnuckle pas trop de différence avec les listes infinies que Haskellers utilise tout le temps :)
Justin L.
37

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.

Daniel Wagner
la source
"vous ne pourrez pas observer ou détecter ces cycles depuis Haskell" n'est pas tout à fait vrai - il existe une bibliothèque qui vous permet de faire exactement cela! Voyez ma réponse.
Artelius
les graphes sont algébriques maintenant! hackage.haskell.org/package/algebraic-graphs
Josh.F
16

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.

liminalisht
la source
14

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 .

Nicolas Trangez
la source
3
Pour développer cela très grossièrement, il vous donne un type de graphique abstrait sur lequel vous pouvez faire correspondre un modèle. Le compromis nécessaire pour que cela fonctionne est que la manière exacte dont un graphe peut être décomposé n'est pas unique, de sorte que le résultat d'une correspondance de modèle peut être spécifique à l'implémentation. Ce n'est pas un gros problème dans la pratique. Si vous êtes curieux d'en savoir plus à ce sujet, j'ai écrit un article de blog d' introduction qui pourrait être mal lu.
Tikhon Jelvis
Je vais prendre une liberté et publier la belle discussion de Tikhon sur ce begriffs.com/posts/2015-09-04-pure-functional-graphs.html .
Martin Capodici
5

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.

Artelius
la source
2

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
pyCthon
la source