clever programming solution wanted

[Jeff Epler]

It sounds to me like you have a somewhat odd representation of an
undirected graph and you want to find connected components.

http://www.cs.sunysb.edu/~algorith/files/dfs-bfs.shtml
http://www.csee.usf.edu/~maurer/graphs/sld024.htm
etc

In an edge-list representation, I think the solution looks something
like (untested):
    all_components = []
    while input:
        initial_element = input.pop()
        visit = [initial_element]
        component = Set([initial_element])
        while visit:
            v = visit.pop()
            vs = neighbors[v] - component:
            component |= vs
            visit.extend(vs)
        all_components.append(component)
        input -= component
This is a O(V+E) algorithm unless I messed something up.

Converting from your d[Ki] = [Tj, Tk, ...] to edge-list representation
is probably O(V^2).  Something like (untested):
    neighbors = dict([(v, Set()) for v in d])
    ds = dict([(k, Set(v)) for k, v in d.iteritems()])
    for v1 in d:
        for v2 in d:
            if ds[v1] & ds[v2]:
                neighbors[v1].add(v2)
                neighbors[v2].add(v1)

Jeff
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20040715/41d1e80e/attachment.sig>