On 20/09/2010 22:42, Astley Le Jasper 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.
[snip]
I thought I'd join in. I've used repr to ensure that I have something
that's hashable:
def show_groups(pairs):
groups = {}
items = {}
for x, y in pairs:
x_repr, y_repr = repr(x), repr(y)
items[x_repr] = x
items[y_repr] = y
x_group = groups.setdefault(x_repr, set([x_repr]))
y_group = groups.setdefault(y_repr, set([y_repr]))
union = set()
for m in x_group | y_group:
union |= groups[m]
for m in union:
groups[m] = union
indexes = {}
for s in groups.values():
indexes.setdefault(frozenset(s), len(indexes) + 1)
indexes = sorted(indexes.items(), key=lambda pair: pair[1])
for s, i in indexes:
for m in sorted(s):
print("{0} {1}".format(i, items[m]))
if __name__ == "__main__":
edges = [
('a', 'b'),
('a', 'c'),
('a', 'd'),
('b', 'c'),
('b', 'd'),
('c', 'd'),
('e', 'f'),
('e', 'g'),
('f', 'g'),
('h', 'i'),
]
show_groups(edges)
print()
show_groups([('a', 'c'), ('b', 'd'), ('c', 'd')])
--
http://mail.python.org/mailman/listinfo/python-list
