节点和边元组的反向列表 (Haskell)

Question

我有一个节点和边的列表，表示为元组，其中第一个元素是一个节点，第二个元素是它有边的所有节点的列表。我正在尝试像这样反转列表：

ghci> snuN [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
ghci> [("a",["c"]),("b",["a"]),("c",["b"]),("d",["c","e"]),("e",[])]

到目前为止，我已经编写了这段代码：

snuH :: Eq t => [(t,[t])] -> [(t,[t])]
snuH [] = []
snuH ps@((x, xs):rest) =
    if (length xs <= 1) && not (x `isInSublist` ps)
        then [(y,[x])| y <- xs] ++ snuH rest ++ [(x, [])]
    else [(y,[x])| y <- xs] ++ snuH rest

isInSublist :: Eq t => t -> [(t,[t])] -> Bool
isInSublist _ [] = False
isInSublist x ((y, ys):rest) = (x `elem` ys) || isInSublist x rest

combine :: Eq t => [(t,[t])] -> [(t,[t])]
combine ps@((x, xs):(y, ys):rest) = if x == y then (x, xs++ys):rest else (x, xs):combine((y, ys):rest)

snuN :: Eq t => [(t, [t])] -> [(t, [t])]
snuN ls = combine $ snuH ls

第一个函数给我这个输出：

ghci> snuH [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
ghci> [("b",["a"]),("c",["b"]),("a",["c"]),("d",["c"]),("d",["e"]),("e",[]),("b",[])]

这不是我想要的结果，因为它创建了两个具有相同第一个元素 (("d",["c"]),("d",["e"])) 的元组，并且它有额外的 ("b",[]) 作为元素，而它不应该.我写了 combine 辅助函数来解决这个问题，它给了我这个输出：

ghci> snuN [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
ghci> [("b",["a"]),("c",["b"]),("a",["c"]),("d",["c","e"]),("e",[]),("b",[])]

这解决了第一个元素相同的两个元组的问题，但我仍然有额外的 ("b",[])，我不知道如何解决，我假设我的 [= 有问题19=] 但我看不出问题出在哪里。

你能告诉我我做错了什么吗？我不明白为什么我会得到额外的 ("b",[])。感谢所有帮助！

Answer 1

我认为以下列表理解可以满足您的需求：

type Graph node = [(node, [node])]

converse :: Eq node => Graph node -> Graph node
converse g = [(v, [e | (e, es) <- g, v `elem` es]) | (v, _) <- g]

但是，如果您尝试一下，您将得到：

> converse [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
[("a",["c"]),("b",["a"]),("c",["b"]),("e",[])]

与您提供的示例相比，输出中缺少 "d" 的条目。那是因为输入没有提到明确的条目 ("d", []).

为了弥补这一点，我们可以在从图中检索完整节点列表时加入更多逻辑，同时考虑“隐含”节点：

nodes :: Eq node => Graph node -> [node]
nodes g = nub $ concat [v : es | (v, es) <- g]

注意：这需要从 Data.List.

导入 nub

那么，我们可以这样写：

converse' :: Eq node => Graph node -> Graph node
converse' g = [(v, [e | (e, es) <- g, v `elem` es]) | v <- nodes g]

事实上，我们屈服了：

> converse' [("a",["b"]),("b",["c"]),("c",["a","d"]),("e",["d"])]
[("a",["c"]),("b",["a"]),("c",["b"]),("d",["c","e"]),("e",[])]

Answer 2

你有 [(a, [a])]，它将节点映射到它们有边的节点。 “逆转”这一点的一种方法是首先将其转换为所有边的列表。我们实际上可以在这里概括一下类型，以区分节点。

allEdges :: [(a, [b])] -> [(a, b)]
allEdges g = [(a, b) | (a, bs) <- g, b <- bs]

现在只需收集具有边缘的节点到每个特定节点：

import Data.Map.Strict (Map)
import qualified Data.Map.Strict as M

gather :: Ord b => [(a,b)] -> Map b [a]
gather edges = M.fromListWith (++) [(b, [a]) | (a, b) <- edges]

现在我们可以使用 M.assocs 将该地图转换为列表！

上面的代码将省略没有边的节点到。我们可以通过一些额外的工作来修补它。

reverseGraph :: Ord a => [(a, [a])] -> [(a, [a])]
reverseGraph = M.assocs . M.fromListWith (++) . gunk
  where
    gunk g = [q  | (a, bs) <- g, q <- (a, []) : [(b, [a]) | b <- bs]]

这里的想法是，当我们看到 (a, bs) 时，我们为 b 中的每个 b 插入空边集 (a, []) 以及非空边集 (b, [a] 19=].

节点和边元组的反向列表 (Haskell)

Reverse list of tuples of nodes and edges (Haskell)

haskell

tuples

list