Jak przedstawić wykres w Haskell?

W odpowiedzi Shanga można zobaczyć jak przedstawić Wykres używając lenistwa. Problem z tymi reprezentacjami polega na tym, że są one bardzo trudne do zmiany. Sztuczka z wiązaniem węzłów jest przydatna tylko wtedy, gdy masz zamiar zbudować wykres raz, a potem nigdy się nie zmienia.

W praktyce, jeśli rzeczywiście chcę zrobić coś z moim grafem, używam bardziej pieszych reprezentacji:

• Lista krawędzi
• Lista Pomocnicza
• nadaj unikalną etykietę dla każdego węzła, użyj etykiety zamiast wskaźnika i zachowaj skończoną mapę od etykiet do węzłów

Jeśli zamierzasz często zmieniać lub edytować Wykres, polecam użycie reprezentacji opartej na suwaku Hueta. Jest to reprezentacja używana wewnętrznie w GHC dla wykresów przepływu sterowania. Możesz o tym przeczytać tutaj:

• aplikacyjny Wykres kontrolno-przepływowy oparty na suwaku Hueta

• Hoopl: modułowa Biblioteka Wielokrotnego Użytku Dla Analiza i transformacja przepływu danych

Jak wspomniał Ben, cykliczne dane w Haskell są konstruowane przez mechanizm zwany "wiązaniem węzła". W praktyce oznacza to, że piszemy wzajemnie rekurencyjne deklaracje za pomocą klauzul let lub where, co działa, ponieważ części wzajemnie rekurencyjne są leniwie oceniane.

Oto przykładowy typ wykresu:

import Data.Maybe (fromJust)

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

data Graph a = Graph [Node a]

Jak widzisz, używamy rzeczywistych odniesień Node zamiast indrection. Oto jak zaimplementować funkcję, która konstruuje Wykres z listy etykiet Stowarzyszenia.

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

Pobieramy listę par (nodeLabel, [adjacentLabel]) i konstruujemy rzeczywiste wartości Node za pomocą pośredniej listy wyszukiwania (która wykonuje rzeczywiste wiązanie węzłów). Sztuczka polega na tym, że nodeLookupList (który ma typ [(a, Node a)]) jest skonstruowany za pomocą mkNode, który z kolei odnosi się z powrotem do nodeLookupList, aby znaleźć sąsiednie węzły.

To prawda, wykresy nie są algebraiczne. Aby poradzić sobie z tym problemem, masz kilka opcji:

1. zamiast Wykresów rozważ nieskończone drzewa. Reprezentują cykle na wykresie jako ich nieskończone rozwinięcie. W niektórych przypadkach możesz użyć sztuczki znanej jako "Wiązanie węzła" (wyjaśnionej dobrze w niektórych innych odpowiedziach tutaj), aby nawet reprezentować te nieskończone drzewa w skończonej przestrzeni, tworząc cykl w stercie; jednak nie będziesz w stanie zaobserwować ani wykryć tych cykli z w Haskell, co sprawia, że różne operacje grafu trudne lub niemożliwe.
W literaturze dostępne są różne algebry grafów. Pierwszy przychodzi mi na myśl zbiór konstruktorów grafów opisanych w sekcji drugiej dwukierunkowych przekształceń grafu . Typową właściwością gwarantowaną przez te algebry jest to, że każdy Graf może być reprezentowany algebraicznie; jednak krytycznie, wiele grafów nie będzie miało kanonicznej reprezentacji. Więc sprawdzanie równości strukturalnie nie wystarczy; zrobienie tego poprawnie sprowadza się do znalezienia izomorfizmu grafu-znanego z trudnego problemu.
2. Zrezygnuj z algebraicznych typów danych; jawnie reprezentuj tożsamość węzła, dając im każdą unikalną wartość (powiedzmy, Int s) i odnosząc się do nich pośrednio, a nie algebraicznie. Może to być znacznie wygodniejsze, czyniąc Typ abstrakcyjny i zapewniając interfejs, który żongluje indrection dla Ciebie. Takie jest podejście zrobione np. przez fgl i inne praktyczne biblioteki grafów na temat Hackage ' u.
3. wymyśl zupełnie nowe podejście, które dokładnie pasuje do twojego przypadku użycia. Jest to bardzo trudna rzecz do zrobienia. =)

Są więc plusy i minusy każdego z powyższych wyborów. Wybierz ten, który wydaje się najlepszy dla Ciebie.

Zawsze podobało mi się podejście Martina Erwiga w "grafach indukcyjnych i algorytmach grafów funkcyjnych" , które możecie przeczytać tutaj . FWIW, kiedyś też napisałem implementację Scali, Zobacz https://github.com/nicolast/scalagraphs .

Kilku innych krótko wspomniało fgl i grafy indukcyjne Martina Erwiga i algorytmy grafów funkcyjnych , ale prawdopodobnie warto napisać odpowiedź, która faktycznie daje poczucie typów danych stojących za podejściem reprezentacji indukcyjnej.

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

(reprezentacja w fgl jest nieco inna i dobrze wykorzystuje typeklasy - ale idea jest zasadniczo taka sama.)

Erwig opisuje Multigraf, w którym węzły i krawędzie mają etykiety i w którym wszystkie krawędzie są skierowane. A Node ma etykietę pewnego typu a; krawędź ma etykietę pewnego typu b. A Context to po prostu (1) Lista oznakowanych krawędzi wskazujących do konkretnego węzła, (2) dany węzeł, (3) Etykieta węzła i (4) Lista oznakowanych krawędzi wskazujących od węzła. A Graph może być następnie pomyślane indukcyjnie jako Empty, lub jako Context połączone (z &) w istniejące Graph.

Jak zauważa Erwig, nie możemy swobodnie generować Graph za pomocą Empty i &, ponieważ możemy wygenerować listę za pomocą konstruktorów Cons i Nil, lub Tree za pomocą Leaf i Branch. Również, w przeciwieństwie do list (jak wspominali inni), nie będzie żadnej kanonicznej reprezentacji Graph. Są to zasadnicze różnice.

Niemniej jednak, to, co sprawia, że reprezentacja ta jest tak potężna i tak podobna do typowych reprezentacji Haskella list i drzew, to że typ danych Graph jest indukcyjnie zdefiniowany. Fakt, że lista jest indukcyjnie zdefiniowana, pozwala nam tak zwięźle dopasować wzór na niej, przetwarzać pojedynczy element i rekurencyjnie przetwarzać resztę listy; podobnie, indukcyjna reprezentacja Erwiga pozwala nam rekurencyjnie przetwarzać jeden wykres Context na raz. W przeciwieństwie do innych typów grafów, Graf może być używany do tworzenia wykresów, a także do tworzenia niestandardowych zagięć na wykresach. wykresy (ufold).

Inne komentarze na tej stronie są świetne. Głównym powodem, dla którego napisałem tę odpowiedź jest jednak to, że kiedy czytam zwroty takie jak "wykresy nie są algebraiczne", obawiam się, że niektórzy czytelnicy nieuchronnie odejdą z (błędnym) wrażeniem, że nikt nie znalazł miłego sposobu na reprezentowanie Wykresów w Haskell w sposób, który pozwala na dopasowanie wzorców na nich, mapowanie na nich, składanie ich lub ogólnie robi coś fajnego, funkcjonalnego, do czego jesteśmy przyzwyczajeni listy i Drzewa.

Każda dyskusja o reprezentowaniu Wykresów w Haskell wymaga wzmianki o bibliotece data-reify Andy ' ego Gilla (tutaj jest papier ).

Reprezentacja stylu "wiązania węzła" może być używana do tworzenia bardzo eleganckich DSL(patrz przykład poniżej). Struktura danych ma jednak ograniczone zastosowanie. Biblioteka Gilla pozwala na to, co najlepsze z obu światów. Możesz użyć "wiązania węzła" DSL, ale następnie przekonwertować wykres oparty na wskaźniku na wykres oparty na etykiecie, dzięki czemu możesz uruchomić swoje algorytmy wybór.

Oto prosty przykład:

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

Do uruchomienia powyższego kodu potrzebne będą następujące definicje:

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

Podoba mi się Ta implementacja wykresu pobranego z tutaj

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