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



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

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

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

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

169   8  

8 ответов:

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

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

однако быстрый google для "Haskell graph" привел меня к http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling, который выглядит как стоит прочитать.

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

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

  • Edge list
  • смежности список
  • дайте уникальную метку каждому узлу, используйте метку вместо указателя и сохраните конечную карту от меток до узлов

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

как упоминал Бен, циклические данные в Haskell строятся с помощью механизма, называемого "связывание узла". На практике это означает, что мы пишем взаимно рекурсивные объявления с помощью 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 для поиска соседних узлов.

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

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

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

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

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

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

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 немного отличается, и хорошо использует typeclasses - но идея по существу тот же.)

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

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

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

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

любое обсуждение представления графов в Haskell нуждается в упоминании Энди Гилла Data-reify library (здесь в статье).

представление стиля "завязывание узла" можно использовать для создания очень элегантных DSLs (см. пример ниже). Однако структура данных имеет ограниченное применение. Библиотека Гилла дает вам лучшее из обоих миров. Вы можете использовать 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, в том числе хороший древовидный синтаксис для того, чтобы узел передавал начальное значение некоторым своим дочерним элементам, а также множество удобных функций для построения конкретных типов узлов. Из конечно, тип данных узла и определения mapDeRef были гораздо более вовлечены.

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

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
    Ничего не найдено.

Добавить ответ:
Отменить.