

 This page uses content from Wikipedia. The original article was at Graph. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



Kosaraju's algorithm (also known as the Kosaraju–Sharir algorithm) is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju. The same algorithm was independently discovered by Micha Sharir and published by him in 1981. It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.


For this task consider the directed graph with these connections:

 0 -> 1
 1 -> 2
 2 -> 0
 3 -> 1,  3 -> 2,  3 -> 4
 4 -> 3,  4 -> 5
 5 -> 2,  5 -> 6
 6 -> 5
 7 -> 4, 7  -> 6, 7 -> 7

And report the kosaraju strongly connected component for each node.



References

 The article on Wikipedia.
 
program KosarajuApp;
 
uses
  System.SysUtils;
 
type
  TKosaraju = TArray<TArray<Integer>>;
 
var
  g: TKosaraju;
 
procedure Init();
begin
  SetLength(g, 8);
  g[0] := [1];
  g[1] := [2];
  g[2] := [0];
  g[3] := [1, 2, 4];
  g[4] := [3, 5];
  g[5] := [2, 6];
  g[6] := [5];
  g[7] := [4, 6, 7];
end;
 
procedure Println(vector: TArray<Integer>);
var
  i: Integer;
begin
  write('[');
  if (Length(vector) > 0) then
    for i := 0 to High(vector) do
    begin
      write(vector[i]);
      if (i < high(vector)) then
        write(', ');
    end;
 
  writeln(']');
end;
 
function Kosaraju(g: TKosaraju): TArray<Integer>;
var
  vis: TArray<Boolean>;
  L, c: TArray<Integer>;
  x: Integer;
  t: TArray<TArray<Integer>>;
  Visit: TProc<Integer>;
  u: Integer;
  Assign: TProc<Integer, Integer>;
begin
  // 1. For each vertex u of the graph, mark u as unvisited. Let L be empty.
  SetLength(vis, Length(g));
  SetLength(L, Length(g));
  x := Length(L);
  // index for filling L in reverse order
  SetLength(t, Length(g)); // transpose graph
 
  // 2. recursive subroutine:
 
  Visit := procedure(u: Integer)
    begin
      if (not vis[u]) then
      begin
        vis[u] := true;
        for var v in g[u] do
        begin
          Visit(v);
          t[v] := concat(t[v], [u]);
          // construct transpose
        end;
 
        dec(x);
        L[x] := u;
      end;
    end;
 
  // 2. For each vertex u of the graph do Visit(u)
 
  for u := 0 to High(g) do
  begin
    Visit(u);
  end;
 
  SetLength(c, Length(g)); // result, the component assignment
 
  // 3: recursive subroutine:
 
  Assign := procedure(u, root: Integer)
    begin
      if vis[u] then
      // repurpose vis to mean "unassigned"
      begin
        vis[u] := false;
        c[u] := root;
 
        for var v in t[u] do
          Assign(v, root);
      end;
    end;
 
  // 3: For each element u of L in order, do Assign(u,u)
 
  for u in L do
    Assign(u, u);
 
  Result := c;
end;
 
begin
  Init;
  Println(Kosaraju(g));
end.