MathGroup Archive 2004

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

Search the Archive

Re: Computing sets of equivalences

In article <c0uu8a$e84$1 at>,
 Mariusz Jankowski<mjankowski at> 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 

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),


 g = MakeGraph[Range[Min[r],Max[r]], f[r]]

compute the connected components (which we already know),


and show the graph

  ShowGraph[g, VertexNumber -> True]; 


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 

  • Prev by Date: RE: permutations?
  • Next by Date: Re: bug in integration with version 5.0 ?
  • Previous by thread: Re: Computing sets of equivalences
  • Next by thread: RE: RE: Computing sets of equivalences