[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
Prev by Date:
**Re: "Not a floating-point number" WHY?**
Next by Date:
**Re: Functions inside list**
Previous by thread:
**Re: Faster ways to unionize intersecting sets?**
Next by thread:
**Re: Faster ways to unionize intersecting sets?**
| |