在OCaml的拓扑排序 [英] Topological sort in OCaml
问题描述
我试着写在OCaml中拓扑排序，但我是一个初学者（OCaml中和放大器;图形算法），我不能独自做到这一点
I'm trying to write topological sorting in ocaml, but I'm a beginner (in OCaml & graphs algorithms) and I can't do this by myself.
它更容易让我想到拓扑排序中，例如C ++（且有拓扑排序的C ++在互联网上有很多例子），但我想学习新的东西。此外，我发现写在OCaml的拓扑排序的例子，但我不理解他们，要坦率地说。
It's easier for me to think about topological sorting in, for example, C++ (and there is a lot examples of topological sorting in C++ on the Internet), but I want to learn something new. Moreover, I've found some examples of topological sorting written in OCaml, but I don't understand them, to be frankly.
让我们说我有一个List （INT * INT列表）名单，例如：
Let's say I have a list (int * int list) list, for example:
myList上= [（1，[2]）; （5，[6; 7]）; （3，[2]）; （6，[3,7]）; （8，[7]）; （4，[3; 1）]。
这意味着，我需要做的任务 1 任务之前 2 ，任务 4 任务之前 3 和 1 等。
and that means, that I need to "do" task 1 before task 2, task 4 before tasks 3 and 1 etc.
我想，对于这个列表的输出应该是：
I think, that output for this list should be:
[8; 5; 6; 7; 4; 3; 1; 2]
（但是我不知道，因为我刚才提出这个例子，所以如果我错了，纠正我请）
(however I'm not sure, because I just made this example, so if I'm wrong, correct me please)
另外，我读过，这拓扑排序不为图个周期的工作，所以必须有某种条件的周期 - 当给定的图有周期（S），我们引发异常（我认为这是一个好主意）。
Also, I've read, that topological sort doesn't work for cycles in graphs, so there must be some kind of condition for cycles - when given graph has cycle(s) we raise exception (I think that is a good idea).
AFAIK，我需要使用DFS的算法进行拓扑排序，其中（DFS），我不知道如何在OCaml中实现（我的理解主要的想法，但我不的感觉的，如何在OCaml中/函数式编程）。
AFAIK, I need to use DFS in algorithm for topological sort, which (DFS) I don't know how to implement in OCaml (I understand main idea, but I don't feel, how that works in OCaml/functional programming).
我真的AP preciate您的帮助，了解我这个概念（我的意思是拓扑排序，DFS在OCaml中/函数式编程）。如果可以的话，这将是巨大的，如果你告诉我的例子codeS，因为阅读code是（对我来说）了解算法的概念的最好方法。
I would really appreciate Your help to understand me this concepts (I mean topological sort, DFS in OCaml/functional programming). If You can, it would be great, if You show me example codes, because reading code is (for me) the best method to understand algorithm's concept.
我知道，对于大多数的你，这是一个简单的问题，但我希望，它不会阻止你帮我。
I know, that for most of You this is a simple question, but I hope, that it won't keep You from helping me.
PS：我在学习OCaml的由我自己（我在高中的），所以我没有坚实的理论背景（无论是在ocaml的或算法）。我已经开始学习OCaml的，因为我想了解递归的概念，而现在这种语言看起来很有趣，因为是从C ++真的不一样，所以我还在努力学习OCaml中一些新的东西。
PS: I'm learning OCaml by myself (I'm in a high school), so I don't have solid theory background (either in OCaml or algorithms). I had started learning OCaml, because I wanted to understand recursion concept, and now this language seems to be interesting, because is really different from C++, so I'm still trying to learn something new in OCaml.
推荐答案
首先，请注意语言Objective Caml不支持的编程风格，尽管语法上的不同，是相当类似于C ++，通过可变数据结构的方法（参考，数组，哈希表）和命令式结构（for和while循环，变量赋值）。我假设之下，你实际上是试图写地道的纯功能性风格的拓扑排序。
First, be aware that Objective Caml does support a programming style which, despite syntactic differences, is fairly similar to C++, by means of mutable data structures (references, arrays, hash tables) and imperative constructs (for and while loops, variable assignment). I'm assuming below that you're actually trying to write your topological sort in idiomatic pure functional style.
纯函数式编程主要是声明：适用于该值此功能的是这个其它的值。这也就是为什么的右侧令x = 是使用<$ C $的前pression（计算结果为一个值），而不是动作序列C>返回。当然，适应即通常描述为一系列步骤，而不是一种算法时会出现麻烦。
Pure functional programming is mostly declarative : this function applied to that value is this other value. This is why the right-hand side of let x = is an expression (evaluates to a value) instead of a sequence of actions that uses return. Of course, trouble appears when adapting an algorithm that is commonly described as a series of steps instead.
幸运的是，有一个模式（实际上，一个家庭的模式），可以让你重新函数式present势在必行十岁上下的算法，通过打开更改X的值为返回一个新的对象，它是相同的旧的，除了X的值。
Fortunately, there's a pattern (actually, a family of patterns) that lets you represent imperative-ish algorithms in functional style by turning "change the value of X" into "return a new object which is identical to the old one, except for the value of X".
一个传统的DFS算法涉及通过图形步进，同时记住哪些元素已被访问 - 一般（这样你就不能访问他们不止一次），并让你的当前位置（这样就可以检测周期）。所以，一个DFS算法的必要状态由当前节点，该组访问过的节点，并在该电流路径的节点集的。所有这些数据将不得不被提供给递归调用，和任何永久性的变化将必须通过这些相同的递归调用返回。
A traditional DFS algorithm involves stepping through the graph while remembering which elements have already been visited - in general (so that you don't visit them more than once) and to get to your current position (so that you can detect cycles). So, the imperative state of a DFS algorithm is comprised of the current node, the set of visited nodes and the set of nodes in the current path. All this data will have to be provided to the recursive calls, and any permanent changes will have to be returned by those same recursive calls.
使用您的图形结构上面，再加上一个列表重新presentation为两套（它几乎没有优化 - 设置将是一个更好的选择在这里），该算法看起来有点像这样的：
Using your graph structure from above, combined with a list representation for the two sets (it's hardly optimal - Set would be a better choice here), the algorithm would look somewhat like this:
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 不是由递归调用修改探索。这是情况下的一个例子，其中功能性数据结构是更舒适的比必须的结构的工作。
Three important details above: first, DFS says that one you are done exploring all the children of a given node, you should remove that node from the "current path" list and put it into the "visited" list. Since we're using immutable data structures, the first step is unnecessary: its only purpose was to undo the insertion of the node when the exploration started, and in our version the list new_path is not modified by the recursive call to explore. This is an example of case where functional data structures are more comfortable to work with than imperative structures.
另外一个重要的细节是使用 List.fold_left 的。当我们开始做了明确的状态，我们替换类隐势在必行功能 - ＆GT;单元与类型的明确职能 - ＆GT;状态 - ＆GT; .. - ＆GT;状态（接受国家为参数，返回新的状态）。因此，当务之急名单的探索，它是这样的：
Another important detail is the use of List.fold_left. When we started making the state explicit, we replaced implicit imperative functions of type -> unit with explicit functions of type -> state -> .. -> state (accept the state as parameter, return new state). So, the imperative list exploration, which looked like this:
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状态[edge_1; edge_2; edge_3] 一样。的Tooting我自己的喇叭，但是我有对此一篇很好的文章在这里。
Which is exactly what List.fold_left f state [edge_1 ; edge_2 ; edge_3] does. Tooting my own horn, but I have a nice article about this here.
第三点是，添加元素，设置操作，使用列表时重新present套，被简单地写成元素::设为，因为这是一个返回一组新的（表），其中包含的原始集合的所有元素连同新元素的操作。这使得原设定不变（这是很好的第一步中描述的原因），而使用的内存一定量（它会创建一个利弊的细胞 - 一个简单的头尾对含参照元素和参照组）：你不仅获得撤消能力，但你这样做，无需额外费用
The third point is that the "add element to set" operation, when using lists to represent sets, is written simply as element :: set, because this is an operation that returns a new set (list) which contains all the elements of the original set along with the new element. This leaves the original set untouched (which is good for the reasons described in step one) while using a constant amount of memory (it creates a cons cell - a simple head-tail pair containing a reference to the element and a reference to the set) : not only do you get undo capabilities, but you do so at no additional cost.
以上算法插入节点到访问先从DFS探索的叶子，而你的情况再present这些节点应最后完成。总之，返回的列表拓扑排序 - 但可能不包含所有元素，因为起点可能不是唯一的根元素（或者甚至是一个根元素的话）。所以，有这里涉及一个附加的处理步骤，其包括在采取另一节点从图中，直到所有的图形已探索
The above algorithm "inserts" nodes into visited starting with the leaves of the DFS exploration, which in your case represent those nodes that should be done last. In short, the returned list is topologically sorted - but might not contain all elements because the starting point might not be the only root element (or even be a root element at all). So, there's an additional processing step involved here which consists in taking another node from the graph until all the graph has been explored.
或者，换言之，开始从每个节点图中的一个新的DFS勘探的 的，但忽略previously探索任何节点的 - 这相当于保持访问了元素从一个DFS勘探到下一列表。
Or, in other words, starting a new DFS exploration from every node in the graph, but ignoring any nodes previously explored - which is equivalent to keeping the list of visited elements from one DFS exploration to the next.
用一个小的调整我们的previous算法，这往往只需要两行：
Using a small tweak to our previous algorithm, this takes only two lines:
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 和之前一样。
The tweak consists in allowing the caller of dfs to specify the list of already visited nodes. Carrying over the list of visited nodes while starting a DFS from every node is done using List.fold_left exactly as before.
修改：除了异常的类型，这里没有什么是限制在图形中元素的类型。然而，一个异常不能是多态的，所以你有两种可能的解决方案。首先是放弃实际上返回任何数据以及异常：
EDIT: aside from the type of the exception, there's nothing here that constrains the type of the elements in the graph. However, an exception cannot be polymorphic, so you have two possible solutions. The first is to give up on actually returning any data along with the exception:
exception CycleFound
... raise CycleFound ...
这将恢复类型 toposort 返回到一个更通用的（'A *（'列表））列表 - ＆GT; 列表。
This will revert the type of toposort back to a more generic ('a * ('a list)) list -> 'a list.
另一种解决方案是相当先进的OCaml的：你需要做的模块的包含异常，拓扑排序多态性在特定的类型，如下所示：
The other solution is rather advanced OCaml : you need to make the module that contains the exception and the topological sort polymorphic in that specific type, as follows:
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
这将使类型的地形（节点）.sort 是（Node.t *（Node.t列表））列表 - ＆GT ; Node.t列表，这意味着你可以按你希望定义一个节点舱与该类型的任何类型：
This would make the type of Topo(Node).sort be (Node.t * (Node.t list)) list -> Node.t list, which means you can sort any type you wish by defining a node module with that type:
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
这篇关于在OCaml的拓扑排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
