haskell - 如何确保图中的边正确

Question

我试图在 Haskell 中为图形创建数据类型，如下所示:

type Vertex a = a
type Edge a = (Vertex a, Vertex a)
data Graph a = Combine [Vertex a] [Edge a]

这是一种适合我想做的事情的表示，但我意识到可能存在不在顶点列表中的顶点的边。

因此，我的问题是是否有可能确保每条边仅包含顶点列表中的顶点？

我已经想了很多，但到目前为止我得到的最好的想法是一些函数，它可以创建一个新图，并将边列表中所有缺失的顶点添加到顶点列表中。像这样的东西:

fix_graph :: Graph a -> Graph a
fix_graph (Combine v e) = Combine (removeDuplicates (v ++ [x | (x,_) <- e] ++ [y | (_,y) <- e])) e

removeDuplicates :: [t] -> [t]
...

因为这个想法并没有真正满足我(也因为我没有花时间很好地实现它)，我想知道是否有可能有一个数据构造函数来添加不在其中的边的顶点顶点列表还立即。

我已经通读了答案 here ，但我不太喜欢那里使用的邻接表示。我知道我很烦人，但我只是想知道是否没有其他可能性来解决这个问题。

如果有人可以帮助我找到解决方案或摆脱我的幻想，那将会很有帮助......

提前致谢

Answer 1

所以有几个不同的选择:

喜结良缘

在 Haskell 中对图进行编码的方法有很多。最简单的方法是使用称为“打结”的过程在树数据结构中创建循环。例如，对该图进行编码:

                  .--.
  A -- B -- C -- D -./
  |    |    |    |
  E -- F    G -- H
  |              |
  +--------------+

您可以简单地编写一个节点作为其名称和子节点列表:

data Node = Node String [Node]
instance Eq Node where
    Node a _ == Node b _ = a == b

my_graph = [a, b, c, d, e, f, g, h] where
    a = Node "A" [b, e]
    b = Node "B" [a, c, f]
    c = Node "C" [b, d, g]
    d = Node "D" [c, d, h]
    e = Node "E" [a, f, h]
    f = Node "F" [b, e]
    g = Node "G" [c, h]
    h = Node "H" [d, e, g]

这有很多便利:您现在可以像任何其他 Haskell 数据结构一样使用尾递归函数遍历该数据结构。要终止循环，在递归时，您将当前项附加到 path 变量上，并且递归逻辑应该说的第一件事是，| nodeelempath = ... 来处理您想要的循环。

另一方面是，你的小一致性问题已经升级为真正棘手的一致性问题。例如考虑这两者之间的区别:

-- A has one child, which is itself; B has one child, which is A.
let a = Node "A" [a]; b = Node "B" [a] in [a, b]

-- this looks almost the same but if you descend far enough on B you find an
-- impostor node with the wrong children.
let a = Node "A" [a]
    impostor = Node "A" [b]
    b = Node "B" [Node "A" [Node "A" [impostor]]] 
in [a, b]

所以这很糟糕，我对此唯一真正的答案是，“通过转换为以下之一来标准化......”。

无论如何，上面的技巧也被称为相互递归和letrec，基本上意味着在where或 let 子句中，您放在那里的所有定义都可以“互相看到”。这不是懒惰的表现，而是懒惰的表现。您也可以使用严格语言来制作上述数据结构 - 但是以这种方式理解相互递归定义的功能性严格语言的语言设计可能有点困难。 (使用非函数式语言，您只需根据需要创建指针。)

明确的数字命理学

现在考虑一下如何获取我们上面得到的图表，并将其转换为您的表示形式。最简单的方法是通过一个包含 Array 的中间人步骤:

import From.Above.Code (Node)
import Data.Array

type Graph = Array [Int]

graph :: [Node] -> Maybe Graph
graph nodes = fmap (array (1, length nodes)) . sequence $ map format nodes where
    indices = zip nodes [1..]
    pair x y = (x, y)
    format node@(Node _ children) = do -- in the Maybe monad
        index <- lookup node indices
        index_list <- sequence $ map (flip lookup indices) children
        return (index, index_list)

现在，一致性问题少了很多，现在都可以通过编程方式缓解。但是，如果您想以编程方式使用状态单子(monad)创建这样的图，并且希望暂时使数据结构处于不一致状态，直到读取正确的节点，那么这些一致性问题就可以发挥作用。唯一的缺点是，当您将图形写入文件时，它看起来有点难以理解，因为数字不如字符串友好:

 array (1, 8) [
     (1, [2, 5]),
     (2, [1, 3, 6]),
     (3, [2, 4, 7]),
     (4, [3, 4, 8]),
     (5, [1, 6, 8]),
     (6, [2, 5]),
     (7, [3, 8]),
     (8, [4, 5, 7])]

您可以使用 Map String [String] 来解决此问题，以权衡访问时间变为 O(log n)。无论如何，您应该了解这种表示形式:当您执行您建议的“完整性检查”时，您将需要转换为 IntMap [Int] 并返回。

一旦获得这些，您就可以使用支持Array Int Node来创建递归[Node]，如上所述:

nodesFromArray arr = nodes where
    makeNode index children = Node (show index) [backingArray ! c | c <- children]
    backingArray = array (bounds arr) [(i, makeNode i c) | (i, c) <- assocs arr]
    nodes = map makeNode arr

边列表

一旦您获得了上述列表(Map.toList 或 Array.assocs)，边列表就变得非常容易制作:

edges_from_array = concatMap . uncurry (fmap . pair) . assocs

另一面稍微复杂一点，可以直接完成您想要做的事情:

import Data.Map (Map)
import Data.Set (Set)
import qualified Data.Map as Map
import qualified Data.Set as Set

makeGraphMap vertices edges = add edges (Map.fromList $ blankGraph vertices) where
     blankGraph verts = zip verts (repeat Set.empty)
     setInsert x Nothing = Just $ Set.singleton x
     setInsert x (Just set) = Just $ Set.insert x set
     add [] graphMap = fmap Set.toList graphMap
     add ((a, b) : es) graphMap = Map.alter (setInsert b) a verts

也就是说，我们用一个映射来遍历边列表，该映射将键映射到它们的子集；我们将其初始化为映射到空集的顶点列表(以便我们可以在图中断开连接的单个节点)，然后通过将值插入到键处的集合来遍历边缘，如果我们不这样做则创建该集合查看 key 。