对于练习我需要反转图形(反转所有边缘),但我没有得到任何结果。所以我需要一些帮助。
我知道你可能不想为我解决这个问题,所以这不是我要求的。我只需要一些建议......
所以要达到它:
data Graph a = G
{ nodes :: [a]
, successors :: a -> [a] }
reverseGraph :: Eq a => Graph a -> Graph a
图表必须包含以下参数:节点列表和定义后继者的函数。此函数的类型为:a -> [a]
例如:
graph1 :: Graph Int
graph1 = G [1..6] $ \case 1 -> [2,3]
2 -> []
3 -> [1,4,6]
4 -> [1]
5 -> [3,5]
6 -> [2,4,5]
反转图表将是:
reverseGraph graph1 ~>
2 -> [1,6]
3 -> [1,5]
1 -> [3,4]
4 -> [3,6]
6 -> [3]
5 -> [5,6]
我得到了我需要在输入图中检查后继节点中的每个节点,并为每个输入节点添加到输出节点的新后继列表。
但我只是不知道如何在Haskell中做到这一点。
任何帮助表示赞赏!
以下是我可以尝试类似事物的人的解决方案:
reverseGraph :: Eq a => Graph a -> Graph a
reverseGraph (G nodes sucs) = (G nodes sucs') where
sucs' a = getVert a nodes sucs
--Makes a list of all occurrences of v in the succeccor list.
getVert :: Eq a => a -> [a] -> (a-> [a]) -> [a]
getVert v [] succs = []
getVert v (n:ns) succs = if v `elem` succs n then [n]++getVert v ns succs else getVert v ns succs
这是一个提示。让我们考虑G vertices edges
的反面。这将是G vertices' edges'
的形式。
很明显,vertices' = vertices
。
怎么样edges'
?好吧,对于任何价值v
,edges' v
必须返回
w
中所有vertices
的列表,使得edge w
包含v
作为元素”您可以使用列表推导将上述英语描述翻译成Haskell代码。您可以使用x `elem` list
来检查x
是否是list
的元素。