%----------------------------------------------- Guy Blelloch, 1995 Finds the spanning tree of a graph using the hybrid technique discussed in: John Greiner. A Comparison of Data-Parallel Algorithms for Connected Components. Proceedings Symposium on Parallel Algorithms and Architectures, pages 16--25, June 1994. For m edges and n vertices, it has a worst case work of O(m lg n) and a worst case time of O(lg^2 n). For many types of graphs it does closer to O(m) work with O(lg n) time. In this implementation graphs are represented as a tagged edgelist. Each edge is represented as a tripple consisting of a unique identifier for the edge, and two indices of the vertices the edge passes between. -------------------------------------------------- % %------------------------------------------------- Shortcuts a set or trees so that all vertices point to the root -------------------------------------------------- % function shortcut_all(p) = let pp = p->p; in if eql(p,pp) then pp else shortcut_all(pp) \$ %------------------------------------------------- Updates edge with values on the vertices they point to -------------------------------------------------- % function update_edges(E,V) = {i,v1,v2 : i,e1,e2 in E ; v1 in v->{e1:(i,e1,e2) in E} ; v2 in v->{e2:(i,e1,e2) in E}} \$ %------------------------------------------------- This routine hooks the vertices using the edges to form a set of trees, shortcuts until all vertices point to a root, and then updates the edges to point to the root. The hooking is either from vertices with a larger index to ones with a smaller index, or the other way around depending on the whether direction is true or false. The routine returns the parent pointers, the updated edges and the identifiers of edges that participated in the hook. -------------------------------------------------- % function hook_and_shortcut(P,E,direction) = let % Flip edges so they all point in the same direction. This guarantees that we do not generate cycles when hooking % e = {i,if (e1 > e2 xor direction) then (e1,e2) else (e2,e1) : i,(e1,e2) in e}; % Attemp a hook by writing edge identifier to vertex % a = [0:#P]<-{e1,i : i,e1,e2 in E}; % Check which edges successfully hooked % TI,TE = unzip({i,e in E ; j in a->{e1: i,e1,e2 in E} | i == j}); % Now execute actual hook, and then shortcut % P = shortcut_all(P<-TE); % update edges to point to new parent % E = update_edges(E,P); % remove self edges % E = {i,(e1,e2) in E | e1 /= e2}; in P,E,TI \$ %----------------------------------------------- Finds the spanning of a graph represented as an edgelist. The input E is a sequence of edges each of which consits of an indentifier along with the indices of the two endpoints. n is the number of vertices in the graph. The algorithm returns the identifiers of the edges on a spanning tree. ----------------------------------------------- % function spanning_tree(E,n) = if #E == 0 then [] int else let % Hook from larger to smaller % (P,E,TI_D) = hook_and_shortcut([0:n],E,t); % Hook from smaller to larger % (P,E,TI_U) = hook_and_shortcut(P,E,f); % Compress graph by identifying the roots and relabeling the edges % roots = {p == i : p in P ; i in [0:n]}; labels = enumerate(roots); E = update_edges(e,labels); n = count(roots); % Recurse -- the new n is at most 1/2 the original n so that the total number of recursive calls is O(lg n) % in TI_D ++ TI_U ++ spanning_tree(E,n) \$