サイクルを得るためにPythonにリンクを結合する方法は？

Question

リンクのリストがあり、結合されたパス/サイクルを知りたいと思っています。

私のリンクは次のようになります：

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

そして、私は答えをそのようなサイクル（または他の一致するサイクル）にしたい：

[0,3,1]

したがって、最初のサブリストの最初の要素を取り、次に2番目の要素を取り、この要素から始まる次のサブリストを探して、もう一度やり直します。

これを達成するためのエレガントな方法はありますか？還元機能を試しましたが、リンクを一致させる方法でリンクをソートする必要があります。

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

これを試してみてください。リンクのリストには1つのサイクルのみが存在すると仮定します。

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]

リンクのリストに複数のサイクルが存在する可能性がある場合（質問には言及していません）、David Robinsonの答えを使用する方が良いでしょう。

Answer 6

ご存知であれば サイクルがあります そして、すべてのリンクはサイクルにあります（または、少なくとも方向に「分割」はありません。つまり 特定のポイントから1つの方法しかありません）、これを使用できます。

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