haskell - 如何使用 Haskell 列出图形中的所有路径

Question

我是一名 Haskell 初学者。这是一个我认为需要几分钟才能构建的脚本，但它给我带来了相当大的困难。

假设我们有一个由节点和边组成的图。数据结构是节点到节点对的列表，如下所示:

[(1,6),(1,8),(6,9),(6,10),(6,13),(8,13)]

我想构建一个函数，它遍历图表并显示从起始节点到底部所有可到达节点的所有可能路径。

因此，该函数的几个理想执行可能如下所示:

> allPaths 1 [(1,6),(1,8),(6,9),(6,10),(6,13),(8,13)]
[[1,6,9],[1,6,10],[1,6,13],[1,8,13]]
> allPaths 8 [(1,6),(1,8),(6,9),(6,10),(6,13),(8,13)]
[[8,13]]

这是我的初步尝试，刚刚开始构建路径列表:

allPaths start graph = [start : [snd edge] | edge <- graph, fst edge == start]

> allPaths 8 [(1,6),(1,8),(6,9),(6,10),(6,13),(8,13)]
[[1,6],[1,8]]

问题是我不知道如何使这个解决方案使用递归来完成路径。这是未通过类型检查的几个蹩脚尝试之一:

allPaths start graph = [start : (snd edge : allPaths (snd edge) graph) | edge <- graph, fst edge == start]

    Occurs check: cannot construct the infinite type: a ~ [a]
    Expected type: [a]
      Actual type: [[a]]
    Relevant bindings include
      edge :: (a, a) (bound at allpaths.hs:5:72)
      graph :: [(a, a)] (bound at allpaths.hs:5:16)
      start :: a (bound at allpaths.hs:5:10)
      allPaths :: a -> [(a, a)] -> [[a]]
        (bound at allpaths.hs:5:1)
    In the second argument of `(:)', namely `allPaths (snd edge) graph'
    In the second argument of `(:)', namely
      `(snd edge : allPaths (snd edge) graph)'
Failed, modules loaded: none.

这是什么意思？我的列表嵌套是否太深了。

有人有解决方案或更好的方法吗？

Answer 1

如果您切换到图表的不同表示形式，这会变得容易得多。我在这里使用的结构不一定是最好或最有效的，并且我没有对循环关系进行任何检查，但它比边列表更容易使用。

首先，一些导入

import qualified Data.Map as M

我们的结构是一个Int节点标签与其子节点之间的关系，所以

type Node = Int
type Children = [Node]
type Graph = M.Map Node Children

现在我们可以写下我们的测试图:

testGraph :: Graph
testGraph = M.fromList
    [ (1,  [6, 8])
    , (6,  [9, 10, 13])
    , (8,  [13])
    , (9,  [])
    , (10, [])
    , (13, [])
    ]

为了使这变得更加简单，您可以编写一个函数来非常轻松地从边列表转到此结构:

fromEdges :: [(Node, Node)] -> Graph
fromEdges = M.fromListWith (++) . map (fmap (:[]))

(这不会以相同的顺序添加它们，您可以使用 Data.Set.Set 缓解此问题。)

现在你只需拥有

testGraph = fromEdges [(1,6),(1,8),(6,9),(6,10),(6,13),(8,13)]

为了实现函数 allPaths::Node -> Graph -> [[Node]] 事情现在非常简单。我们只需要考虑三种情况:

1. 在图中查找节点时，该节点不存在。应返回空列表。
2. 该节点存在于图中，但没有子节点。应返回路径[[node]]。
3. 该节点存在于图中并且有子节点。应返回以当前节点为前缀的所有子节点的所有路径。

所以

allPaths startingNode graph =
    case M.lookup startingNode graph of
        Nothing -> []                -- Case 1
        Just [] -> [[startingNode]]  -- Case 2
        Just kids ->                 -- Case 3
            map (startingNode:) $    -- All paths prepended with current node
                concatMap (`allPaths` graph) kids  -- All kids paths