Re: Computing sets of equivalences

*To*: mathgroup at smc.vnet.net*Subject*: [mg46468] Re: Computing sets of equivalences*From*: Paul Abbott <paul at physics.uwa.edu.au>*Date*: Fri, 20 Feb 2004 00:29:13 -0500 (EST)*Organization*: The University of Western Australia*References*: <c0uu8a$e84$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

In article <c0uu8a$e84$1 at smc.vnet.net>, Mariusz Jankowski<mjankowski at usm.maine.edu> wrote: > 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}}. Not my area, but I assume that DiscreteMath`Combinatorica` has code for this? Working backwards from your output, r = {{1, 2, 3, 4, 5, 6}, {7, 8}, {10, 14}, {11, 12, 13}} defining a test to check if a pair {a,b} appears in the connected components list, f[r_][a_, b_] := Or @@ (Intersection[#, {a, b}] == Sort[{a, b}] & ) /@ r we can make a graph (here including the extra vertex "9" which does not appear in your list -- this could be avoided by renumbering), <<DiscreteMath`Combinatorica` g = MakeGraph[Range[Min[r],Max[r]], f[r]] compute the connected components (which we already know), ConnectedComponents[g] and show the graph ShowGraph[g, VertexNumber -> True]; Cheers, Paul -- Paul Abbott Phone: +61 8 9380 2734 School of Physics, M013 Fax: +61 8 9380 1014 The University of Western Australia (CRICOS Provider No 00126G) 35 Stirling Highway Crawley WA 6009 mailto:paul at physics.uwa.edu.au AUSTRALIA http://physics.uwa.edu.au/~paul