Как вы представляете график в Haskell?

Question

Достаточно просто представить дерево или список в haskell, используя алгебраические типы данных. Но как бы вы описали типографское представление графика? Кажется, вам нужны указатели. Я предполагаю, что у вас может быть что-то вроде

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

И это было бы осуществимо. Тем не менее, он чувствует себя немного отделенным; Связи между различными узлами в структуре на самом деле не "кажутся" такими же прочными, как связи между текущими предыдущими и следующими элементами в списке или родителями и потомками узла в дереве. У меня есть предчувствие, что алгебраические манипуляции с графиком, как я определил, будут несколько затруднены уровнем косвенности, введенным через систему тегов.

Именно это чувство сомнения и восприятия неумелости заставляет меня задать этот вопрос. Есть ли лучший / более математически элегантный способ определения графов в Haskell? Или я наткнулся на что-то сложное / фундаментальное? Рекурсивные структуры данных приятны, но, похоже, это нечто другое. Самостоятельная ссылочная структура данных в том смысле, в каком деревья и списки являются самостоятельными ссылочными. Это похоже на то, что списки и деревья являются самоссылочными на уровне типа, но графы самоссылаются на уровне значений.

Так что же на самом деле происходит?

Answer 1

В ответе Шанга вы можете увидеть, как изобразить график с помощью лени. Проблема с этими представлениями заключается в том, что их очень трудно изменить. Уловка завязывания узлов полезна, только если вы собираетесь построить график один раз, а потом он никогда не изменится.

На практике, если я действительно хочу сделать что-то с моим графиком, я использую более пешеходные представления:

• Пограничный список
• Список смежности
• Дайте уникальную метку каждому узлу, используйте метку вместо указателя и сохраняйте конечную карту от меток до узлов

Если вы собираетесь часто менять или редактировать график, я рекомендую использовать представление, основанное на молнии Huet. Это представление, используемое внутри GHC для графов потоков управления. Вы можете прочитать об этом здесь:

• Аппликативный график управления потоком на основе молнии Хуета

• Hoopl: модульная многоразовая библиотека для анализа и преобразования потока данных

Answer 2

Мне также неловко пытаться представлять структуры данных с циклами на чистом языке.Это циклы, которые действительно проблема;Поскольку значения могут быть общими, любой ADT, который может содержать член типа (включая списки и деревья), действительно является DAG (направленным ациклическим графом).Основная проблема заключается в том, что если у вас есть значения A и B, где A содержит B и B содержит A, то ни один из них не может быть создан до того, как существует другой.Поскольку Haskell ленив, вы можете использовать уловку, известную как Tying the Knot , чтобы обойти это, но это причиняет боль моему мозгу (потому что я еще не сделал большую часть этого).До сих пор я занимался более серьезным программированием на Mercury, чем на Haskell, и Mercury строг, поэтому завязывание узлов не помогает.

Обычно, когда я сталкиваюсь с этим, прежде чем просто прибегнуть кдополнительная косвенность, как вы предлагаете;часто используя карту от идентификаторов до фактических элементов, и имея элементы, содержащие ссылки на идентификаторы, а не на другие элементы.Главное, что мне не понравилось в этом (кроме очевидной неэффективности), это то, что он чувствовал себя более хрупким, представляя возможные ошибки при поиске несуществующего идентификатора или пытаясь назначить один и тот же идентификатор более чем одномуэлемент.Конечно, вы можете написать код, чтобы эти ошибки не возникали, и даже скрыть его за абстракциями, чтобы единственные места, где такие ошибки могли , были ограничены.Но это еще одна вещь, чтобы ошибиться.

Тем не менее, быстрый Google для «графика Хаскелла» привел меня к http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling,, который выглядит как стоящее чтение.

Answer 3

Как упоминал Бен, циклические данные в Хаскеле строятся с помощью механизма, называемого «связывание узла». На практике это означает, что мы пишем взаимно рекурсивные объявления, используя предложения let или where, что работает потому, что взаимно рекурсивные части лениво оцениваются.

Вот пример типа графика:

import Data.Maybe (fromJust)

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

data Graph a = Graph [Node a]

Как видите, мы используем фактические Node ссылки вместо косвенных. Вот как можно реализовать функцию, которая создает граф из списка ассоциаций меток.

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

Мы берем список пар (nodeLabel, [adjacentLabel]) и создаем фактические значения Node через промежуточный список поиска (который выполняет фактическую привязку узлов). Хитрость заключается в том, что nodeLookupList (который имеет тип [(a, Node a)]) создается с использованием mkNode, который, в свою очередь, обращается к nodeLookupList для поиска соседних узлов.

Answer 4

Это правда, графики не алгебраические. Для решения этой проблемы у вас есть несколько вариантов:

1. Вместо графиков рассмотрим бесконечные деревья. Представлять циклы в графе как их бесконечные разворачивания. В некоторых случаях вы можете использовать уловку, известную как «связывание узла» (хорошо объясненную в некоторых других ответах здесь), чтобы даже представить эти бесконечные деревья в конечном пространстве, создав цикл в куче; однако вы не сможете наблюдать или обнаруживать эти циклы в Haskell, что затрудняет или делает невозможным множество операций с графами.
2. В литературе имеется множество графовых алгебр. Первым на ум приходит коллекция конструкторов графов, описанная во втором разделе Двунаправленные преобразования графов . Обычное свойство, гарантированное этими алгебрами, состоит в том, что любой граф может быть представлен алгебраически; однако, что очень важно, многие графы не будут иметь каноническое представление. Поэтому структурной проверки равенства недостаточно; правильное выполнение этой задачи сводится к нахождению изоморфизма графов, который, как известно, является сложной задачей.
3. Откажись от алгебраических типов данных; явно представлять идентичность узла, присваивая им уникальные значения (скажем, Int s) и ссылаясь на них косвенно, а не алгебраически. Это можно сделать значительно более удобным, сделав тип абстрактным и предоставив интерфейс, который будет манипулировать вами. Этот подход используется, например, fgl и другими практическими библиотеками графов в Hackage.
4. Придумайте новый подход, который точно соответствует вашему варианту использования. Это очень сложно сделать. =)

Таким образом, у каждого из вышеперечисленных вариантов есть свои плюсы и минусы. Выберите тот, который кажется вам наиболее подходящим.

Answer 5

Несколько других кратко упомянули fgl и алгоритмы индуктивных графов и функциональных графов Мартина Эрвига , но, вероятно, стоит написать ответ, который фактически дает представление о типах данных, лежащих в основе подхода индуктивного представления,

В своей статье Эрвиг представляет следующие типы:

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

(Представление в fgl немного отличается и хорошо использует классы типов - но идея по сути та же самая.)

Эрвиг описывает мультиграф, в котором узлы и ребра имеют метки, и в котором все ребра направлены.A Node имеет метку какого-то типа a;ребро имеет метку какого-то типа b.Context - это просто (1) список помеченных ребер, указывающих на конкретный узел, (2) рассматриваемый узел, (3) метка узла и (4) список помеченных реберуказывая от на узел.Graph может быть затем индуктивно воспринят либо как Empty, либо как Context, объединенный (с &) в существующий Graph.

Как отмечает Эрвиг, мы не можемсвободно генерируйте Graph с Empty и &, как мы могли бы создать список с конструкторами Cons и Nil, или Tree с Leaf и Branch.Кроме того, в отличие от списков (как уже упоминали другие), не будет никакого канонического представления Graph.Это принципиальные различия.

Тем не менее, то, что делает это представление настолько мощным и похожим на типичные представления списков и деревьев на Хаскеле, состоит в том, что тип данных Graph здесь индуктивно определен ,Тот факт, что список является индуктивно определенным, позволяет нам так кратко сопоставлять шаблоны, обрабатывать отдельный элемент и рекурсивно обрабатывать остальную часть списка;в равной степени индуктивное представление Эрвига позволяет нам рекурсивно обрабатывать граф по одному Context за раз.Это представление графа поддается простому определению способа отображения на графе (gmap), а также способа выполнения неупорядоченных сгибов над графами (ufold).

Другие комментарии на этой странице великолепны.Однако основная причина, по которой я написал этот ответ, заключается в том, что когда я читаю фразы типа «графы не алгебраические», я боюсь, что у некоторых читателей неизбежно возникнет (ошибочное) впечатление, что никто не нашел хорошего способа представления графиков.в Haskell таким образом, который позволяет сопоставлять с ними шаблоны, отображать их, сворачивать их или вообще делать что-то классное, функциональное, что мы привыкли делать со списками и деревьями.

Answer 6

Мне всегда нравился подход Мартина Эрвига в «Индуктивных графах и алгоритмах функциональных графов», который вы можете прочитать здесь .FWIW, я однажды написал также реализацию Scala, см. https://github.com/nicolast/scalagraphs.

Answer 7

Любое обсуждение представления графов в Haskell требует упоминания библиотеки данных * Энди Гилла (здесь статья ).

"Связывание-knot "представление стиля может использоваться для создания очень элегантных DSL (см. пример ниже).Однако структура данных имеет ограниченное использование.Библиотека Джилла позволяет вам лучшее из обоих миров.Вы можете использовать DSL «связывая узел», но затем преобразовать граф на основе указателей в граф на основе меток, чтобы на нем можно было использовать выбранные вами алгоритмы.

Вот простой пример:

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

Чтобы запустить приведенный выше код, вам понадобятся следующие определения:

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

Я хочу подчеркнуть, что это упрощенный DSL, но небо - предел! Я разработал очень интересный DSL, включая приятный древовидный синтаксис для того, чтобы узел передавал начальное значение некоторым его дочерним элементам, и множество вспомогательных функций для создания определенных типов узлов.Разумеется, определения типа данных Node и mapDeRef были гораздо более сложными.

Answer 8

Мне нравится эта реализация графика, взятого из здесь

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