Sorting an Edge List

[Anthony D'Agostino]

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?

 

[bearophileHUGS]

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

 

[Lonnie Princehouse]

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

 

[Roy Smith]

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?

 

[Anthony D'Agostino]

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.

 

[Bengt Richter]

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