如何在Python中连接链接以获得循环？

Question

我有一个链接列表，想知道连接的路径/循环。

我的链接如下所示：

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

我希望答案是这样的循环（或任何其他匹配的循环）：

[0,3,1]

因此，您采用第一个子列表的第一个元素，然后采用第二个元素，然后查找下一个子列表有了这个元素，你就可以重新开始。

有没有一种优雅的方法来实现这一点？我尝试了reduce 函数，但是必须以链接匹配的方式对链接进行排序。

Answer 1

使用生成器有一种非常优雅的方法：

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

首先，它允许自然迭代：

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

其次，它允许轻松创建列表：

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

最后，它允许无限的项目生成：

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

考虑使用 networkx 包：

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]

输出：

>> [0, 3, 1]

Answer 3

我会看一下 python-graph：

提供的功能和算法：

...

• 周期检测

Answer 4

把它变成一本字典，然后循环浏览它。

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

尝试一下，假设链接列表中仅存在一个循环：

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

以您的示例为例：

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

如果链接列表中可能存在多个循环（您在问题中没有提及），那么您'最好使用大卫罗宾逊的答案。

Answer 6

如果您知道存在一个循环并且所有链接都在循环中（或者至少方向上没有“分裂”，这意味着从任何给定点只有一种方式< /strong>），您可以使用它：

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]

它的作用是从第一个链接的第一个点开始遍历给定的数据。然后它只跟踪所有链接，直到到达路径的开头。当它到达路径的开头时，它返回该路径。

很简单，而且我相信它非常有效。

Answer 7

使用 itertools.permutations，这将为您提供一组唯一的循环：

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

本例中的结果为 [[3, 1, 0], [4, 3, 1]]