Grouping pairs - suggested tools

[Arnaud Delobelle]

On Sep 20, 10:42 pm, Astley Le Jasper <astley.lejas... at 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