Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to join links in Python to get a cycle?

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.

like image 305
dominik Avatar asked Jan 10 '12 20:01

dominik


4 Answers

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
like image 61
e-satis Avatar answered Nov 16 '22 20:11

e-satis


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]
like image 23
Max Li Avatar answered Nov 16 '22 19:11

Max Li


I'd take a look at python-graph:

Provided features and algorithms:

...

  • Cycle detection
like image 1
jcollado Avatar answered Nov 16 '22 20:11

jcollado


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]]
like image 1
David Robinson Avatar answered Nov 16 '22 20:11

David Robinson