469,898 Members | 1,792 Online

# Sorting an Edge List

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')].

I was successful in doing this a while back with a modified bubble sort
algorithm, but now I can't find my own code. Can the list be sorted with a
comparison function or some other way?

Jul 19 '05 #1
5 1994
Anthony D'Agostino, this is my first raw version, it can fail in lots
of ways depending on your input list l (and surely there are better
ways to do it), but it's a start:

.. l = [('A','Y'), ('J','A'), ('Y','J')]
.. pairs = dict(l)
.. result = []
.. key = pairs.iterkeys().next()
.. while pairs:
.. val = pairs.pop(key)
.. result.append( (key, val) )
.. key = val
.. print result

Bear hugs,
Bearophie

Jul 19 '05 #2
Sort demands a unique ordering, which isn't present in your case.
You're constructing an Eulerian path. See Fleury's algorithm:

http://en.wikipedia.org/wiki/Eulerian_path

Jul 19 '05 #3
In article <fL********************@comcast.com>,
"Anthony D'Agostino" <ga*******@dope.comcast.net> wrote:
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')].

This is an interesting problem. Can you give us more details? I'm
assuming the length of the list can be any arbitrary length. Will there
always only be three letters? Can there ever be a pair with the same first
and second elements, i.e. ('A', 'A')?

Will there always be a valid solution? For example, it's trivial to show
that

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

cannot be sorted using your criteria (there's no pair starting with 'Y' to
match the one that ends with 'Y')

Is this a real-life problem, or are we doing your homework for you? :-)
Jul 19 '05 #4
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.
Jul 19 '05 #5
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])
out = []
seen = set()
curr = nodes[h]
sub = []
while curr not in seen:
sub.append(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
Jul 19 '05 #6

### This discussion thread is closed

Replies have been disabled for this discussion.