Sorting an Edge List

[Bengt Richter]

On Fri, 29 Apr 2005 23:37:39 -0400, "Anthony D'Agostino" <gamma-ray at 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])
    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