% 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]
%