On Sep 20, 10:42 pm, Astley Le Jasper <astley.lejas...@gmail.com> wrote: > I have a list of tuples that indicate a relationship, ie a is related > to b, b is related to c etc etc. What I want to do is cluster these > relationships into groups. An item will only be associated with a > single cluster. > > Before I started, I wondered if there was any particular tool within > Python I should be looking at. I don't expect anyone to code this for > me, just say ... "you need to look at using x". I was going to use > populate a dictionary and > > Sorry for being so vague. > > Example Data: > [(a,b) > (a,c) > (a,d) > (b,c) > (b,d) > (c,d) > (e,f) > (e,g) > (f,g) > (h,i)] > > Output (grouping id, item ref) > (1,a), > (1,b), > (1,c), > (1,d), > (2,e), > (2,f), > (2,g), > (3,h), > (3,i)
What you are doing is finding the connected components of a graph. There aren't any tools in the standard library to do this. But for example python-graph [1] has a connected_components function. Probably other packages will. If you don't want a dependency, it is not too hard to implement if you think about it. [1] http://code.google.com/p/python-graph/ -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
