Computing sets of equivalences
- To: mathgroup at smc.vnet.net
- Subject: [mg46437] Computing sets of equivalences
- From: Mariusz Jankowski<mjankowski at usm.maine.edu>
- Date: Wed, 18 Feb 2004 00:37:03 -0500 (EST)
- Organization: University of Southern Maine
- Sender: owner-wri-mathgroup at wolfram.com
Dear Mathgroup, I think this falls into the "classic algorithms" category,
so I hope some of you will find this interesting. I checked archives and
mathsource but did not find anything useful.
I have a list of lists, each sublist implying an equivalence. I am trying to
split the list into lists of equivalences (this is part of a connected
components algorithm). For example, given
{{1,2},{1,5},{2,3},{3,4},{5,6},{7,8},{11,12},{12,13},{10,14}}
I want
{{1,2,3,4,5,6},{7,8},{10,14},{11,12,13}}.
Here is my currently "best" attempt. I accumulate the equivalences by
comparing pairs of list, merging them if they have common elements. At the
end of each iteration I remove all merged pairs from original list and
repeat.
iselectEquivalences[v_]:=Module[{x,y,tmp,pos},
x=v;y={};
While[x=!={},
tmp=x[[1]];
pos={{1}};
Do[
If[Intersection[tmp,x[[i]]]==={}, tmp, tmp=Union[tmp,x[[i]]];
pos=Join[pos, {{i}}]], {i, 2, Length[x]}];
x=Delete[x, pos];
y=Join[y, {tmp}] ];
y]
Can you tell me if you have or know of a realization of this classic
operation that works better/faster? Are there alternative paradigms for
solving this kind of problem.
Thanks, Mariusz