Làm thế nào để tham gia các liên kết trong Python để có được một chu kỳ?

Question

Tôi có một danh sách các liên kết và muốn biết đường dẫn/chu trình đã tham gia.

liên kết của tôi trông như thế này:

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

Và tôi muốn câu trả lời là một chu kỳ như thế (hoặc bất kỳ chu kỳ phù hợp khác):

[0,3,1] 

Vì vậy, bạn lấy phần tử đầu tiên của danh sách con đầu tiên, sau đó bạn lấy phần tử thứ hai và bạn tìm kiếm danh sách con tiếp theo bắt đầu với phần tử này và bạn bắt đầu lại từ đầu.

Có cách nào thanh lịch để thực hiện việc này không? Tôi đã thử chức năng giảm nhưng sau đó các liên kết phải được sắp xếp theo cách mà các liên kết phù hợp.

Answer 1

Có một cách rất thanh lịch để làm điều đó bằng cách sử dụng máy phát điện:

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 

Thứ nhất, nó cho phép lặp lại tự nhiên:

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

Thứ hai, nó cho phép để tạo ra một danh sách một cách dễ dàng:

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

Và cuối cùng, nó cho phép vô hạn thế hệ mục:

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

tôi muốn có một cái nhìn tại python-graph:

tính năng cung cấp và các thuật toán:

...

• phát hiện Cycle

Answer 3

biến nó thành một từ điển, và đi qua nó.

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

Hãy thử điều này, giả định rằng chỉ một chu trình đơn hiện diện trong danh sách liên kết:

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 

Với ví dụ của bạn:

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

Nếu nó có thể là nhiều hơn một chu kỳ tồn tại trong danh sách các liên kết (bạn không đề cập đến nó trong câu hỏi), sau đó bạn nên sử dụng câu trả lời của David Robinson.

Answer 5

Nếu bạn biết có một chu kỳ và tất cả các liên kết đang trong chu kỳ (hoặc ít nhất là không có "chia rẽ" trong định hướng, có nghĩa chỉ có một cách từ bất kỳ điểm nào), bạn có thể sử dụng điều này:

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] 

Những gì nó đang đi qua dữ liệu đã cho, bắt đầu bằng điểm đầu tiên của liên kết đầu tiên. Sau đó, nó chỉ sau tất cả các liên kết cho đến khi nó đạt đến đầu đường dẫn. Khi nó đến đầu đường dẫn, nó sẽ trả về đường dẫn.

Đơn giản và tôi tin rằng nó khá hiệu quả.

Answer 6

Xem xét sử dụng các networkx gói:

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] 

Sản lượng:

>> [0, 3, 1] 

Answer 7

Sử dụng itertools.permutations, điều này sẽ giúp bạn có được bộ các chu kỳ duy nhất:

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 

kết quả trong trường hợp này là [[3, 1, 0], [4, 3, 1]]