Grouping pairs - suggested tools

[Peter Otten]

Arnaud Delobelle wrote:

> I think I would go for the two-step approach of constructing the graph
> first and then recursively building connected components.  It sounds
> more complicated at first but when you implement it it turns out quite
> simple:
> 
> from collections import defaultdict
> from itertools import count
> 
> def build_groups(edges):
>     neighbors = defaultdict(set)
>     for x, y in edges:
>         neighbors[x].add(y)
>         neighbors[y].add(x)
> 
>     groups, group_indices = {}, count(1)
>     def set_group(x, group_index):
>         groups[x] = group_index
>         for y in neighbors[x]:
>             if y not in groups:
>                 set_group(y, group_index)
> 
>     for x in neighbors:
>         if x not in groups:
>             set_group(x, group_indices.next())
>     return groups

That looks a little less like legwork than mine. My only objection is that 
you may hit Python's low recursion limit.

Peter