Haskell中的拓扑排序

Question

我有一个数据类型Graph,如下所示:

data Graph w = Graph {vertices :: [(Char, w)],
                      edges :: [(Char, Char, w)]} deriving Show

这表示有向无环图.顶点有一个字符标识符(添加的第一个顶点为'a',第二个顶点为'b',依此类推)和权重.边是两个顶点标识符和一个权重.

我正在考虑使顶点更复杂,也许它们应该包含所有邻居的列表？

到目前为止,拓扑排序看起来像这样:

topological_ordering :: Graph w -> [Char]
topological_ordering (Graph v w) =
    let startingNodes = getStartNodes (Graph v w)
        emptyList = []
        sorted = sortAlgorithm startingNodes emptyList (Graph v w)
    in sorted

sortAlgorithm :: [Char] -> [Char] -> Graph w -> [Char]
sortAlgorithm startingNodes sorted (Graph v w) =
    | [] _ _ = []
    | (x:startingNodes) sorted (Graph v w) =
      let sorted = sorted ++ [x]
          neigbours = findNeighbours (Graph v w) x

getStartNodes :: Graph w -> [Char]
getStartNodes (Graph v w) =
    let set1 = Set.fromList $ firstNodes w
        set2 = Set.fromList $ secondNodes w
        startNodes = Set.toList $ Set.difference set1 set2
    in  startNodes

firstNodes :: [(Char, Char, w)] -> [Char]
firstNodes [] = []
firstNodes (x:xs) = selectFirst x:firstNodes xs

secondNodes :: [(Char, Char, w)] -> [Char]
secondNodes [] = []
secondNodes (x:xs) = selectSecond x:secondNodes xs

从那里我有点失落.我真的不知道如何完成sortAlgorithm,因为我希望它是递归的(或者使用foldl/foldr？).应该以另一种方式实现Graph的数据类型还是应该继续？

几周前我刚刚开始使用haskell,但仍然感觉功能编程有点丢失.

谢谢

Answer 1

您可能想看看它在Data.Graph中的优雅程度.以下是算法的概述:

topSort      :: Graph -> [Vertex]
topSort       = reverse . postOrd

postOrd      :: Graph -> [Vertex]
postOrd       = postorderF . dff

postorder :: Tree a -> [a]
postorder (Node a ts) = postorderF ts ++ [a]

postorderF   :: Forest a -> [a]
postorderF ts = concat (map postorder ts)

-- | A spanning forest of the graph, obtained from a depth-first search of
-- the graph starting from each vertex in an unspecified order.
dff          :: Graph -> Forest Vertex
dff g         = dfs g (vertices g)

-- | A spanning forest of the part of the graph reachable from the listed
-- vertices, obtained from a depth-first search of the graph starting at
-- each of the listed vertices in order.
dfs          :: Graph -> [Vertex] -> Forest Vertex

也就是说,图的拓扑类型是图的生成森林的后序遍历(反之).

以下是如何使用它的示例:

  import qualified Data.Graph as G

  {-
     5 --> 7
     |     |
     v     V
     1 --> 4 --> 8
  -}

  (myGraph,vertexToNode,keyToVertex) = G.graphFromEdges [
      ("node4",4,[8]),     -- the first component can be of any type
      ("node8",8,[]),
      ("node7",7,[4]),
      ("node5",5,[1,7]),
      ("node1",1,[4])
   ]

  sorted = map vertexToNode $ G.topSort myGraph
  -- [("node5",5,[1,7]),("node7",7,[4]),("node1",1,[4]),("node4",4,[8]),("node8",8,[])]