Haskell에서 그래프를 어떻게 표현합니까?

Haskell에서 그래프를 어떻게 표현합니까?

---

대수 데이터 형식을 사용하여 haskell에서 트리 또는 목록을 나타내는 것은 쉽습니다. 그러나 그래프를 활자로 표현하는 방법은 무엇입니까? 포인터가 필요한 것 같습니다. 나는 당신이 같은 것을 가질 수 있다고 생각합니다.

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

그리고 그것은 가능할 것입니다. 그러나 약간 분리 된 느낌이 듭니다. 구조에서 서로 다른 노드 사이의 링크는 목록의 현재 이전 및 다음 요소 사이 또는 트리에서 노드의 부모와 자식 사이의 링크처럼 실제로 "느낌"을 느끼지 않습니다. 필자가 정의한대로 그래프에서 대수 조작을하는 것은 태그 시스템을 통해 도입 된 간접적 인 수준에 의해 다소 방해 받는다는 직감이 있습니다.

내가이 질문을하는 것은 주로이 의심과 불우에 대한 인식이다. Haskell에 그래프를 정의하는 더 좋고 수학적으로 우아한 방법이 있습니까? 아니면 본질적으로 어려운 / 기본적인 것을 우연히 발견 했습니까? 재귀 적 데이터 구조는 좋지만 이것은 다른 것 같습니다. 트리와 목록이 자기 참조 방식과 다른 의미에서 자기 참조 데이터 구조. 목록과 나무는 유형 수준에서 자체 참조와 같지만 그래프는 값 수준에서 자체 참조입니다.

무슨 일이야?

---

또한 순수한 언어로 사이클을 사용하여 데이터 구조를 나타내는 것이 어색합니다. 실제로 문제가되는 것은주기입니다. 유형의 멤버 (목록 및 트리 포함)를 포함 할 수있는 모든 ADT는 값을 공유 할 수 있기 때문에 실제로는 DAG (Directed Acyclic Graph)입니다. 근본적인 문제는 A가 B를 포함하고 B가 A를 포함하는 값 A와 B가 있으면 다른 값이 존재하기 전에 어느 것도 만들 수 없다는 것입니다. Haskell은 게으 르기 때문에 매듭 을 묶는 것으로 알려진 트릭을 사용 하여이 문제 를 해결할 수는 있지만 (아직 많이하지 않았기 때문에) 뇌가 아프게됩니다. 지금까지 Haskell보다 Mercury에서 실질적인 프로그래밍을 더 많이 수행했으며 Mercury는 엄격하므로 매듭 묶기가 도움이되지 않습니다.

일반적으로 제안한대로 추가 간접 지시에 의존하기 전에이 문제에 부딪쳤을 때; 종종 id에서 실제 요소로의 맵을 사용하고 요소에 다른 요소 대신 id에 대한 참조가 포함됩니다. 내가하는 일에 대해 싫어했던 주요한 점은 명백한 비효율을 제외하고는 더 취약하기 때문에 존재하지 않는 ID를 찾거나 동일한 ID를 둘 이상에 할당하려고 할 때 발생할 수있는 오류를 초래한다는 것입니다 요소. 물론 이러한 오류가 발생하지 않도록 코드를 작성하고 추상화 뒤에 숨겨서 그러한 오류 가 발생할 수 있는 유일한 위치 를 제한 할 수 있습니다. 그러나 여전히 잘못하는 것이 하나 더 있습니다.

그러나 "Haskell graph"에 대한 빠른 구글은 http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling으로 귀결되었습니다 .

---

shang의 답변에서 게으름을 사용하여 그래프를 나타내는 방법을 볼 수 있습니다. 이러한 표현의 문제점은 변경하기가 매우 어렵다는 것입니다. 매듭 묶기 트릭은 그래프를 한 번 작성하고 나중에 변경되지 않는 경우에만 유용합니다.

실제로, 나는 실제로 싶어해야 할 내 그래프 뭔가를, 내가 더 많은 보행자 표현을 사용합니다 :

• 가장자리 목록
• 인접 목록
• 각 노드에 고유 한 레이블을 지정하고 포인터 대신 레이블을 사용하고 레이블에서 노드로 유한 맵을 유지하십시오.

그래프를 자주 변경하거나 편집하려면 Huet의 지퍼를 기반으로 한 표현을 사용하는 것이 좋습니다. 이것은 제어 흐름 그래프를 위해 GHC에서 내부적으로 사용되는 표현입니다. 여기에서 읽을 수 있습니다.

• Huet의 지퍼를 기반으로 한 응용 제어 흐름 그래프

• Hoopl : 데이터 흐름 분석 및 변환을위한 모듈 식의 재사용 가능한 라이브러리

---

Ben이 언급했듯이 Haskell의 순환 데이터는 "매듭 묶기"라는 메커니즘으로 구성됩니다. 실제로, 이것은 우리가 letor 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. Instead of graphs, consider infinite trees. Represent cycles in the graph as their infinite unfoldings. In some cases, you may use the trick known as "tying the knot" (explained well in some of the other answers here) to even represent these infinite trees in finite space by creating a cycle in the heap; however, you will not be able to observe or detect these cycles from within Haskell, which makes a variety of graph operations difficult or impossible.
2. There are a variety of graph algebras available in the literature. The one that comes to mind first is the collection of graph constructors described in section two of Bidirectionalizing Graph Transformations. The usual property guaranteed by these algebras is that any graph can be represented algebraically; however, critically, many graphs will not have a canonical representation. So checking equality structurally isn't enough; doing it correctly boils down to finding graph isomorphism -- known to be something of a hard problem.
3. Give up on algebraic datatypes; explicitly represent node identity by giving them each unique values (say, Ints) and referring to them indirectly rather than algebraically. This can be made significantly more convenient by making the type abstract and providing an interface that juggles the indirection for you. This is the approach taken by, e.g., fgl and other practical graph libraries on Hackage.
4. Come up with a brand new approach that fits your use case exactly. This is a very difficult thing to do. =)

So there are pros and cons to each of the above choices. Pick the one that seems best for you.

---

I always liked Martin Erwig's approach in "Inductive Graphs and Functional Graph Algorithms", which you can read here. FWIW, I once wrote a Scala implementation as well, see https://github.com/nicolast/scalagraphs.

---

A few others have briefly mentioned fgl and Martin Erwig's Inductive Graphs and Functional Graph Algorithms, but it's probably worth writing up an answer that actually gives a sense of the data types behind the inductive representation approach.

In his paper, Erwig presents the following types:

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

(The representation in fgl is slightly different, and makes good use of typeclasses - but the idea is essentially the same.)

Erwig is describing a multigraph in which nodes and edges have labels, and in which all edges are directed. A Node has a label of some type a; an edge has a label of some type b. A Context is simply (1) a list of labeled edges pointing to a particular node, (2) the node in question, (3) the node's label, and (4) the list of labeled edges pointing from the node. A Graph can then be conceived of inductively as either Empty, or as a Context merged (with &) into an existing Graph.

As Erwig notes, we can't freely generate a Graph with Empty and &, as we might generate a list with the Cons and Nil constructors, or a Tree with Leaf and Branch. Too, unlike lists (as others have mentioned), there's not going to be any canonical representation of a Graph. These are crucial differences.

Nonetheless, what makes this representation so powerful, and so similar to the typical Haskell representations of lists and trees, is that the Graph datatype here is inductively defined. The fact that a list is inductively defined is what allows us to so succinctly pattern match on it, process a single element, and recursively process the rest of the list; equally, Erwig's inductive representation allows us to recursively process a graph one Context at a time. This representation of a graph lends itself to a simple definition of a way to map over a graph (gmap), as well as a way to perform unordered folds over graphs (ufold).

The other comments on this page are great. The main reason I wrote this answer, however, is that when I read phrases such as "graphs are not algebraic," I fear that some readers will inevitably come away with the (erroneous) impression that no one's found a nice way to represent graphs in Haskell in a way that permits pattern matching on them, mapping over them, folding them, or generally doing the sort of cool, functional stuff that we're used to doing with lists and trees.

---

Any discussion of representing graphs in Haskell needs a mention of Andy Gill's data-reify library (here is the paper).

The "tying-the-knot" style representation can be used to make very elegant DSLs (see example below). However, the data structure is of limited use. Gill's library allows you the best of both worlds. You can use a "tying the knot" DSL, but then convert the pointer-based graph into a label-based graph so you can run your algorithms of choice on it.

Here is a simple example:

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

To run the above code you will need the following definitions:

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

I want to stress that this is a simplistic DSL, but the sky's the limit! I designed a very featureful DSL, including a nice tree-like syntax for having a node broadcast an initial value to some of its children, and many convenience functions for constructing specific node types. Of course, the Node data type and mapDeRef definitions were much more involved.

---

I like this implementation of a graph taken from here

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

참고URL : https://stackoverflow.com/questions/9732084/how-do-you-represent-a-graph-in-haskell