On Fri, 29 Apr 2005 23:37:39 -0400, "Anthony D'Agostino" <ga*******@dope.comcast.net> wrote:

I found my old bubble sort solution:

============================================

def esort(edges):

while 1:

swaps = 0

for j in range(len(edges)-2):

if edges[j][1] != edges[j+1][0]:

edges[j+1],edges[j+2] = edges[j+2],edges[j+1] # swap

swaps = 1

if swaps == 0: break

return edges

print esort([('A','Y'), ('J','A'), ('Y','J')])

print esort([(5,0), (6, -12), (0,6), (-12, 3)])

============================================

The list can be any length and there will always be multiple valid

solutions, depending on which edge you start with. I'm using this to sort

edges for mesh subdivision. I just thought there might be a more elegant way

to write it.

This is not tested beyond what you see, but it might give some ideas for

what you want to do. I finds separate sequences if you combine the above into

one, e.g.,

----< dagostinoedges.py >-----------------------------------------------------------

# I need to sort this list:

# [('A','Y'), ('J','A'), ('Y','J')] like this:

# [('A','Y'), ('Y','J'), ('J','A')].

#

# Note how the Ys and Js are together. All I need is for the second element of

# one tuple to equal the first element of the next tuple. Another valid

# solution is [('J','A'), ('A','Y'), ('Y','J')].

#

import itertools

def connect(edges):

nodes = dict([(e[0], e) for e in edges])

heads = set([e[0] for e in edges])

tails = set([e[1] for e in edges])

starts = heads - tails

out = []

seen = set()

for h in itertools.chain(starts, heads):

curr = nodes[h]

sub = []

while curr not in seen:

sub.append(curr)

seen.add(curr)

curr = nodes.get(curr[1])

if curr is None: break

if sub: out.append(sub)

return out

if __name__ == '__main__':

edges = set([('A','Y'), ('J','A'), ('Y','J'),

(5,0), (6, -12), (0,6), (-12, 3),

('all', 'alone')])

for sub in connect(edges): print sub

------------------------------------------------------------------------------------

Result:

[ 2:54] C:\pywk\clp>py24 dagostinoedges.py

[('all', 'alone')]

[(5, 0), (0, 6), (6, -12), (-12, 3)]

[('A', 'Y'), ('Y', 'J'), ('J', 'A')]

Regards,

Bengt Richter