% The Awerbuch-Shiloach algorithm for finding the connected components
  of a graph.  See:
    Baruch Awerbuch and Yossi Shiloach.  New Connectivity and MSF Algorithms 
    for Ultracomputer and PRAM.  International Conference on Parallel 
    Processing.  August 1983.  Pages 157--179.
%

function StarCheck(D) =
  let 
      % get pointer to grandparent %
      G = D->D;
      % is parent a self loop? %
      ST = {D == G: D in D; G in G};
      % if parent does not equal grandparent, put false flag in grandparent %
      ST = ST <- {(G,F): D in D; G in G | G /= D}
  % retrieve from grandparent %
  in ST->G $

% 
Finds the connected components of a graph: all vertices in the same component
will be labeled with the same number in the result sequence.
  D -- for each vertex it points to its parent (initially points to self)
  E1,E2 -- the two sides for each edge
%
function ConComp(D,E1,E2) =
  let
    % Conditional Hook -- when E1 points to the son of a root and
                          the parent of E1 is greater than parent of E2 %
    D = D <- {(Di,Dj) : Di in D->E1; Dj in D->E2; Gi in D->(D->E1)
                      | (Gi==Di) and (Di>Dj)};
    % Unconditional Hook -- when E1 points to a star and the parent
                            of E1 does not equal the parent of E2 %
    D = D <- {(Di,Dj) : Di in D->E1; Dj in D->E2
                      ; ST in StarCheck(D)->E1
                      | ST and (Di /= Dj)}
  in 
  if all(StarCheck(D)) 
    % If done, return D %
    then D
    % If not, shortcut and repeat %   
    else ConComp(D->D,E1,E2) $

% An example graph (from JaJa, An Introduction to Parallel Algorithms).

  8                     1    3
   \                  / |    |
    9 - 2 - 13 - 4 - 5  |    7
   /    |             \ |   
  12    11              6 - 10  
%

E1 = [1, 5, 1,  6, 4, 13,  2,  2, 9, 12, 8, 3] $
E2 = [5, 6, 6, 10, 5,  4, 13, 11, 2,  9, 9, 7] $

% This function adds in the dummy vertices and doubles up the edges for
  each direction.
  The input is a vector of the downsides of each edge (E1) 
  and the upsides (E2) %
function ConCompFull(E1,E2) =
  let
    % What is the number of vertices %
    N = 1 + max(max_val(E1),max_val(E2));
    % Create vertices and dummy vertices %
    D = index(N) ++ index(N);
    % Create edges in each direction %
    NE1 = E1 ++ E2;    NE2 = E2 ++ E1
    % Call connected components and remove the dummy vertices when done %
  in take(ConComp(D,NE1,NE2),N) $

% concompfull(e1,e2) should return:
  [0, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1]
%