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？）。我应该用另一种方式实现图形的数据类型，还是应该继续使用这个？

我几周前刚刚开始学习 Haskell，对于函数式编程仍然感到有点迷茫。

谢谢。

- hboy

---

由于您的图形始终是无环的，我想知道是否可以使用ADT来表示它，而不是顶点和边的列表？ - user3974391

@user2894391 有向无环图并不意味着树形结构。你仍然需要打结，这在计划进行序列化/反序列化等操作时可能会有些脆弱，但如果只是在运行时内存中，则可以接受。 - not my job

@user2894391 ADT 是 一棵树。即使没有路径循环，无环有向图也可以成为拓扑循环。假设我们有顶点1、2、3、4、5和边缘(1,2) (2,4) (1,3) (3,4) (4,5)。如果您尝试将其表示为ADT而不绑定结，您将有两个标记为4的顶点。 - not my job

@enoughreptocomment 在HaskellWiki上并没有关于“tying the knot”（打结）的确切定义。但整篇文章都是关于自引用数据结构的，因此我认为“tying the knot”这个术语仅适用于严格求值会进入无限循环的情况。在您的示例中，即使是一个严格的程序也将终止。 - user3974391

@user2894391 在我看来，以错误的结果终止并不是一件好事。例如：边长之和或平均值、最多折叠次数、遍历次数等。 - not my job

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,[])]

- ErikR

---

Data.Graph 的 topSort 函数的时间复杂度是什么？ - egdmitry

@egdmitry Erlang的实现是线性的，并且使用相同的算法。 - Filip Haglund

Answer 2

你是否有一种可靠的算法方法来处理拓扑排序？有不同的可能性；最著名的两种可能是以下两种：

1. 在图上进行深度优先搜索，根据顶点的完成时间按降序排序。所以：如果你已经有了DFS，请将其改为输出完成时间并按降序排序。

2. 另一种方法要求您在每个顶点中存储未处理边的数量（这可能需要一些预处理，通常是一个图遍历 - 让我们称之为每个顶点的相应字段“边计数器”）。起始节点当然具有边计数器= 0。作为下一个顶点，您只能选择其边计数器设置为0的那些顶点。如果遇到边（a，b，w），则必须将b的边计数器减1。

请注意，可以以这样一种方式实现第二种方法，即您有一个列表candidates，最初仅填充了起始节点。一旦您减少了b的边计数器并看到它现在为0，您就将b添加到candidates中。在下一步中，您选择candidates的头作为要处理的下一个顶点。

要存储边计数，您可以使用例如 HashMap 。以下是第二种方法的一些（非Haskell，但可能接近Haskell）启示：

sortAlgorithm startingNodes sorted (Graph v w) edgeCounts =
    | [] _ _ = sorted    -- processed all nodes? => output result
    | (x:remainingNodes) sorted (Graph v w) =
      let newEdgeCounts = foldl 
          (\ec (a, b, w) -> Data.HashMap.insert ((Data.HashMap.findWithDefault 0 b ec) - 1) ec)
      in sortAlgorithm remainingNodes (sorted ++ [x]) newEdgeCounts

- phimuemue

---

我正在尝试实现这个算法： 当startingNodes非空时 从startingNodes中移除一个节点n 将n添加到已排序的末尾 对于每个具有从n到m的边缘e的节点m 从图中删除边缘e 如果m没有其他入边 将m插入startingNodes中这是直接从维基百科上摘抄的，所以我不知道它是否适用于Haskell，但我想它应该可以工作。使用你描述的两种方法中的哪一种会更好呢？谢谢 - hboy

不，我认为你的方法已经足够好了。你只需要在某个地方存储所提到的“边缘计数”（例如HashMap）即可。 - phimuemue