Come unire i collegamenti in Python per ottenere un ciclo?

Question

Ho una lista di link e voglio conoscere il percorso / ciclo unito.

I miei links simile a questa:

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

E voglio la risposta sia un ciclo del genere (o qualsiasi altro ciclo di corrispondenza):

[0,3,1]

Quindi si prende il primo elemento della prima sottolista, poi si prende il secondo elemento e si guarda per la prossima sottolista a partire da questo elemento, e si avvia di nuovo.

C'è un modo elegante per ottenere questo risultato? Ho provato la funzione di ridurre, ma poi i link devono essere ordinati in modo che i collegamenti corrispondano.

Answer 1

C'è un modo molto elegante per farlo utilizzando un generatore:

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

In primo luogo, esso consente iterazione naturale:

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

In secondo luogo, permette di creare facilmente un elenco:

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

E alla fine, permette la generazione voce infinita:

>>> 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

Si consiglia di utilizzare l'href="http://networkx.lanl.gov/" rel="noreferrer"> NetworkX pacchetto :

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]

L'output:

>> [0, 3, 1]

Answer 3

mi piacerebbe dare un'occhiata alla python-grafico :

caratteristiche fornite e algoritmi:

...

• rilevazione del ciclo

Answer 4

trasformarlo in un dizionario, e il ciclo attraverso di essa.

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

Prova questo, supponendo che solo un singolo ciclo è presente nella lista di link:

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

Con il vostro esempio:

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

Se è possibile che più di un ciclo esiste nella lista di link (non menzionarlo nella domanda), allora è meglio utilizzare la risposta di David Robinson.

Answer 6

Se si conosce c'è un ciclo e tutti i link sono nel ciclo (o almeno non ci sono "spaccature" nelle direzioni, il che significa c'è solo un modo da qualsiasi dato punto ), è possibile utilizzare questo:

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]

Ciò che fa è a piedi attraverso i dati forniti, a cominciare dal primo punto del primo collegamento. Poi si segue solo tutti i link fino a raggiungere l'inizio del percorso. Quando raggiunge l'inizio del percorso, che restituisce il percorso.

Semplice e credo che sia abbastanza efficiente.

Answer 7

Utilizzando itertools.permutations, questo ti porterà la serie di cicli unici:

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

Il risultato in questo caso è [[3, 1, 0], [4, 3, 1]]