better 'splice' function

[gyromagnetic]

Hi,
I have written a function that essentially 'splices' together a number
of tuples in a list, and I would appreciate any suggestions that you
might have on how to make the code or algorithm better.

Each tuple in the input list comprises three strings, e.g.
('A','k1,'B').
The splice function should exhaustively try to match the 'end' (last
element) of one tuple with the 'beginning' (first element) of another
(eliminating the duplicate string) to create the longest tuples
possible.

For instance, if I had as a list

mylist = [('B','k8','C'),('B','k3','D'),('A','k4','E'),
          ('Z','k5','F'),('F','k3','G'),('A','k1','B'),
          ('G','k2','H'),('C','k2','I')]

splice_tuples(mylist) should return

[('Z', 'k5', 'F', 'k3', 'G', 'k2', 'H'), 
 ('A', 'k4', 'E'), 
 ('A', 'k1', 'B', 'k3', 'D'), 
 ('A', 'k1', 'B', 'k8', 'C', 'k2', 'I')]


As another example,

mylist = [('B','k8','C'),('B','k3','D'),('A','k4','E'),
          ('Z','k5','F'),('F','k3','G'),('A','k1','B'),
          ('G','k2','H'),('C','k2','I'),('H','k6','A')]

splice_tuples(mylist) should return

[('A', 'k4', 'E'), 
[('Z', 'k5', 'F', 'k3', 'G', 'k2', 'H', 'k6', 'A', 'k1', 'B', 'k8',
'C', 'k2', 'I'),
('Z', 'k5', 'F', 'k3', 'G', 'k2', 'H', 'k6', 'A', 'k1', 'B', 'k3',
'D'),
('Z', 'k5', 'F', 'k3', 'G', 'k2', 'H', 'k6', 'A', 'k4', 'E')]


The same symbol will not appear as the first and last elements of a
tuple in the input list. Also, there won't be 'loops' in the input
data; input lists like [('A','k1','B'),('B','k2','C'),('C','k3','A')]
won't happen.

I'd appreciate any advice you may have on how to improve the
(admittedly klunky) code below.

I'm using Python v2.2.

Thanks.

-Brad


#-------------------------------------------------------------------
def splice_tuples(rlist):

    spliced_list, spliced_dict, mdict = [], {}, {}

    map(mdict.setdefault,rlist,[1]*len(rlist))

    fdict, ldict = {}, {}
    spliced_dict = {}

    for item in rlist:
        t0,t2 = item[0],item[-1]
        if fdict.has_key(t0):
            if not item in fdict[t0]: fdict[t0].append(item)
        else:
            fdict[t0] = [item]
        if ldict.has_key(t2):
            if not item in ldict[t2]: ldict[t2].append(item)
        else:
            ldict[t2] = [item]

    def splice(ltup1,ltup2):
        if not ltup1 or not ltup2: return []
        ltup = []
        for t1 in ltup1:
            for t2 in ltup2:
                if t1[0] == t2[-1]:
                    tup = t2 + t1[1:]
                    if tup not in ltup: ltup.append(tup)
                if t1[-1] == t2[0]:
                    tup = t1 + t2[1:]
                    if tup not in ltup: ltup.append(tup)
        return ltup

    while mdict:
        cur_t0 = mdict.keys()[0]
        del mdict[cur_t0]
        rcur, pcur = cur_t0[0], cur_t0[-1]
        new_t0 = []

        if ldict.has_key(rcur):
            new_t0 = splice(ldict[rcur],[cur_t0])
            map(mdict.setdefault,new_t0,[1]*len(new_t0))

        if fdict.has_key(pcur):
            new_t0 = splice(fdict[pcur],[cur_t0])
            map(mdict.setdefault,new_t0,[1]*len(new_t0))

        if not new_t0:
            spliced_dict[cur_t0] = 1

    spliced_list = spliced_dict.keys()

    return spliced_list