Re: Faster ways to unionize intersecting sets?

*To*: mathgroup at smc.vnet.net*Subject*: [mg70484] Re: [mg70118] Faster ways to unionize intersecting sets?*From*: Adriano Pascoletti <pascolet at dimi.uniud.it>*Date*: Tue, 17 Oct 2006 02:59:42 -0400 (EDT)*References*: <eg02a3$81m$1@smc.vnet.net><eg2e4o$70u$1@smc.vnet.net> <eg81ph$mqh$1@smc.vnet.net> <200610110553.BAA19421@smc.vnet.net>

The problem of unionizing a collection s={s1,s2,...} of intersecting sets si={i1,i2,...} posted by "lsha" <lsha at earthlink.net> on Sat, 7 Oct 2006 has been solved in several ways. Here is another one. Consider the elements i1, i2,... of each set si as vertices of an undirected graph with edges connecting every pair of vertices of si. Then the unionization of intersecting sets amounts to finding the simply connected components of the graph. Define the function adjacencies s.t. adjacencies[s] returns the adjacency lists of the graph In[1]:= adjacencies = Function[s, Reap[Function[i, (Sow[#1, s[[i]]] & ) /@ s [[i]]] /@ Range[Length[s]], _, {#1, Union[#2]} & ][[2]]]; findcomponents[s] will find the connected components In[2]:= findcomponents = Function[vertices, Scan[If[unvisited[#1], v[#1] = + +m; dfsvisit[#1]] & , vertices]]; dfsvisit = Function[i, Scan[If[unvisited[#1], v[#1] = m; dfsvisit [#1]] & , a[i]]]; with In[4]:= unvisited = Head[v[#1]] === v & ; The main function is In[5]:= unionize[s:{___List}] := Block[{a, m = 0, v, L = Union[Flatten[s]]}, Scan[(a[#1[[1]]] = #1[[2]]) & , adjacencies[s]]; findcomponents[L]; Reap[(Sow[#1, v[#1]] & ) /@ L, _][[2]]]; Some examples, In[6]:= unionize[{{1, 2, 3}, {3, 4}, {5, 6, 7}, {7, 8}, {9, 10}}] Out[6]= {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}} In[7]:= unionize[{{1, 2, 3}, {3, 4}, {5, 6, 7}, {7, 8}, {8, 3, 10}}] Out[7]= {{1, 2, 3, 4, 5, 6, 7, 8, 10}} In[8]:= unionize[{{1, 2}, {2, 3}, {4, 5}, {6, 7}, {7, 5}, {9, 10}, {11, 12}, {13, 14}}] Out[8]= {{1, 2, 3}, {4, 5, 6, 7}, {9, 10}, {11, 12}, {13, 14}} Adriano Pascoletti

**References**:**Re: Faster ways to unionize intersecting sets?***From:*"Ray Koopman" <koopman@sfu.ca>