[Date Index] [Thread Index] [Author Index]

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>