clever programming solution wanted

[David Eppstein]

In article <NY2dnS5S670Vm2rdRVn-uA at comcast.com>,
 "Larry Bates" <lbates at swamisoft.com> wrote:

> Maybe someone else can decipher this.  I just don't
> know what "such that the groups are maximal" could
> possibly mean.
> 
> Larry Bates
> 
> "Scott Rifkin" <sar38 at pantheon.yale.edu> wrote in message
> news:Pine.LNX.4.44.0407151728020.7818-100000 at ajax.its.yale.edu...
> > If anyone has a good, quick solution to the following in python2.3
> > I'd appreciate it:
> >
> > I have a dictionary with keys K1, K2, ..., K10000
> > Each entry looks like:
> >
> > dict[K1]=[T1,T4,T500]
> >
> > where the T's are indexed from, say, 1 to 20000 and each K has some number
> > of Ts (not always 3).
> >
> > I want to create groups of Ks which share Ts such the groups are maximal,
> > for instance:
> >
> > dict[K1]=[T1,T4,T500]
> > dict[K2]=[T1]
> > dict[K3]=[T500,T7000]

The way I interpreted it: draw an undirected bipartite graph from the 
K's to the T's, find connected components, and report the K's in each 
connected component.

Something like:

from sets import Set

def keygroups(dictKT):
    dictTK = {}
    for k,tlist in dictKT.iteritems():
        for t in tlist:
            dictTK.setdefault(t,[]).append(k)
    visitedK = Set()
    visitedT = Set()
    for k in dictKT:
        if k not in visitedK:
            component = Set([k])
            unexplored = [k]
            while unexplored:
                k = unexplored.pop()
                component.add(k)
                for t in dictKT[k]:
                    if t not in visitedT:
                        visitedT.add(t)
                        for k in dictTK[t]:
                            if k not in visitedK:
                                visitedK.add(k)
                                unexplored.append(k)
            yield list(component)

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science