StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POTopological sort in OCaml
text
Body
copied!<p>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.</p> <p>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.</p> <p>Let's say I have a list <code>(int * int list) list</code>, for example:</p> <p><code>myList = [(1, [2]); (5, [6; 7]); (3, [2]); (6, [3; 7]); (8, [7]); (4, [3; 1])];;</code></p> <p>and that means, that I need to "do" task <code>1</code> before task <code>2</code>, task <code>4</code> before tasks <code>3</code> and <code>1</code> etc.</p> <p>I think, that output for this list should be:</p> <p><code>[8; 5; 6; 7; 4; 3; 1; 2]</code></p> <p>(however I'm not sure, because I just made this example, so if I'm wrong, correct me please)</p> <p>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).</p> <p>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 <em>feel</em>, how that works in OCaml/functional programming).</p> <p>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.</p> <p>I know, that for most of You this is a simple question, but I hope, that it won't keep You from helping me.</p> <p>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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload