图中可达节点

Question

我想要检查一个节点可以到达哪些节点。

因此，我想要提供一个图形和一个节点，并返回一个列表，其中包含可以从该节点到达图形的所有节点。（我知道有Data.Graph，但是我想从头开始理解它，并故意不使用它。）

为了构建图形，我获得了以下数据。

data Node = Node String [Node]

字符串只是节点名称的表示。

这是图形的表示方式。

node1 = Node "node1" [node2,node3]
node2 = Node "node2" [node3]
node3 = Node "node3" [node4,node5]
node4 = Node "node4" [node1,node2]
node5 = Node "node5" [node4]

我还获得了以下节点的(直接)到达：

canReachNext (Node x y) = y 

我的基本想法是这样的：

listForReachables:: Node n => n -> [n]
listForReachables x
    | contains[x] (canReachNext x) == False = listForReachables (head(canReachNext (x)))
    | contains [x] (canReachNext x)== True = [x]
    | otherwise = []

如果我运行，这会导致无限循环。

listForReachables node1

我明白为什么会进入循环了。因为在这个例子中，头部将总是有另一个列表。

我的问题和困惑之处在于，我习惯面向对象编程，在这种情况下，感觉需要一个列表来记住我已经检查过哪些节点，以及我还需要检查哪些节点。

- Sorun

---

这不是在Haskell中解决该问题的好数据表示。 - Joseph Sible-Reinstate Monica

@JosephSible-ReinstateMonica 为什么不呢？显然，邻接图之所以受欢迎是因为它更容易构建，但如果您可以使用这种表示构建给定的图，则完全可以在其上运行图算法。 - amalloy

@amalloy 我没说这是不可能的，只是不好。我不喜欢的主要原因是它无法“使非法状态不可表示”，因为你可以有一个具有相同标签的两个节点的图形。对我来说，这种数据结构似乎是为具有引用相等性的语言而设计的，而 Haskell 不具备这种特性。 - Joseph Sible-Reinstate Monica

是的，确实有reallyUnsafePtrEquality#这个函数，但请不要使用它。 - Joseph Sible-Reinstate Monica

Answer 1

在Haskell中，一个具有所需类型的函数通常会调用另一个带有许多参数的函数。您可以使用这些参数来捕获中间状态。

在这种情况下，我添加了一个已经访问过的节点列表。第一个参数是要探索的节点列表。当程序遇到已经通过的节点时，它会将其丢弃并继续使用第一个参数中的其他节点。

您的退出条件无法发生，因为Bool只有True和False值。这些值不再需要进行比较。

我有一个问题，即标准类Show和Eq应用于node1时会挂起，因此我为自己制作了不完整的contains和name。

如果您遇到循环问题，请确保检查show node1和contains是否正常。或者，制作一个非循环测试图表。

node6 = Node "node6" [node7]
node7 = Node "node7" []

代码：

data Node = Node String [Node]

node1 = Node "node1" [node2,node3]
node2 = Node "node2" [node3]
node3 = Node "node3" [node4,node5]
node4 = Node "node4" [node1,node2]
node5 = Node "node5" [node4]

canReachNext :: Node -> [Node]
canReachNext (Node x y) = y

name :: Node -> String
name (Node x y) = x

contains :: [Node] -> [Node] -> Bool
contains (x:xs) ys = any ((\(Node a b) -> \(Node c d) ->  a == c) x) ys

listForReachables :: Node -> [Node]
listForReachables x = listForReachables' (x:[]) []

listForReachables' :: [Node] -> [Node] -> [Node]
listForReachables' (x:xs) ys
    | contains [x] ys  = listForReachables' xs ys
    | otherwise = listForReachables' (xs ++ canReachNext x) (x:ys)
listForReachables' [] ys = ys

测试：

map name $ listForReachables node1

输出：

["node5","node4","node3","node2","node1"]

注意1：有一个惯例是将辅助函数命名为"go"，具体可参考这里。

listForReachables :: Node -> [Node]
listForReachables x = go (x:[]) [] where
 go (x:xs) ys
    | contains [x] ys  = go xs ys
    | otherwise = go (xs ++ canReachNext x) (x:ys)
 go [] ys = ys

- David Lukas

Answer 2

感觉需要一个列表来记住我已经检查过的节点和我还需要检查的节点。

我同意。那我们就用一个列表吧！

listForReachables :: Node -> [String] -> ([String], [Node])
listForReachables node@(Node src tgts) visited
    | src `elem` visited = (visited, [])
    | otherwise = loopOver tgts (src:visited)
    where
    loopOver [] visited = (visited, [node])
    loopOver (tgt:tgts) visited = let
        (visited', reachables) = listForReachables tgt visited'
        (visited'', reachables') = loopOver tgts visited'
        in (visited'', reachables ++ reachables')

实际上，有经验的Haskeller会注意到这个模式：

(visited', reachables) = listForReachables tgt visited'
(visited'', reachables') = loopOver tgts visited'

同时要认识到，这正是 State [String] 单子中 (>>=) 的实现方式。所以他们可能会用以下方式改变实现：

listForReachables :: Node -> State [String] [Node]
listForReachables node@(Node src tgts) = do
    done <- gets (src `elem`)
    if done then pure [] else do
        modify (src:)
        reachables <- mapM listForReachables tgts
        pure (node : concat reachables)

相当紧凑！让我们试试看：

> name (Node nm _) = nm
> map name (evalState (listForReachables node1) [])
["node1","node2","node3","node4","node5"]

- Daniel Wagner