fgl库:节点上下文未提供具有ufold的预期传出连接列表

Question

在{A,B,C,D,E}图中取以下边：

A -> B
C -> D
C -> E
D -> A

其中节点用Int:进行索引

-5959232120642455838 -> "A"
-5322791284737046018 -> "B"
6963039171755682694  -> "C"
-5226022365236209258 -> "D"
-5226022365169098782 -> "E"

fgl提供的ufold在每个节点a、B、C、D和E处提供上下文。

ufold :: Graph gr => (Context a b -> c -> c) -> c -> gr a b -> c
type Context a b = (Adj b, Node, a, Adj b)
type Adj b = [(b, Node)]

这里有一个函数，它生成一个String，显示当前访问的节点及其所有传出连接的列表。

getOutgoing :: Gr String String -> [String]
getOutgoing myGraph =
  ufold ((_,_,nodeStr,connsOut) st -> 
      (nodeStr ++ " -> " ++ show (map snd connsOut)) : st)
        [] myGraph

对于上面列出的连接，我希望这个getOutgoing返回：

A -> [-5322791284737046018]
B -> []
C -> [-5226022365236209258,-5226022365169098782]
D -> [-5959232120642455838]
E -> []

然而，它返回：

A -> [-5322791284737046018]
B -> []
D -> []
E -> []
C -> []

这是一个完整的版本：

module Main where
import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.PatriciaTree (Gr)
grEdges :: [LEdge String]
grEdges = [ (-5959232120642455838, -5322791284737046018,"AtoB")
          , (6963039171755682694,  -5226022365236209258,"CtoD")
          , (6963039171755682694,  -5226022365169098782,"CtoE")
          , (-5226022365236209258, -5959232120642455838,"DtoA") ]
grNodes :: [LNode String]
grNodes = [ (-5959232120642455838,"A")
          , (-5322791284737046018,"B")
          , (6963039171755682694,"C")
          , (-5226022365236209258,"D")
          , (-5226022365169098782,"E") ]
getOutgoing :: Gr String String -> [String]
getOutgoing myGraph =
    ufold ((_,_,nodeStr,connsOut) st ->
       (nodeStr ++ " -> " ++ show (map snd connsOut)) : st)
          [] myGraph
main :: IO ()
main = do
  putStrLn "Expected outgoing connections to nodeIDs:"
  mapM_ putStrLn [ "A -> [-5322791284737046018]"
                 , "B -> []"
                 , "C -> [-5226022365236209258,-5226022365169098782]"
                 , "D -> [-5959232120642455838]"
                 , "E -> []" ]
  putStrLn "Actual outgoing connections to nodeIDs:"
  let gr = mkGraph grNodes grEdges :: Gr String String
  mapM_ putStrLn (getOutgoing gr)

那么，为什么对于节点C和D，ufold会为它们的传出连接提供一个包含空列表的节点上下文呢？

Answer 1

上下文仅指尚未访问的节点。（想象一下，在访问时删除每个节点以及该节点的所有边。）如果你想看到额外的边，不要忽略传入的边（四元组的第一个字段）。