Re: Sorting an Edge List
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
Re: Sorting an Edge List
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.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Sorting an Edge List
In article <[EMAIL PROTECTED]>,
"Anthony D'Agostino" <[EMAIL PROTECTED]> 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? :-)
--
http://mail.python.org/mailman/listinfo/python-list
Re: Sorting an Edge List
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Sorting an Edge List
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
--
http://mail.python.org/mailman/listinfo/python-list
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?
--
http://mail.python.org/mailman/listinfo/python-list
