2

我很难弄清楚如何在 Haskell 中读入（以及如何表示）图表。

文件的输入看起来像

NODES 3
EDGE 1 2
EDGE 1 3
EDGE 2 3

我已经弄清楚如何使用以下方法从文件中获取各个输入行：

loadFile :: String -> IO [[String]]
loadFile filename = do 
                contents <- readFile filename
                return $ map words $ lines contents

这给出了如下输出：

loadFile "input.txt"
[["NODES","3"],["EDGE","1","2"],["EDGE","1","3"],["EDGE","2","3"]]

不过，我真正需要弄清楚的是如何将此图形数据表示为图形。我正在考虑将其设置为边缘列表：

type Edge = (Int,Int)
type Graph = [Edge]

但后来我不确定如何开始实现我需要的功能，例如 addNode、addEdge、getNodes、getEdges。

任何帮助或指出我正确的方向都会很棒！注意：我不能为此使用任何已经开发的图形模块。

因此，对于 tl;dr 版本：

  1. 我是否以最好的方式阅读数据？
  2. 我应该如何在 haskell 中表示这些数据？
  3. 如果我使用上面概述的数据结构，我将如何实现其中一个功能。
4

1 回答 1

7

这里有很多有趣的问题。让我攻击他们。

  1. 对于面向行的语言，您正在阅读数据。稍后您将看到Data.ByteString并Data.Text替换String以提高效率。您还将看到Parsec用于解析。不过，那些可以等待。及时重温他们。

  2. 您的图形表示很好。邻接表是一种常见且有用的表示。

  3. 现在，你拥有的真正诀窍就在这里。让我们看一下addNode和addEdge。每个都是用纯函数式语言生成的具有一定挑战性的函数，因为他们想修改图形……但我们没有状态。

修改无状态最重要的方法是变异。因此，您正在寻找的功能是

addNode :: Node -> Graph -> Graph

其中返回Graph与输入相同，Graph除了多了一条边​​。您应该立即注意到这里有问题——邻接表假定没有孤立节点。我们不能只向图中添加一个节点。

有两种解决方案。第一，我们可以将节点“链接”到图中（实际上是addEdge伪装的），或者第二，我们可以扩展图表示以包含孤立节点。让我们做（2）。

data Graph = Graph [Edge] [Int] -- orphans

现在让我们实现添加边。假设您可以有重复的边，将边添加到邻接列表很容易，只需附加它

addEdge0 :: Edge -> Graph -> Graph
addEdge0 e (Graph adj orph) = Graph (e:adj) orph

但这还不够好——我们希望我们的孤儿列表只包含真正的孤儿节点。我们会过滤它。

addEdge :: Edge -> Graph -> Graph
addEdge (n1,n2) (Graph adj orph) = 
  Graph ((n1,n2):adj) (filter (/=n1) . filter (/=n2) $ orph)

getEdges很简单，因为我们已经存储了边列表

getEdges :: Graph -> [Edge]
getEdges (Graph edges _) = edges

getNodes只需要将邻接列表中的所有节点附加到孤立列表中。我们可以使用Data.List.nub仅获取唯一节点。

getNodes :: Graph -> [Int]
getNotes (Graph adj orph) = nub (orph ++ adjNodes adj) where
  adjNodes [] = []
  adjNodes ((n1,n2):rest) = n1 : n2 : adjNodes rest

希望这些能给你一些关于如何用函数式语言思考的指示。您将不得不深入研究它们以了解它们是如何工作的，但我在这里介绍了许多有趣的概念。

这里的下一步可能包括尝试使用Statemonad 重新捕获命令式状态修改并将这些Graph修改函数链接在一起。

于 2013-04-16T04:02:34.897 回答