Anonymous user
Kosaraju: Difference between revisions
→{{header|Sidef}}
(Add Swift) |
|||
Line 955:
<pre>
[0, 0, 0, 3, 3, 5, 5, 7]
</pre>
=={{header|Standard ML}}==
<lang sml>datatype 'a node = Node of 'a * bool ref * 'a node list ref * 'a node list ref
fun node x = Node (x, ref false, ref nil, ref nil)
fun mark (Node (_, r, _, _)) = !r before r := true
fun unmark (Node (_, r, _, _)) = !r before r := false
fun value (Node (x, _, _, _)) = x
fun sources (Node (_, _, ref xs, _)) = xs
fun targets (Node (_, _, _, ref ys)) = ys
fun connect (m, n) =
let
val Node (_, _, _, ns) = m
val Node (_, _, ms, _) = n
in
ms := m :: !ms;
ns := n :: !ns
end
datatype 'a step = One of 'a | Many of 'a list
fun visit (ms, nil) = ms
| visit (ms, One m :: ss) = visit (m :: ms, ss)
| visit (ms, Many nil :: ss) = visit (ms, ss)
| visit (ms, Many (n :: ns) :: ss) =
if mark n then
visit (ms, Many ns :: ss)
else
visit (ms, Many (targets n) :: One n :: Many ns :: ss)
fun assign (xs, nil) = xs
| assign (xs, nil :: ss) = assign (xs, ss)
| assign (xs, (n :: ns) :: ss) =
if unmark n then
assign (value n :: xs, sources n :: ns :: ss)
else
assign (xs, ns :: ss)
fun assigns (xs, nil) = xs
| assigns (xs, n :: ns) =
case assign (nil, (n :: nil) :: nil) of
nil => assigns (xs, ns)
| x => assigns (x :: xs, ns)
fun kosaraju xs = assigns (nil, visit (nil, Many xs :: nil))
fun make (n, i, is) =
let
val xs = Vector.tabulate (n, node)
fun item i = Vector.sub (xs, i)
fun step (i, j) = connect (item i, item j)
fun path (i :: j :: is) = (step (i, j); path (j :: is))
| path _ = ()
in
app path is;
item i
end
val is =
[ [0, 1, 2, 3, 4, 2, 0, 5, 7],
[0, 9, 10, 11, 12, 9, 11],
[1, 12],
[3, 5, 6, 7, 8, 6, 15],
[5, 13, 14, 13, 15],
[8, 15],
[10, 13] ]
val n = make (16, 0, is)
val xs = kosaraju (n :: nil)</lang>
{{out}}
<pre>
> xs;
val it = [[15], [14, 13], [10, 11, 12, 9], [7, 8, 6], [5], [1, 3, 4, 2, 0]]: int list list
</pre>
| |||