您将如何在Haskell中表示图形(与旅行商问题相关的图形)

Question

在haskell中表示一棵树很容易:

data Tree a = Node Tree a Tree | Leaf a

但这是因为它不需要命令式样式"指针"的概念,因为每个Node/Leaf都有一个,而且只有一个父节点.我想我可以将它表示为Maybe Ints 列表的列表... Nothing为那些没有路径的节点创建一个表,对于那些Just n那些...但这看起来真的很丑陋而且不实用.

Answer 1

你可以使用类似的类型

type Graph a = [Node a]
data Node a = Node a [Node a]

节点列表是该节点的传出(或您喜欢的传入)边缘.由于您可以构建循环数据结构,因此可以表示任意(多)图形.这种图形结构的缺点是一旦你构建它就无法修改它.要遍历每个节点可能需要一个唯一的名称(可以包含在其中a),以便您可以跟踪您访问过的节点.

Answer 2

免责声明:以下是"打结"技术的无意义练习.如果你想真正使用你的图表,Fgl是要走的路.但是,如果您想知道如何在功能上表示循环数据结构,请继续阅读.

在Haskell中表示图表非常容易!

-- a directed graph

data Vertex a b = Vertex { vdata :: a, edges :: [Edge a b] }
data Edge   a b = Edge   { edata :: b, src :: Vertex a b, dst :: Vertex a b }

-- My graph, with vertices labeled with strings, and edges unlabeled

type Myvertex = Vertex String ()
type Myedge   = Edge   String ()

-- A couple of helpers for brevity

e :: Myvertex -> Myvertex -> Myedge
e = Edge ()

v :: String -> [Myedge] -> Myvertex
v = Vertex

-- This is a full 5-graph

mygraph5 = map vv [ "one", "two", "three", "four", "five" ] where
    vv s = let vk = v s (zipWith e (repeat vk) mygraph5) in vk

这是一个循环的,有限的,递归的,纯函数的数据结构.不是一个非常有效或美丽的,但看,马,没有指针!这是一个练习:包括顶点中的传入边

data Vertex a b = Vertex {vdata::a, outedges::[Edge a b], inedges::[Edge a b]}

构建一个完整的图形很容易,每个边缘有两个(无法区分)副本:

mygraph5 = map vv [ "one", "two", "three", "four", "five" ] where
    vv s = 
       let vks = repeat vk
           vk = v s (zipWith e vks mygraph5) 
                    (zipWith e mygraph5 vks)
       in vk

但尝试建立一个每个都有一个副本!(想象一下,涉及一些昂贵的计算e v1 v2).