Kosaraju: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 7:
;References:
* The article on [[wp:Kosaraju's_algorithm|Wikipedia]].
=={{header|C sharp|C#}}==
<lang csharp>using System;
using System.Collections.Generic;
class Node
{
public enum Colors
{
Black, White, Gray
}
public Colors color { get; set; }
public int N { get; }
public Node(int n)
{
N = n;
color = Colors.White;
}
}
class Graph
{
public HashSet<Node> V { get; }
public Dictionary<Node, HashSet<Node>> Adj { get; }
/// <summary>
/// Kosaraju's strongly connected components algorithm
/// </summary>
public void Kosaraju()
{
var L = new HashSet<Node>();
Action<Node> Visit = null;
Visit = (u) =>
{
if (u.color == Node.Colors.White)
{
u.color = Node.Colors.Gray;
foreach (var v in Adj[u])
Visit(v);
L.Add(u);
}
};
Action<Node, Node> Assign = null;
Assign = (u, root) =>
{
if (u.color != Node.Colors.Black)
{
if (u == root)
Console.Write("SCC: ");
Console.Write(u.N + " ");
u.color = Node.Colors.Black;
foreach (var v in Adj[u])
Assign(v, root);
if (u == root)
Console.WriteLine();
}
};
foreach (var u in V)
Visit(u);
foreach (var u in L)
Assign(u, u);
}
}</lang>
=={{header|C++}}==
Line 99 ⟶ 173:
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
=={{header|D}}==
Line 625:
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
=={{header|Perl}}==
Line 709 ⟶ 708:
Fred Gary
Hank</pre>
=={{header|Phix}}==
Line 902 ⟶ 838:
<pre>'((7) (6 5) (4 3) (2 1 0))</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2018.09}}
Inspired by Python & Kotlin entries.
Accepts a hash of lists/arrays holding the vertex (name => (neighbors)) pairs. No longer limited to continuous, positive, integer vertex names.
<lang perl6>sub kosaraju (%k) {
my %g = %k.keys.sort Z=> flat ^%k;
my %h = %g.invert;
my %visited;
my @stack;
my @transpose;
my @connected;
sub visit ($u) {
unless %visited{$u} {
%visited{$u} = True;
for |%k{$u} -> $v {
visit($v);
@transpose[%g{$v}].push: $u;
}
@stack.push: $u;
}
}
sub assign ($u, $root) {
if %visited{$u} {
%visited{$u} = False;
@connected[%g{$u}] = $root;
assign($_, $root) for |@transpose[%g{$u}];
}
}
.&visit for %g.keys;
assign($_, $_) for @stack.reverse;
(|%g{@connected}).pairs.categorize( *.value, :as(*.key) ).values.map: { %h{|$_} };
}
# TESTING
-> $test { say "\nStrongly connected components: ", |kosaraju($test).sort } for
# Same test data as all other entries, converted to a hash of lists
(((1),(2),(0),(1,2,4),(3,5),(2,6),(5),(4,6,7)).pairs.hash),
# Same layout test data with named vertices instead of numbered.
(
%(:Andy<Bart>,
:Bart<Carl>,
:Carl<Andy>,
:Dave<Bart Carl Earl>,
:Earl<Dave Fred>,
:Fred<Carl Gary>,
:Gary<Fred>,
:Hank<Earl Gary Hank>)
)</lang>
{{out}}
<pre>
Strongly connected components: (0 1 2)(3 4)(5 6)(7)
Strongly connected components: (Andy Bart Carl)(Dave Earl)(Fred Gary)(Hank)</pre>
=={{header|Sidef}}==
| |||