Comment représenter un graphe en Haskell?

Shang de réponse, vous pouvez voir comment représenter un graphe à l'aide de la paresse. Le problème avec ces représentations, c'est qu'ils sont très difficiles à changer. Le nouage astuce est utile seulement si vous avez l'intention de construire un graphe une fois, et par la suite, il ne change jamais.

Dans la pratique, dois-je réellement envie de ne quelque chose avec mon graphique, j'utilise le plus de piétons représentations:

• Bord liste
• Liste d'adjacence
• Donner un label unique pour chaque nœud, utilisez l'étiquette au lieu d'un pointeur, et de garder une durée de carte à partir d'étiquettes de nœuds

Si vous allez être en train de changer ou de modifier le graphique fréquemment, je recommande d'utiliser une représentation basée sur Huet de la fermeture à glissière. C'est la représentation utilisée en interne dans GHC pour le contrôle de flux de graphiques. Vous pouvez lire à ce sujet ici:

• Un Applicatif de Contrôle Graphique de Flux basé sur Huet de la fermeture à Glissière

• Hoopl: Modulaire, Bibliothèque Réutilisable pour des Flux de données, l'Analyse et la Transformation

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

1. Au lieu de graphiques, de considérer l'infini des arbres. Représenter les cycles dans le graphe que leur infinie unfoldings. Dans certains cas, vous pouvez utiliser l'astuce connue comme "d'attacher le noeud" (bien expliqué dans les autres réponses ici) à même de représenter ces infini des arbres dans l'espace limité par la création d'un cycle dans le tas; toutefois, vous ne serez pas en mesure d'observer ou de détecter ces cycles de l'intérieur Haskell, qui en fait une variété de graphique des opérations difficiles ou impossibles.
2. Il existe une variété de graphique algèbres disponibles dans la littérature. Celui qui vient en premier à l'esprit est la collection de graphique constructeurs décrit dans la section deux de Bidirectionalizing Graphique Transformations. L'habitude de propriété garanti par ces algèbres, c'est que tout graphe peut être représenté algébriquement; toutefois, de façon critique, de nombreux graphiques n'aura pas de canonique représentation. Donc la vérification de l'égalité structurellement n'est pas suffisant; le faire correctement se résume à trouver graphique isomorphisme -- connu pour être quelque chose d'un problème difficile.
3. Renoncer à des types de données algébriques; représentent de façon explicite nœud d'identité en leur donnant à chacun les valeurs uniques (par exemple, Ints) et, se référant à eux indirectement plutôt que algébriquement. Cela peut être fait beaucoup plus pratique en rendant le type abstrait et une interface qui jongle avec les indirection pour vous. C'est l'approche adoptée par la, par exemple, fgl et d'autres pratiques graphique bibliothèques sur le Hackage.
4. Venir avec une toute nouvelle approche qui s'adapte à votre cas d'utilisation, exactement. C'est une chose très difficile à faire. =)

Il y a donc des avantages et des inconvénients à chacun des choix ci-dessus. Choisissez celle qui vous semble la meilleure pour vous.

Quelques autres ont brièvement mentionné fgl et Martin Erwig de Inductive Graphes et Algorithmes sur les graphes Fonctionnels, mais c'est probablement la peine de rédiger une réponse qui effectivement donne une idée des types de données derrière le inductive de la représentation de l'approche.

Dans son papier, 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 fgl est légèrement différente, et fait bon usage de typeclasses - mais l'idée est essentiellement la même.)

Erwig décrit un multigraph dans lequel les nœuds et les arêtes ont des étiquettes, et dont toutes les arêtes sont orientées. Un Node a une étiquette de certains type de a; une arête a une étiquette de certains type de b. Un Context est tout simplement (1) une liste de étiquetés bords de pointage à un nœud particulier, (2) le nœud en question, (3) le nœud de l'étiquette, et (4) la liste de étiquetés bords de pointage de le nœud. Un Graph peut alors être conçu de façon inductive comme Empty, ou comme un Context fusionné (avec &) dans un Graph.

Comme Erwig notes, nous ne pouvons pas librement générer un Graph avec Empty et &, comme on pourrait générer une liste avec les Cons et Nil les constructeurs, ou un Tree avec Leaf et Branch. Aussi, contrairement aux listes (comme d'autres l'ont mentionné), il n'y a pas de représentation canonique d'une Graph. Ce sont des différences cruciales.

Néanmoins, ce qui fait de cette représentation si puissant et si semblable à la moyenne de Haskell représentations de listes et les arbres, c'est que le Graph type de données est ici inductif défini. Le fait qu'une liste est défini inductivement est ce qui nous permet donc de façon succincte, en correspondance du modèle sur elle, processus d'un seul élément, et de manière récursive processus le reste de la liste; de même, Erwig inductive de la représentation nous permet de nous traitez de manière récursive un graphique un Context à la fois. Cette représentation d'un graphe se prête à une simple définition d'un moyen de la carte sur un graphique (gmap), ainsi que d'un moyen pour effectuer non ordonnée plis sur les graphes (ufold).

Les autres commentaires sur cette page sont grands. La principale raison que j'ai écrit cette réponse, cependant, est que quand je lis des phrases telles que "les graphiques ne sont pas algébriques," j'ai peur que certains lecteurs vont inévitablement venir de loin avec la (fausse) impression que personne n'est trouvé une belle manière de représenter des graphes en Haskell d'une façon qui permet le filtrage sur eux, de la cartographie sur eux, les plier et, plus généralement, faire le tri de cool fonctionnel des choses que nous sommes habitués avec les listes et les arbres.

J'aime cette mise en œuvre d'un graphe prises de 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