Grouping pairs - suggested tools

[Arnaud Delobelle]

On Sep 22, 8:30 am, Peter Otten <__pete... at web.de> wrote:
> 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

True.  One could setrecursionlimit() temporarily to work around this.
Or here is an alternative set_group() function:

def set_group(x, group_index):
    group = [x]
    for y in group:
        groups[y] = group_index
        group.extend(z for z in neighbors[y] if z not in groups])

It's untested!

--
Arnaud