如何使用Haskell列出通过图形的所有路径

Question

我是Haskeller的开始.这是一个我认为需要几分钟才能构建的脚本,但这给我带来了相当大的困难.

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

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