algorizm to merge nodes

[Scott David Daniels]

JD wrote:
> It could be a very good "homework assignment".
> This is for a real application.

def do_nets(pairs):
     r = {}
     for a, b in pairs:
         if a in r:
             a_net = r[a]
             if b not in a_net: # if not redundant link
                 if b in r: # Need to merge nets
                     a_net |= r[b]
                     for x in r[b]:
                         r[x] = a_net
                 else: # add a single node to the net
                     a_net.add(b)
                     r[b] = a_net
         elif b in r: # add this node to another net
             r[b].add(a)
             r[a] = q[b]
         else: # create a new net
             r[a] = r[b] = set([a, b])
     # r holds the result nets, but each net is in values multiple times
     # So, get the unique elements in r's values.
     return dict((id(x), x) for x in r.values()).values()

for group in do_nets([['a', 'b'], ['c', 'd'], ['e', 'f'], ['a', 'g'],
                       ['e', 'k'], ['c', 'u'], ['b', 'p']]):
     print group

--Scott David Daniels
Scott.Daniels at Acm.Org