strongly connected components(SCC graph algorithm) in SML

Question

Hi I need to write SCC algorithm in standard ML. but I don't know how to do that. I have following TYPEs whitch has to be uesd in code:

type vertex = int
type edge = int * int
type graph = (vertex * vertex list) list


fun dfs (g: graph) (n: vertex): vertex list = 
  let
    fun helper (todo: vertex list) (visited: vertex list): vertex list =
    case todo of
      [] => []
    | h::t => if (List.exists (fn x => x = h) visited)
                then helper t visited
                else
                  let
                    val adj = case List.find (fn (n, _) => n = h) g of
                                NONE => raise Fail "incomplete adjacency list"
                              | SOME (_, adj) => adj
                  in
                    h :: (helper (adj @ t) (h::visited))
                  end
  in
    helper [n] []
  end

The above code has been compiled and run correctly. I put these code because I know in computing SCC dfs is needed. so does anyone has any solution?

Answer 1

Pseudo code - http://algowiki.net/wiki/index.php/Tarjan's_algorithm.

Answer 2

I'm guessing that you're trying to use Standard ML ( http://www.smlnj.org/sml.html ) .

During your classroom time, your teacher should have presented either a modelling tool with which to create your SML code, or should have referred you to a resource with which to write the code. S/he should also have presented sample code - and your book (or a CD in the back of your book) should include SML code.

Assuming you don't have a modelling tool, my recommendation is as follows. Start by refering to the sample code that your teacher or book offers, and pick the code that solves a problem most similar to your needs. Copy & paste that into your answer, being absolutely sure to clearly cite the source at the very beginning of the answer. Then, use other examples from class, the details from your book, and the resources under the "documentation and literature" section of smlnj.org (particularly the tutorials) to implement your solution.

Then, if you have a stumbling block - something that wasn't discussed in class, and wasn't covered in your book, but you just can't solve, you should discuss it with your TA or your teacher. If you ask the question to one of them, then your teacher can find out that the topic wasn't clearly covered in class. If you don't ask them, then they won't know, and much of the rest of your class may have difficulty with the topic.

And finally, if your teacher and TA aren't available, and you're running into a problem that you just don't know how to solve, and you have a very specific question (like, "here's my code; it won't compile and I can't figure out why"), at that point you should ask Stack Overflow.