How to join links in Python to get a cycle?

Question

I have a list of links and want to know the joined path/cycle.

My links look like this:

[[0, 3], [1, 0], [3, 1]]

And I want the answer to be a cycle like that (or any other matching cycle):

[0,3,1]

So you take the first element of the first sublist, then you take the second element and you look for the next sublist starting with this element, and you start all over again.

Is there an elegant way to accomplish this? I tried the reduce function but then the links have to be sorted in a way that the links match.

Answer 1

There is a very elegant way to do it using a generator:

def cycle(lst, val, stop=None):
    d = dict(lst)
    stop = stop if stop is not None else val
    while True:
        yield val
        val = d.get(val, stop)
        if val == stop: break

Firstly, it allows natural iteration:

>>> for x in cycle([[0, 3], [1, 0], [3, 1]], 0):
....    print x
....
0
3
1

Secondly, it allows to create a list easily:

>>> list(cycle([[0, 3], [1, 0], [3, 1]], 0))
[0, 3, 1]

And eventually, it allows infinite item generation:

>>> generator = cycle([[0, 3], [1, 0], [3, 1]], 0, Ellipsis)
>>> generator.next()
... 0
>>> generator.next()
... 3
>>> generator.next()
... 1
>>> generator.next()
... 0
>>> generator.next()
... 3
>>> generator.next()
... 1
>>> generator.next()
... 0
>>> generator.next()
... 3

Answer 2

Consider using the networkx package:

import networkx as nx
G = nx.DiGraph() #creates directed graph
G.add_edges_from([[0, 3], [1, 0], [3, 1]])
print nx.simple_cycles(G).pop()[:-1]

The output:

>> [0, 3, 1]

Answer 3

I'd take a look at python-graph:

Provided features and algorithms:

...

• Cycle detection

Answer 4

Turn it into a dictionary, and cycle through it.

def get_cycles(links):
    """Get a list of all cycles given a list of links"""
    links_dict = dict(links)
    ret = []
    ret_sets = []
    for starting_point in links_dict:
        cycle = []
        x = starting_point
        while x != None:
            cycle.append(x)
            x = links_dict.get(x)
            if x == starting_point:
                break
        # make sure the cycle is not a repeat (and was a cycle)
        if x != None:
            cycle_set = set(cycle)
            if cycle_set not in ret_sets:
                    ret.append(cycle)
                    ret_sets.append(cycle_set)
    return ret

assert get_cycles([[0, 3], [1, 0], [3, 1]]) == [[0, 3, 1]]
assert get_cycles([[0, 3], [1, 0], [3, 1], [5, 2]]) == [[0, 3, 1]]
assert get_cycles([[0, 3], [1, 0], [3, 1], [5, 2], [2, 5]]) == [[0, 3, 1], [2, 5]]

Answer 5

Try this, assuming that only a single cycle is present in the list of links:

def cycle_list(links):
    d = dict(links)
    ele = links[0][0]
    nxt = d[ele]
    lst = [ele]
    seen = set(lst)
    while nxt not in seen:
        lst.append(nxt)
        seen.add(nxt)
        ele = nxt
        nxt = d[ele]
    return lst

With your example:

cycle_list([[0, 3], [1, 0], [3, 1]])
> [0, 3, 1]

If it's possible that more than one cycle exists in the list of links (you don't mention it in the question), then you're better off using David Robinson's answer.

Answer 6

If you know there is a cycle and all the links are in the cycle (or at least there are no "splits" in the directions, meaning there is only one way from any given point), you can use this:

def get_cycle(data):
    d = dict(data)
    first = data[0][0]
    current = d[first]
    path = [first]
    while True:
        if current == first:
            return path
        else:
            path.append(current)
            current = d[current]

What it does is walking through the given data, beginning with the first point of the first link. Then it just follows all the links until it reaches the beginning of the path. When it reaches the beginning of the path, it returns the path.

Simple and I believe it is pretty efficient.

Answer 7

Using itertools.permutations, this will get you the set of unique cycles:

import itertools

g = [(0,3), (1,0), (3,1), (1,4), (4,3)]

cycles = {}
for edges in itertools.permutations(g):
    start = prev = edges[0]
    for i, edge in enumerate(edges[1:], start=1):
        if prev[1] != edge[0]:
            break
        if edge[1] != start[0]:
            prev = edge
            continue
        cycles.update({tuple(sorted(edges[0:i+1])): edges[0:i+1]})
        break

result = []
for cycle in cycles.values():
    result.append([edge[0] for edge in cycle])

print result

the result in this case being [[3, 1, 0], [4, 3, 1]]