OCaml中的拓扑排序

Question

我正在尝试在ocaml中编写拓扑排序,但我是初学者(在OCaml和图算法中),我不能自己做.

我更容易考虑拓扑排序,例如C++(并且在互联网上有很多关于C++拓扑排序的例子),但我想学习一些新东西.此外,我已经找到了一些用OCaml编写的拓扑排序的例子,坦率地说,我不明白它们.

假设我有一个列表(int * int list) list,例如:

myList = [(1, [2]); (5, [6; 7]); (3, [2]); (6, [3; 7]); (8, [7]); (4, [3; 1])];;

这意味着,我需要"做"任务1任务之前2,任务4任务之前3和1等

我想,这个列表的输出应该是:

[8; 5; 6; 7; 4; 3; 1; 2]

(但我不确定,因为我刚刚做了这个例子,所以如果我错了,请纠正我)

另外,我已经读过,拓扑排序对于图中的循环不起作用,因此循环必须有某种条件 - 当给定图形有循环时,我们引发异常(我认为这是一个好主意) .

AFAIK,我需要在算法中使用DFS进行拓扑排序,其中(DFS)我不知道如何在OCaml中实现(我理解主要思想,但我不觉得,这在OCaml /函数编程中是如何工作的).

我非常感谢你帮助我理解这个概念(我的意思是拓扑排序,OCaml /函数编程中的DFS).如果可以的话,如果您向我展示示例代码,那将会很棒,因为阅读代码(对我来说)是理解算法概念的最佳方法.

我知道,对于大多数人来说,这是一个简单的问题,但我希望,它不会阻止你帮助我.

PS:我自己学习OCaml(我在高中),所以我没有扎实的理论背景(在OCaml或算法中).我开始学习OCaml,因为我想理解递归概念,现在这种语言看起来很有趣,因为它与C++真的不同,所以我还在尝试学习OCaml中的新东西.

Answer 1

首先,请注意Objective Caml确实支持一种编程风格,尽管语法不同,它与C++非常相似,通过可变数据结构(引用,数组,哈希表)和命令式结构(for和while循环,变量赋值) .我假设你正在尝试用惯用的纯函数式编写拓扑类型.

纯函数式编程主要是声明式的:应用于该值的此函数是另一个值.这就是为什么右侧let x =是表达式(求值为值)而不是使用的一系列动作return.当然,在调整通常被描述为一系列步骤的算法时会出现问题.

幸运的是,有一种模式(实际上是一系列模式)可以让你通过将"将X的值更改为"返回一个与旧的相同的新对象来表示功能样式中的命令式算法,除了X的值".

传统的DFS算法包括单步执行图表,同时记住哪些元素已被访问过 - 通常(这样您不会多次访问它们)并到达当前位置(这样您就可以检测周期).因此,DFS算法的命令状态包括当前节点,访问节点集和当前路径中的节点集.必须将所有这些数据提供给递归调用,并且必须由那些相同的递归调用返回任何永久更改.

使用上面的图形结构,结合两组的列表表示(这几乎不是最佳的 - Set这将是一个更好的选择),算法看起来有点像这样:

let dfs graph start_node = 
  let rec explore path visited node = 
    if List.mem node path    then raise (CycleFound path) else
    if List.mem node visited then visited else     
      let new_path = node :: path in 
      let edges    = List.assoc node graph in
      let visited  = List.fold_left (explore new_path) visited edges in
      node :: visited
  in explore [] [] start_node

上面的三个重要细节:首先,DFS说你已经完成了探索给定节点的所有子节点,你应该从"当前路径"列表中删除该节点并将其放入"访问"列表中.由于我们使用的是不可变数据结构,因此第一步是不必要的:它的唯一目的是在探索开始时撤消节点的插入,而在我们的版本中,列表new_path不会被递归调用修改explore.这是功能数据结构比命令式结构更舒适的情况的示例.

另一个重要细节是使用List.fold_left.当我们开始使状态显式化时,我们用类型-> unit的显式函数替换类型的隐式命令函数-> state -> .. -> state(接受状态作为参数,返回新状态).那么,命令式列表探索,看起来像这样:

f edge_1 ; f edge_2 ; f edge_3

现在看起来像这样:

let state = f (f (f state edge_1) edge_2) edge_3)

究竟是什么呢List.fold_left f state [edge_1 ; edge_2 ; edge_3].嘟嘟我自己的号角,但我在这里有一篇很好的文章.

第三点是,当使用列表来表示集合时,"添加要设置的元素"操作被简单地写为element :: set,因为这是一个返回新集合(列表)的操作,其中包含原始集合的所有元素以及新元素.这使原始集保持不变(这在步骤1中描述的原因是好的)同时使用恒定量的内存(它创建一个cons单元 - 一个简单的头尾对,包含对元素的引用和对集合的引用):您不仅可以获得撤消功能,而且还可以免费获得.

上面的算法visited从DFS探索的叶子开始"插入"节点,在你的情况下代表那些应该在最后完成的节点.简而言之,返回的列表在拓扑上排序 - 但可能不包含所有元素,因为起点可能不是唯一的根元素(甚至根本不是根元素).因此,这里涉及一个额外的处理步骤,其中包括从图中取出另一个节点,直到探索完所有图形.

或者,换句话说,从图中的每个节点开始新的DFS探索,但忽略先前探索的任何节点 - 这相当于将访问过的元素列表从一个DFS探索保持到下一个.

使用我们之前算法的小调整,这只需要两行:

let dfs graph visited start_node = 
  let rec explore path visited node = 
    if List.mem node path    then raise (CycleFound path) else
    if List.mem node visited then visited else     
      let new_path = node :: path in 
      let edges    = List.assoc node graph in
      let visited  = List.fold_left (explore new_path) visited edges in
      node :: visited
  in explore [] visited start_node

let toposort graph = 
  List.fold_left (fun visited (node,_) -> dfs graph visited node) [] graph

调整包括允许调用者dfs指定已访问节点的列表.使用List.fold_left与以前完全相同的方式完成从每个节点启动DFS时访问受访节点列表.

编辑:除了异常的类型,这里没有什么限制图中元素的类型.但是,异常不能是多态的,因此您有两种可能的解决方案.第一种是放弃实际返回任何数据以及异常:

exception CycleFound

... raise CycleFound ...

这会将返回的类型还原toposort为更通用 的类型('a * ('a list)) list -> 'a list.

另一个解决方案是相当高级的OCaml:您需要在该特定类型中创建包含异常和拓扑排序多态的模块,如下所示:

module type NODE = sig
  type t 
end

module type Topo = functor (Node:NODE) -> struct 
  exception CycleFound of Node.t list      
  let dfs ...
  let sort ...  
end

这将使Topo(Node).sortbe 的类型(Node.t * (Node.t list)) list -> Node.t list,这意味着您可以通过定义具有该类型的节点模块来排序您希望的任何类型:

type recipe = Eggs | Milk | Wheat | Mix | Cook | Serve

module Node = struct 
  type t = recipe 
end

let graph = [ Wheat, [Eggs,Milk,Mix] ;
              Milk,  [Mix] ;
              Eggs,  [Mix] ;
              Mix,   [Cook] ;
              Cook,  [Serve] ;
              Serve, [] ]

module RecipeTopo = Topo(Node)

let sorted = RecipeTopo.sort graph

Answer 2

[如果你不知道这个术语，我在下面写 DAG 的意思是“有向无环图”，或者是连接顶点的从/到边的集合，这样就没有循环。]

一种方法是将偏序（DAG 结构）扩展为全序（因此，对于每对不同的顶点 u 和 v，u 是 v 的后继，反之亦然）。然后，您可以按顺序对顶点进行排序：如果 v 是 u 的后继，则 u 位于 v 之前。

您可以通过从空图开始并从原始 DAG 中一次添加一条边来构建总订单。也就是说，原始 DAG 中的一项 (u, [v1; v2; ...; vn]) 对应于边 (u, v1), (u, v2), ..., (u, vn)。对于每个这样的边 (u, v)，从总顺序中找到 u 的前驱 P 和 v 的后继 S。然后将 (p, s) 添加到 PU {u} 中所有 p 和 SU {v} 中所有 s 的总订单中。

现在！更快的方法是在原始 DAG 中找到根（即没有前辈的顶点），并从该根进行深度优先搜索，确保您永远不会两次访问同一个顶点。每次回溯遍历时，都会“输出”要离开的顶点。通过这种方式，您可以构建 DAG 的拓扑排序。如果还有剩余的顶点，请用泡沫冲洗，然后重复，直到全部完成。