On Fri, 29 Apr 2005 23:37:39 -0400, "Anthony D'Agostino" <[EMAIL PROTECTED]>
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
--
http://mail.python.org/mailman/listinfo/python-list
