% 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);