Comment représentez-vous un graphe en Haskell ?

Question

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 vous y prendriez-vous à la typographie représentant un graphique? Il semble que vous avez besoin d'avoir des pointeurs. Je devine que vous pourriez avoir quelque chose comme

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

Et qui serait réalisable. Cependant, il se sent un peu découplé; les liens entre Les différents nœuds de la structure n'est pas vraiment "sentir" aussi solide que les liens entre le précédent et suivant des éléments dans une liste, ou les parents et les enfants d'un nœud dans un arbre. J'ai un pressentiment que faire des manipulations algébriques sur le graphe que j'ai défini, il serait quelque peu entravée par le niveau d'indirection introduit par le système de tag.

C'est surtout ce sentiment de doute et de la perception de inelegance qui me fait poser cette question. Est-il mieux/plus mathématiquement élégante manière de définir les graphiques en Haskell? Ou ai-je tombé sur quelque chose d'intrinsèquement dur/fondamental? Récursive structures de données sont doux, mais cela semble être quelque chose d'autre. Un auto-référentielle de la structure des données dans un sens différent de la façon dont les arbres et les listes sont auto référentielle. C'est comme les listes et les arbres sont autoréférentiels au niveau du type, mais les graphiques sont auto-référentielle à la valeur de niveau.

Alors, quel est-il vraiment?

Answer 1

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 faire 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

Answer 2

Je trouve aussi qu'il est très difficile d'essayer de représenter des structures de données avec des cycles dans une langue pure. C'est les cycles qui sont vraiment le problème, car les valeurs peuvent être partagés en toute ADT qui peut contenir un membre du type (y compris les listes et les arbres) est vraiment un DAG (Graphe Dirigé Acyclique). Le problème de fond est que si vous avez les valeurs de A et B, avec Un contenant B et B contenant de l'Un, puis l'un ne peut être créée avant que l'autre existe. Parce que Haskell est paresseux, vous pouvez utiliser une astuce connue que d'Attacher le Noeud pour contourner ce problème, mais ce qui rend mon cerveau mal (parce que je n'ai pas fait grand chose encore). J'ai fait plus de mon substantielle de la programmation dans le Mercure de Haskell jusqu'à présent, et le Mercure est de rigueur afin de nouage ne l'aide pas.

Généralement quand j'ai couru dans cette avant, j'ai juste eu recours à d'autres indirection, comme vous êtes suggérant; souvent par l'utilisation d'une carte à partir des identifiants pour les éléments réels, et d'avoir des éléments de contenir des références à l'id plutôt qu'à d'autres éléments. La principale chose que je n'aime pas cela (à part l'évidente inefficacité), c'est qu'il se sentait plus fragiles, présentant les erreurs possibles de la recherche d'un id qui n'existe pas ou qui tentent d'assigner le même id à plus d'un élément. Vous pouvez écrire du code pour que ces erreurs ne se produisent pas, bien sûr, et même de le cacher derrière des abstractions, de sorte que les seuls endroits où de telles erreurs pourraient se produire sont bornées. Mais c'est encore une chose de plus à se tromper.

Cependant, un rapide google pour "Haskell graphique" m'a conduit à http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling, qui ressemble à une la peine d'être lu.

Answer 3

Ben mentionné, les données cyclique en Haskell est construit par un mécanisme appelé "d'attacher le noeud". Dans la pratique, cela signifie que nous écrivons mutuellement récursives déclarations à l'aide de let ou where clauses, qui fonctionne parce que l'mutuellement récursives pièces sont paresseusement évalué.

Voici un exemple du 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 réel Node références au lieu d'indirection. Voici comment implémenter une fonction qui construit le graphe à partir d'une liste de label associations.

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 dans une liste d' (nodeLabel, [adjacentLabel]) des paires et de construire le réel Node valeurs par le biais d'un intermédiaire pour la recherche de la liste (qui ne le réel de nœuds). Le truc, c'est qu' nodeLookupList (qui est le type [(a, Node a)]) est construit à l'aide d' mkNode, ce qui, à son tour, renvoie à l' nodeLookupList de trouver les nœuds adjacents.

Answer 4

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 canonique de la 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.

Answer 5

J’ai toujours aimé approche de Martin Erwig dans « Inductive graphiques et fonctionnelles Graph Algorithms », que vous pouvez lire ici. FWIW, j’ai écrit une fois une implémentation de Scala, voir https://github.com/nicolast/scalagraphs.