OCaml中的拓扑排序

4 回答

• -3

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

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

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

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

  使用上面的图形结构，结合两组的列表表示（这几乎不是最优的 - 这里是一个更好的选择），算法看起来有点像这样：

  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说你已经完成了探索给定节点的所有子节点，你应该从"current path"列表中删除该节点并将其放入"visited"列表中 . 由于我们使用的是不可变数据结构，因此第一步是不必要的：它的唯一目的是在探索开始时撤消节点的插入，而在我们的版本中，列表 new_path 不会被递归调用 explore 修改 . 这是功能数据结构比命令式结构更舒适的情况的示例 .

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

  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 .

  第三点是"add element to set"操作，当使用列表来表示集合时，简单地写为 element :: set ，因为这是一个返回新集合（列表）的操作，其中包含原始集合的所有元素以及新元素 . 这离开了使用恒定量的内存（它创建一个cons单元 - 一个简单的头尾对，包含对元素的引用和对集合的引用），原始集合不受影响（这在第一步中描述的原因是好的）：not not只有你获得撤消功能，但你这样做是免费的 .

  上面的算法"inserts"节点进入 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 的调用者指定已访问节点的列表 . 在完成从每个节点启动DFS的同时对承载的节点列表进行完全使用 List.fold_left 完成 .

  EDIT ：除了异常的类型之外，这里没有任何东西限制图中元素的类型 . 但是，异常不能是多态的，因此您有两种可能的解决方案 . 第一种是放弃实际返回任何数据以及异常：

  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).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
  

  回复于 2024-04-27T10:46:44+08:00
• 18

  [如果您不知道这个术语，我在下面写DAG的意思是“有向无环图”，或者是连接顶点的/来自边缘的集合，这样就没有周期 . ]

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

  您可以从空图表开始构建总订单，并从原始DAG一次添加一条边 . 也就是说，原始DAG中的项目（u，[v1; v2; ...; vn]）对应于边（u，v1），（u，v2），...，（u，vn） . 对于每个这样的边（u，v），从总订单中找到u的前驱P和v的后继S.然后将（p，s）添加到P U 中的所有p和S U 中的所有p的总顺序 .

  现在！更快的方法是在原始DAG中找到一个根（即没有前驱的顶点）并从该根进行深度优先搜索，确保您永远不会访问同一个顶点两次 . 每次回溯遍历时，都会“输出”您要离开的顶点 . 这样就构建了DAG的拓扑类型 . 如果剩下任何顶点，请用其他方式冲洗，然后重复，直至完成所有操作 .

  回复于 2024-04-27T10:46:44+08:00
• -2

  你应该首先尝试DFS，它更容易和有益 .

  回复于 2024-04-27T10:46:44+08:00
• 4

  我没有't know OCaml,but there'这是一个简单的算法Wikipedia认证Kahn我已成功使用（转录到Python） . 这很简单，也许你可以把它翻译成OCaml . 这里是：

  L ← Empty list that will contain the sorted elements
  S ← Set of all nodes with no incoming edges
  while S is non-empty do
      remove a node n from S
      insert n into L
      for each node m with an edge e from n to m do
          remove edge e from the graph
          if m has no other incoming edges then
              insert m into S
  if graph has edges then
      output error message (graph has at least one cycle)
  else 
      output message (proposed topologically sorted order: L)
  

  回复于 2024-04-27T10:46:44+08:00