% 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)
E -- an array of edges
%
function ConComp(D,E) =
let
E1,E2 = unzip(E);
% 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,E) $
% An example graph (from JaJa, An Introduction to Parallel Algorithms).
8 1 3
\ / | |
9 - 2 - 13 - 4 - 5 | 7
/ | \ |
12 11 6 - 10
%
edges = [(1, 5), (5, 6), (1, 6), (6, 10), (4, 5), (13, 4),
(2, 13), (2, 11), (9, 2), (12, 9), (8, 9), (3, 7)];
% This function adds in the dummy vertices and doubles up the edges for
each direction.
The input is a vector of edges and the number of nodes %
function aw_connected_components(E,n) =
let
% Create vertices and dummy vertices %
D = index(N) ++ index(N);
% Create edges in each direction %
E = E ++ {(i,j) : (j,i) in E};
% Call connected components and remove the dummy vertices when done %
in take(ConComp(D,E),N) $
aw_connected_components(edges,14);