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