fun dfs_step nei color [] result = result
| dfs_step nei color (v::remaining) result =
if Array.sub (color, v) = 2 then
dfs_step nei color remaining result
else
if Array.sub (color, v) = 1 then
NONE
else
let
val save = Array.update (color, v, 1)
val part_result = dfs_step nei color (Vector.sub (nei, v)) result
val save' = Array.update (color, v, 2)
val part_result' = part_result >>= (fn rslt => return (v::rslt))
in
dfs_step nei color remaining part_result'
end
fun dfs_all v nei color i result =
if v = i then
result
else
let val processed = dfs_step nei color [i] result
in
dfs_all v nei color (i + 1) processed
end
fun topological_sort g =
let
val v = length g
val nei = Vector.fromList g
val color = Array.array(v, 0)
in
dfs_all v nei color 0 (return [])
end