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