首页 文章

如何确保图中的正确边

提问于
浏览 次
4

我试图在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，但我还有其他任何可能解决这个问题的方法 .

如果有人可以帮我解决问题或摆脱我的幻想，那将会有所帮助......

提前致谢

haskell graph types

1 回答

  • 2

    所以有几个不同的选择：

    结结

    有很多方法可以在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 变量上，并且递归逻辑应该说的第一件事是， | node elem path = ... 来处理您想要的循环 .

    另一方面，你的次要一致性问题已经引发了一些棘手的一致性问题 . 考虑一下这两者之间的区别：

    -- 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 子句中，你放在那里的所有定义都可以"see each other" . 它不是懒惰的 property ;您也可以使用严格的语言来创建上述数据结构 - 但是这种方式理解相互递归定义的功能严格语言的语言设计可能有点困难 . （使用非功能性语言，您只需根据需要创建指针 . ）

    明确的数字命理学

    现在想想你是如何得到的，并将其转换为你的代表 . 最简单的方法是通过一个包含 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)

    现在，这一致性问题要少得多，现在可以通过编程方式缓解这些问题 . 但是，如果要以编程方式使用State 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] 并在你做出你提议的"completeness checks"时返回 .

    一旦你得到这些，事实证明你可以使用支持 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

    也就是说，我们使用 Map 来遍历边缘列表，该 Map 将键映射到他们的子集;我们将其初始化为映射到空集的顶点列表（以便我们可以在图中使用断开的单个节点），然后通过将值插入到键的集合中来遍历边缘，如果我们不这样做则创建该集合看到钥匙 .

    回复于

相关问题