Note:

You are viewing a development version of the library. Goto the latest version.

let topological_sort t =
  let size = Array.length t.vertexes in

  (* Empty list that will contain the sorted vertexes *)
  let l = ref [] in

  (* Visited vertexes *)
  let visited = Array.make size false in

  let reverted_edges =
    let arr = Array.make size [] in
      for v1 = 0 to size - 1 do
        SetInt.iter
          (fun v2 -> arr.(v2) <- v1 :: arr.(v2))
          !(snd t.vertexes.(v1))
      done;
      arr
  in

  let rec visit v =
    if not visited.(v) then
      begin
        visited.(v) <- true;
        List.iter visit reverted_edges.(v);
        l := v :: !l
      end
  in

    (* Go through all vertexes with no outgoing edges *)
    for v = 0 to size - 1 do
      visit v
    done;
    !l