On Sep 22, 8:30 am, Peter Otten <__pete...@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
--
http://mail.python.org/mailman/listinfo/python-list
