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.

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}}