473,699 Members | 2,679 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 2107
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************ ********@comcas t.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()
for h in itertools.chain (starts, heads):
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>py2 4 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 thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 16 3382 by: aruna | last post by: Given a set of integers, how to write a program in C to sort these set of integers using C, given the following conditions a. Do not use arrays b. Do not use any comparison function like if/then or switch-case c. you can use pointers only d. you cannot use any of the loops either. 0 3238 by: Brian Henry | last post by: Here is another virtual mode example for the .NET 2.0 framework while working with the list view. Since you can not access the items collection of the list view you need to do sorting another way... here is my code on how I did it to help anyone starting out get an idea of how to use virtual mode in ..NET 2.0 Imports CrystalDecisions.CrystalReports.Engine Imports CrystalDecisions.Shared 7 2188 by: apotheos | last post by: I can't seem to get this nailed down and I thought I'd toss it out there as, by gosh, its got to be something simple I'm missing. I have two different database tables of events that use different schemas. I am using python to collate these records for display. I do this by creating a list of lists that look roughly like this: events = , ...] I then thought I'd just go events.sort(lambda x,y: x