¿Cómo unir enlaces en Python para obtener un ciclo?

Question

Tengo una lista de enlaces y quiero saber la ruta/ciclo unido.

Mis enlaces se ven así:

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

Y quiero que la respuesta sea un ciclo así (o cualquier otro ciclo de adaptación):

[0,3,1] 

Así se toma el primer elemento de la primera sublista, luego toma el segundo elemento y busca la siguiente sublista que comienza con este elemento, y comienza de nuevo.

¿Hay una forma elegante de lograr esto? Intenté la función de reducción, pero luego los enlaces deben ordenarse de manera que coincidan los enlaces.

Answer 1

Hay una forma muy elegante de hacerlo usando un generador:

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 

En primer lugar, permite la iteración natural:

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

segundo lugar, permite crear una lista fácilmente:

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

Y finalmente, permite la generación de posiciones 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

me gustaría echar un vistazo a python-graph:

características y algoritmos prestados:

...

• detección Ciclo

Answer 3

convertirlo en un diccionario, y recorrerlo.

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 4

Prueba de esto, suponiendo que sólo un único ciclo está presente en la lista de enlaces:

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 su ejemplo:

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

Si es posible que más de un ciclo existe en la lista de enlaces (no lo menciona en la pregunta), entonces es mejor que use la respuesta de David Robinson.

Answer 5

Si conoces hay un ciclo y todos los enlaces están en el ciclo (o al menos no hay "divisiones" en las direcciones, lo que significa sólo hay un camino desde cualquier punto dado), se puede usar esto:

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] 

Lo que hace es caminar a través de los datos dados, comenzando con el primer punto del primer enlace. Luego sigue todos los enlaces hasta que llega al comienzo de la ruta. Cuando llega al comienzo de la ruta, devuelve la ruta.

Simple y creo que es bastante eficiente.

Answer 6

Considere el uso de la networkx paquete:

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] 

La salida:

>> [0, 3, 1] 

Answer 7

Usando itertools.permutations, esto le dará el conjunto de ciclos únicas:

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 

el resultado en este caso ser [[3, 1, 0], [4, 3, 1]]