algorithm - OCaml中的拓扑排序

Question

我试图用ocaml编写拓 flutter 排序，但是我是一个初学者(使用OCaml和图形算法)，我自己无法做到。

对于我来说，考虑C++中的拓 flutter 排序比较容易(并且Internet上有很多C++中的拓 flutter 排序示例)，但是我想学习一些新知识。此外，坦率地说，我发现了一些用OCaml编写的拓 flutter 排序示例，但我不理解它们。

假设我有一个列表(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]
(但是我不确定，因为我只是举了这个例子，所以如果我错了，请纠正我)

另外，我读过，拓 flutter 排序不适用于图的循环，因此循环必须有某种条件-当给定的图具有循环时，我们会引发异常(我认为这是一个好主意) 。

AFAIK，我需要在算法中使用DFS进行拓 flutter 排序，该DFS我不知道如何在OCaml中实现(我了解主要思想，但我不知道这在OCaml /函数式编程中如何工作)。

我非常感谢您的帮助，以帮助我理解这个概念(我的意思是拓 flutter 排序，OCaml /函数式编程中的DFS)。如果可以的话，如果您向我展示示例代码，那就太好了，因为(对我来说)阅读代码是理解算法概念的最佳方法。

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

PS:我正在独自学习OCaml(我正在读高中)，所以我没有扎实的理论背景(无论是OCaml还是算法)。我已经开始学习OCaml，因为我想了解递归的概念，现在这种语言似乎很有趣，因为它确实与C++不同，因此我仍在尝试学习OCaml中的新知识。

Answer 1

首先，请注意，Objective Caml确实支持一种编程样式，尽管存在语法上的差异，但通过可变数据结构(引用，数组，哈希表)和命令式构造(for和while循环，变量赋值)，它与C++非常相似。 。我在下面假设您实际上是在尝试按惯用的纯函数样式编写拓 flutter 排序。

纯粹的函数式编程主要是声明性的:应用于该值的此函数是此另一个值。这就是let x =右侧是一个表达式(求值)而不是使用return的一系列 Action 的原因。当然，改编通常描述为一系列步骤的算法时会出现麻烦。

幸运的是，有一种模式(实际上是一系列模式)，可以通过将“更改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]正是这样做的。吹着我自己的喇叭，但是我有 a nice article about this here。

第三点是，当使用列表表示集合时，“将元素添加到集合”操作被简单地编写为 element :: set，因为这是一个返回新集合(列表)的操作，其中包含原始集合的所有元素与新元素。这将使原始集保持不变(这对于步骤1中所述的原因而言是不错的)，同时使用恒定数量的内存(它会创建一个cons单元-一个简单的头尾对，其中包含对元素的引用和对集的引用):您不仅可以获得撤消功能，而且无需任何额外费用。

上面的算法从DFS探索的叶子开始将节点“插入”到 visited中，在您的情况下，这些叶子代表应该最后完成的那些节点。简而言之，返回列表按拓 flutter 进行排序-但可能不包含所有元素，因为起点可能不是唯一的根元素(甚至根本不是根元素)。因此，这里涉及一个额外的处理步骤，包括从图中获取另一个节点，直到浏览完所有图为止。

或者换句话说，从图中的每个节点开始新的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:您需要使包含异常和该特定类型的拓 flutter 排序多态的模块，如下所示:

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).sort的类型为 (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