Sorting tuples in Python like dominoes/ finding vertex connectivity

Question

I have a list of integer tuples like this:

L=[(1,2),(7,6),(2,3),(8,5),(3,8),(5,7)]

Each pair defines an edge between two vertices and I want to find the vertex connectivity. There are no loops, the tuples always uniquely link up like dominoes so in this case the sorted list should look like:

L_sorted=[(1,2),(2,3),(3,8),(8,5),(5,7),(7,6)]

Or alternatively

L_sorted=[1,2,3,8,5,7,6]

Is there an efficient way to do sorting like this in Python using predefined methods?

Answer 1

I do not think that any built-in facility can solve this. Third-party libraries might help. You can solve it in pure python:

L=[(1,2),(7,6),(2,3),(8,5),(3,8),(5,7)]
def domino(l):
    start = cursor = l[0][0]
    d = dict(l)
    while True:
        yield cursor
        try:
            cursor = d[cursor]
        except KeyError:
            # return here if your input may be non-cyclic.
            raise
        if cursor==start:
            return
x = list(domino(L))
# raises KeyError because 6 is dangling...

... or brew some C code using ctypes.